I wrote a program to play unbeatable tictactoe in my experimental functional language PYFL.
(PYFL = Python based functional language; henceforth PyFL)
Of course writing a tictactoe player is hardly a major challenge, but I wanted to see how it turned out in PyFL. It worked out rather well, as you’ll see. It made good use of most of PyFL”s new features, especially variable binding operators.
Let’s start with boards. I number the cells 1-9 in the usual way, so that e.g. 5 is the center square and 9 is the bottom right corner. The players are the words “X” and “O” and an empty cell is “.”.
A board is represented as a function that assigns one of these three values to every cell. Thus we have
cells = [1 2 3 4 5 6 7 8 9]; startingboard(c) = ".":
(I’ll put the complete program at the end as an appendix.)
The main part of the program is a big while loop (while loops are translated into tail recursion).
The loop variables are board, player and a counter ix and their recurrence definitions are
board = startingboard fby MakeMove(move, player); player = X fby opponent(player); ix = 1 fby ix+1;
The variable move is the move made by the current player. If the current player is X, you (who are playing X against the computer) are prompted to input your move. Otherwise the move (for O, who is being played by the program) is calculated by a formula.
The program does not use a min/max algorithm. Instead, it uses a half dozen prioritized heuristics which I believe make it unbeatable. These heuristics needed twiddling because on two occasions I managed to beat the program I thought was unbeatable. The heuristics are, in order of priority:
- – Make a winning move (for O) if there is one
- – Block a win for X, if X has a winning move
- – Take the center, if it’s open
- – Take a corner, if it’s empty and surrounded by X’s
- – Take the middle of a side or bottom or top, if one is free
- – Take a corner, if one is free
- – Take one of whatever’s left
When there is more than one move which satisfies the heuristic, the program chooses one at random.
The rest of the program codes up these heuristics and displays the sequence of moves and board images.
First, making a move: the result is a function identical to the current function except for its value at the move being made:
MakeMove(p,m) = b where b(c) = if c==m then p else board(c) fi;
(this uses a where clause, which is often clearer than a valof);
Next we have the crucial definition of a winning move for a player. It’s one which is the open cell in a line (vertical, horizontal or diagonal) in which the other two cells are occupied by the player.
WinningMoves(p) = (% HasWinningMove, WinningMove %) where lines = Openlines(p); HasWinningMove = lines != ; l = hd(lines); WinnningMove = firstof c in l: board(c) == "." end; end; OpenLines(p) = those l in alllines: WinFor(p,l) end; WinFor(p,l) = not exist c in l: board(c) == opponent(p) end and 1 = sumfor c in l: board(c) == "." all 1 end;
The definition of move is an if that checks for the preconditions of each heuristic and returns a corresponding move if the precondition is satisfied.
move = if player == X then InputXMove HasWinX then outputln('win X') && WinX HasWinO then outputln('win O') && WinO CenterFree then outputln('center') && Center ExistThreatenedCorner then outputln('thrd corner') && ThreatenedCorner FreeSide then outputln('side') && Side ExistOpenCorner then outputln('open corner') && OpenCorner else outputln('random') && RandomMove fi where
(The Outputln calls report which heuristic is used for each computer move.) These variables, like ThreatenedCorners, all have similar definitions. For example,
ExistThreatenedCorner, ThreatenedCorner = ThreatenedCorners; ThreatenedCorners = (% htc, tc %) where htc = tcorners != ; tcorners = those cr in corners: board(el1(cr)) = "." and board(el2(cr)) = X and board(el3(cr)) = X end; tc = el1(tcorners); end; Corners = [[1 2 4][3 2 6][7 4 8][9 8 6]];
In each the first value is a Boolean which, if true, confirms that the second is available. The (% %) tuples are lazy so that evaluating the first component does not necessarily trigger evaluation of the second, which could produce errors.
There remains the code to display the board. DisplayBoard produces the characters (including newlines) that produce an image of the current board.
DisplayBoard= concatfor r in rows all DisplayRow(r)^'\n' end^'\n' where DisplayRow(r) = concatfor c in r all Icon(board(c)) end ; Icon(m) = if m== X then 'X ' m== O then 'O ' else '. ' fi; end;
The output is produced as a side effect of the loop while condition:
outputs(DisplayBoard) && not(HasWonX or HasWonO or IsTie) and ix<10
The expression outputs(DisplayBoard) has the side effect of sending the string DisplayBoard to the terminal (yes, a shameless side effect – but no monads). The && operator evaluates its first argument, ignores the result, and returns the result of its second.
The result of the while loop announces the outcome of the game:
result = if HasWon(X) then 'Congratulations, you win!' HasWon(O) then 'Yay, I win!' else 'A tie!' fi;
I’ll be releasing PyFL as a zip file once I clean it up a bit. I’ll include the tictactoe program so you can try your luck against it. I claim it’s unbeatable but it could be that the heuristics still need tweaking, Good luck!
APPENDIX – THE COMPLETE PROGRAM
res = while outputs(DisplayBoard) && not(HasWon(X) or HasWon(O) or IsTie) and ix != 10 board = startboard fby MakeMove(player,move); O = "O"; X = "X"; ix = 1 fby ix+1; player = "X" fby opponent(player); opponent(p) = if p == X then O p == O then X else "." fi; move = if player== X then InputXMove HasWinX then outputln('win X') && WinX HasWinO then outputln('win O') && WinO CenterFree then outputln('center') && Center ExistThreatenedCorner then outputln('thrd corner') && ThreatenedCorner FreeSide then outputln('side') && Side ExistOpenCorner then outputln('open corner') && OpenCorner else outputln('random') && RandomMove fi where InputXMove = input(str(ix)+' - choose an empty cell '); HasWinX, WinX = WinningMove(X); HasWinO, WinO = WinningMove(O); ExistOpposingCorner, OpposingCorner = OpposingCorners; ExistThreatenedCorner, ThreatenedCorner = ThreatenedCorners; ExistOpenCorner, OpenCorner = OpenCorners; FreeSide, Side = FreeSides; CenterFree = board(5) == "."; Center = 5; end; MakeMove(p0,c0) = if board(c0) != "." then error('overplay '+str(p0)+str(c0)) else b fi where b(c) = if c0 == c then p0 else board(c) fi; end; HasWon(p) = // p has already won exist l in lines: forall c in l: board(c) == p end end; IsTie = // board is tied - game over no winner forall c in cells : board(c) != "." end; OpenLines(p) = // lines where p has a winning move those l in lines: WinFor(p,l) end ; WinFor(p,l) = //p can win playing in l not exist c in l: board(c) == opponent(p) end; and 1 == sumfor c in l: board(c) == "." all 1 end; WinningMove(p) = // a winning move for p (% haswin, winningmove %) where ls = OpenLines(p); haswin = ls != ; l = hd(ls); winningmove = firstof c in l:board(c) == "." end; end; FreeSides = (% fs, s %) where fss = those c in Sides: board(c) == "." end; fs = fss !=  and not(board(5) == "X"); s = randomelement(fss); end; ThreatenedCorners = (% etc, tc %) where tcs = those r in Corners: board(el1(r)) == "." and board(el2(r)) == X and board(el3(r)) == X end; etc = tcs != ; tc = el1(el1(tcs)); end; OpposingCorners = (%eoc,oc %) where dcs = those l in DiagonalCorners: board(el1(l)) == "." and board(el2(l)) == X end; eoc = dcs != ; oc = el1(el1(dcs)); end; OpenCorners = (% opcok, opc %) where opcs = those r in Corners: board(el1(r)) == "." end; opcok = opcs != ; ropc = randomelement(opcs); opc = el1(ropc); end; RandomMove = m where poss = those c in cells: board(c) == "." end; m = randomelement(poss); end; DisplayBoard= concatfor r in rows all DisplayRow(r)^'\n' end^'\n' where DisplayRow(r) = concatfor c in r all Icon(board(c)) end ; Icon(m) = if m== X then 'X ' m== O then 'O ' else '. ' fi; end; result = if HasWon(O) then 'Yay, I Win!' HasWon(X) then 'Congrats, you win!' IsTie then 'Tie!' else error('inconclusive outcome') fi; end; cells = [1 2 3 4 5 6 7 8 9]; startboard(c) = "."; lines = rows<>columns<>diagonals; rows = [[1 2 3] [4 5 6] [7 8 9]]; columns = [[1 4 7] [2 5 8] [3 6 9]]; diagonals = [[1 5 9][3 5 7]]; Corners = [[1 2 4][3 6 2][7 4 8][9 8 6]]; DiagonalCorners = [[1 9][9 1][7 3][3 7]]; el1(l) = hd(l); el2(l) = el1(tl(l)); el3(l) = el2(tl(l)); Sides = [2 4 6 8];