Unbeatable? Tictactoe in PyFL

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];

About Bill Wadge

I am a retired Professor in Computer Science at UVic.
This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to Unbeatable? Tictactoe in PyFL

  1. sness says:

    Very engaging post, and helpful to see an entire program in PyFL. Looking forward to trying it when it’s released.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.