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<10The 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];
Bill Wadge's Blog 
Very engaging post, and helpful to see an entire program in PyFL. Looking forward to trying it when it’s released.