tictactoe.org
Table of Contents
1 PREFACE
Originally, this code was developed as part of the interview process for the Spring 2017 batch at the Recurse Center. The [[https://gist.github.com/brudgers/3f464e36e3c7ef142ec13effbb4f378b]] [original Gist].
My 'what will you work on' proposal was to work through Norvig's Paradigms of Artificial Intelligence: case studies in Common Lisp with the goal of learning 'classic' AI at the agent level (in contrast to studying lower abstraction layer implementation mechanisms such as deep neural networks). TicTacToe seemed to fit into that program of study more thouroughly than the other alternatives, i.e. the interview part of the exercise was to pair program on addding a feature so that the program could play.
Emacs (alongside JavaScript and Linux) has been a specific focus for my technical interest since the beginning of 2016. Emacs Lisp was chosen as the implemenation language as part of that ongoing project and with an eye toward the possibility that via Emacs Lisp, Emacs might make a good prototyping environment for 'classic' AI agents given the relationship of 'classic' AI to Lisp.
1.1 Make the files
- The output for this file is
tictactoe.el. - The web page for this file is
docs/index.html. It is structured to work with Github pages. - To generate these files, navigate into the source block and use
M-x org-babel-execute-src-block.
;; generate tictactoe.el (org-babel-tangle) ;; generate docs/index.html (org-html-export-as-html) (save-current-buffer (set-buffer "*Org HTML Export*") (write-file "docs/index.html") (kill-buffer)) (concat "Files Generated: " (current-time-string))
Files Generated: Mon Jan 23 19:21:58 2017
2 INTRODUCTION
2.1 INSTRUCTIONS
- Open this file in Emacs
- M-x ielm to start IELM
- C-x b RET to return to source file
- M-x eval-buffer to evaluate source file
- C-x 3 to split windows
- C-x b RET to put IELM in window
- (setup) at the ELISP> prompt
- C-x o to return to the code window
- C-x b tictactoe to bring up the display window
- C-x o to return to the IELM window
- (tictactoe-play) at ELISP> prompt to play game
2.2 GAME DESIGN BACKGROUND
Adapted from Artificial Intelligence: A Modern Approach, Russell and Norvig, 1995. [pages 123-124]
A game consists of:
- |Initial State| which consists of a board position and an indication of whose move it is.
- A set of |Terminal States|.
- A set of |Operators| which define the legal moves a player can make.
- A |Terminal Test| which determines when the game is over.
- A |Utility Function| which assigns a numeric value to each Terminal State of the game.
2.3 INTERFACE DESIGN BACKGROUND
Game play is displayed in a new buffer named "tictactoe", but commands are entered via the mini-buffer in the IELM window. The overall exercise included learning a bit more about Emacs in general, and Emacs Lisp in particular. The implementation reflects the fact that this is the first time trying to write code for (rather than in) the Emacs environment and proves that "How hard could it be?" is not often a question that produces the expected answer. The tutorial: Emacs Lisp Animation http://dantorop.info/project/emacs-animation/ was invaluable.
3 HEADER
The output file defaults to tictactoe.el.
;;; Auto generated from tictactoe.org ;;; ;;; To generate a new copy: M-x org-babel-tangle
4 IMPORTS
During development, it was helpful to use some Common Lisp constructs. Over the long run, this practice might not be worth the confusion regarding documenation lookup. On the other hand, Common Lisp does provide some well documented and useful tools.
(require 'cl)
5 INITIAL STATE
The initial state of the |Environment| is an empty board. Environment is a useful abstraction which I did not fully employ at the beginning of the exercise.
5.1 Board
(defun make-empty-board () "Returns an empty ticktacktoe board. Example: () -> (0 0 0 0 0 0 0 0 0)" (make-list board-size empty-square)) (defconst board-size 9 "A BOARD consists of 9 squares. A board's squares are arranged in a 3x3 grid. 0 | 1 | 2 ----------- 3 | 4 | 5 ----------- 6 | 7 | 8 ")
5.2 Square Contents
Each square has a contents. A SQUARE contents is one of: empty-square | player-1-square | player-2-square.
(defconst empty-square 0 "A zero value represents an empty (unmarked) square.") (defconst player-1-square 1 "The value 1 represents a square marked by player-1.") (defconst player-2-square -1 "The value -1 represents a square marked by player-2")
5.3 Board Helpers
These functions organize a board by rows, columns and diagonals to aid in the search for winning conditions.
(defun get-rows (board)
"Returns a list of board rows represented as lists of their square's contents.
Board -> List(List : Squares)
Example: (1 0 -1 0 1 -1 0 0 1) -> ((1 0 -1)(0 1 -1)(0 0 1))"
(list
(list (nth 0 board)
(nth 1 board)
(nth 2 board))
(list (nth 3 board)
(nth 4 board)
(nth 5 board))
(list (nth 6 board)
(nth 7 board)
(nth 8 board))))
(defun get-columns (board)
"Returns a list of board columns represented as lists of their square's contents.
Board -> List(List : Squares)
Example: (1 0 -1 0 1 -1 0 0 1) -> ((1 0 0)(0 1 0)(-1 -1 1))"
(list
(list (nth 0 board)
(nth 3 board)
(nth 6 board))
(list (nth 1 board)
(nth 4 board)
(nth 7 board))
(list (nth 2 board)
(nth 5 board)
(nth 8 board))))
(defun get-diagonals (board)
"Returns a list of board diagonals represented as lists of their square's contents.
Board -> List(List : Squares)
Example: (1 0 -1 0 1 -1 0 0 1) -> ((1 1 1)(-1 1 0))"
(list
(list (nth 0 board)
(nth 4 board)
(nth 8 board))
(list (nth 2 board)
(nth 4 board)
(nth 6 board))))
5.4 Players
A PLAYER is one of player-1 | player-2.
(defconst player-1 #'(lambda (square) (= square player-1-square)) "Player-1 is a function that returns true for squares marked by player-1") (defconst player-2 #'(lambda (square) (= square player-2-square)) "Player-1 is a function that returns true for squares marked by player-2")
6 TERMINAL STATES
A finished game is one of: drawn-game | player-1-wins | player-2-wins
6.1 Player 1 or 2 wins
One function covers both cases depending on which player is passed in.
(defun winner-p (player board)
"Returns true if the player has won.
Player Board -> Boolean
Example: (winner-p player-1 '(1 0 -1 0 1 -1 0 0 1)) -> t"
(let
((rows
(map-player-squares player
#'get-rows
board))
(columns
(map-player-squares player
#'get-columns
board))
(diagonals
(map-player-squares player
#'get-diagonals
board)))
(or (some #'identity
(winning-squares rows))
(some #'identity
(winning-squares columns))
(some #'identity
(winning-squares diagonals)))))
6.2 Terminal State Draw
This function is a fall-through from winner-p.
(defun all-squares-filled-p (board) "Utility Function. Returns true if no squares are empty. Board -> Boolean Example: (all-squares-filled-p '(1 0 -1 0 1 -1 0 0 1))) -> nil" (not (some #'zerop board)))
6.3 Terminal State Helpers
(defun map-player-squares (player get-squares board)
"A utility function. Given a board representation, maps true to the squares marked by a player.
Player (Board -> List(List : Squares)) Board -> List(List : Boolean)
Example:
(map-player-squares player-1
#'get-diagonals
'(1 0 -1 0 1 -1 0 0 1))
-> ((t t t)
(nil t nil))
"
(mapcar #'(lambda (x)
(mapcar player x))
(funcall get-squares board)))
(defun winning-squares (map)
"A utility function. Given a mapping of true to a player's squares over a board representation returns true if there is a winning condition.
List(List : Boolean) -> List Boolean
Example:
(winning-squares '((t t t)(nil t nil))) -> t"
(mapcar #'(lambda (list)
(every #'identity list))map))
7 TERMINAL TEST
(defun game-over-p (board) "Example: (game-over-p '(1 0 -1 0 1 -1 0 0 1))) -> 'player-one-wins Example: (game-over-p (make-empty-board)) -> nil" (cond ((winner-p player-1 board) 'player-1-wins) ((winner-p player-2 board) 'player-2-wins) ((all-squares-filled-p board) 'draw)))
8 OPERATORS
The environment (board) is modified by player-1 and player-2. The only modification is choosing a square. The mechanics of player choice could be parameterized.
(defun player-1-choose-square (board)
"Board -> Board"
(insert "Status: It is Player-1's turn\n")
(setf (nth (ttt:human-agent board) board) player-1-square)
board)
(defun player-2-choose-square (board)
"Board -> Board"
(insert "Status: It is Player-2's turn\n")
(setf (nth (ttt:simple-reflex-agent board) board)
player-2-square)
board)
8.1 Operator Helpers
(defun find-empty-squares (board)
"Utility function. Returns a list of indexes to a board's empty squares.
Board -> List:number[0-8]
Example: (find-empty-squares (make-empty-board))
-> (0 1 2 3 4 5 6 7 8)
Example: (find-empty-squares '(1 0 -1 0 1 -1 0 0 1)
-> (1 3 6 7)"
(let ((i 0)
(acc))
(dolist (element board acc)
(if (= 0 (nth i board))
(push i acc))
(setq i (+ i 1)))
(reverse acc)))
9 GAME LOOP
Game play is lacking due to limited integration with the Emacs platform.
9.1 Main Loop
The main loop recurses and mutates a list. Copy semantics seemed like a bit of yak-shaving since the board only lives inside the loop. Philosophically, the idea that it is always the same board and the idea that it might be possible to cheat given enough effort and will also seem consistent with the idea of a game.
(defun tictactoe-main (board)
(board->text board)
(if (game-over-p board)
(game-over-p board)
(let
((board-sum (apply #'+ board)))
(cond
((= board-sum 0)
(tictactoe-main (player-1-choose-square board)))
((= board-sum 1)
(tictactoe-main (player-2-choose-square board)))))))
9.2 Game Loop Helpers
(defun setup () "Setup() configures emacs for gameplay" (get-buffer-create "tictactoe") (set-buffer "tictactoe"))
(defun tictactoe-play ()
"This is an interactive command wrapper around tictactoe-main."
(interactive nil)
(let ((game-outcome (tictactoe-main (make-empty-board))))
(cond
((eq game-outcome 'player-1-wins)
(insert "Game Over: Player-1 Wins"))
((eq game-outcome 'player-2-wins)
(insert "Game Over: Player-2 Wins"))
((eq game-outcome 'draw)
(insert "Game Over: It is a draw")))
game-outcome))
10 USER INTERFACE
Given the game-play mechanics are a kludge this is a work in progress.
10.1 Text representations of boards
(defun square->text (square index)
"Utility function. Converts a square to the correct text value."
(cond
((eq square -1) " o ")
((eq square 1) " x ")
(t (concat " " (prin1-to-string index) " "))))
(defun row->text (row i)
"Utility function. Converts board row to its text representation"
(concat
(square->text (nth 0 row) i)
"|"
(square->text (nth 1 row) (+ i 1))
"|"
(square->text (nth 2 row) (+ i 2))))
(defun board->text (board)
"Utility function. Converts a board to its text representation."
(let* ((brd (get-rows board))
(separator "\n-----------\n")
(row1 (row->text (nth 0 brd) 0))
(row2 (row->text (nth 1 brd) 3))
(row3 (row->text (nth 2 brd) 6)))
(erase-buffer)
(insert "Playing TicTacToe\n\n")
(insert row1)
(insert separator)
(insert row2)
(insert separator)
(insert row3)
(insert "\n\n")))
11 AGENTS
The early versions of the program had players (the business logic abstraction) but not agents (an AI/computational abstraction). I knew I wanted the agent abstraction, but I was trying not to get 'ahead of myself.' Mostly this was a fairly conservative (and more literal) interpretation of the Recurse Center advice not to create a solution to the pair programming portion of the exercise upfront. The reason for the advice was that people got less out of the pair programming exercise. I suspect that it was an over interpretation on my part. On the other hand, I was actively trying to avoid the Lisp version of 'factory factory player factor'…there's a point where nested abstractions stand in the way of getting things done and I was striving for completion in a week.
11.1 Human Agent
The early (embedded) version of this code used (read choice) which creates a "drop tables and launch the missiles" type vulnerability. It was a quick and dirty way to handle the problem while figuring out how to Rube Goldberg some sort of IO.
(defun ttt:human-agent (precept)
"Precept -> Action
A precept is a board. An Action is a square."
(let*
((empty-squares (find-empty-squares precept))
(message (concat "Player-1 choose square: "
(prin1-to-string empty-squares)
" : "))
(choice (read-string message)))
(string-to-number choice)))
11.2 Greedy Agent
When the underlying game logic of Initial State, Terminal State, and Terminal Test was defined, the challenge in developing the Operators was the human interface for the players. To simplify development, I worked on human interaction via Player-1 and had Player-2 automatically pick the first square from the list of empty squares. I've come to think of this as a 'Greedy' approach. A 'greedy' decision forms the final element of the Simple Reflex Agent.
(defun ttt:greedy-agent (precept)
"Precept -> Action
A precept is a board. An Action is a square."
(let*
((empty-squares (find-empty-squares precept)))
(first empty-squares)))
11.3 Random Agent
The Gist I submitted for the interview contained the equivalent of the human agent for both players. At the beginning of the pair session, my suggestion was to first automate one player and then to consider performance. The decision to select a square at random is interesting in regard to agency. I think it boils down to the notion of a precept. An agent makes a decision that is determined by the structure of the precept and an agent that chooses at random seems to be ignoring the structure.
Random selection has a role in computer science but that role seems to be selecting inputs to algorithms (e.g. monte-carlo simulation). In this game, the selection of random-agent is an action on the enviroment but does not fully determine the environment's state from the standpoint of the random-agent: the other player also determines the state.
Thinking about the difference between the greedy-agent and the random-agent, a person or machine could find a pattern in the greedy-agent responses and infer an underlying decision process. There is (pseudo-random-number generation aside) no pattern produced by the random-agent and it is hard to see agency in a mechanism that acts randomly. I think it is akin to McCarthy's remarks about thermostats having beliefs.
Machines as simple as thermostats can be said to have beliefs, and having beliefs seems to be a characteristic of most machines capable of problem solving performance. –John McCarthy
(defun ttt:random-agent (precept)
"Precept -> Action
A precept is a board. An Action is a square."
(let*
((empty-squares (find-empty-squares precept)))
(nth (random (length empty-squares) empty-squares))))
11.4 Simple Reflex Agent
A simple reflex agent matches precepts (here a board) against a set of rules. This one uses a minimal search, so maybe it is not exactly a simple reflex agent. On the other hand, it is possible to see the search as a compression of all the states from which it is possible to win in a single move…i.e. code generation is the ultimate data compression. YMMV.
(defun ttt:simple-reflex-agent (precept)
"precept -> action
A precept is a board.
An action is the label of a square.
The agent prefers winning squares over other squares.
The agent prefers blocking squares over other squares.
The agent prefers the center square over other squares.
The agent prefers corner squares over other squares."
(let* ((options (find-empty-squares precept))
(*player* player-2)
(*other-player* player-1)
(*player-square* player-2-square)
(*other-player-square* player-1-square)
(expansion (expand precept options *player-square*))
(winner (find-winner expansion options *player*))
(center 4)
(corner0 0)
(corner2 2)
(corner6 6)
(corner8 8))
(if winner
winner
(let*
((other-expansion (expand precept
options
*other-player-square*))
(block (find-winner other-expansion
options
*other-player*)))
(cond
(block block)
((memq center options) center)
((memq corner0 options) corner0)
((memq corner2 options) corner2)
((memq corner6 options) corner6)
((memq corner8 options) corner8)
(t (first options)))))))
11.5 Agent Helpers
These helpers are generally useful to any classically designed intelligent agent for tictactoe. Or at least one that uses a some form of search.
(defun expand (board empty-squares player-square)
(let ((new-board (copy-list board)))
(cond
((null empty-squares) nil)
(t (setf (nth (first empty-squares) new-board)
player-square)
(cons new-board
(expand board
(rest empty-squares)
player-square))))))
(defun find-winner (expansion empty-squares player)
(cond
((null expansion) nil)
((winner-p player (first expansion))
(first empty-squares))
(t (find-winner (rest expansion)
(rest empty-squares)
player))))