Tic Tac Toe

version 2, November 6, 2004
Jim Mahoney
based on LightsOn.nb by Rob Raguet-Schofield, Wolfram Research

This second version includes code to have the computer play the game;
version 1 was just a clickable board that let two people play.

Code

Evaluating this code :
All this stuff is evaluated automatically when the file is opened; just click "yes" in the dialog box that pops up.  How does this work?  Read on.

All the cells in this "Code" section have been marked as "initialization" cells, and the notebook itself has been set to always evaluate those that can be evaluated when the file is opened.  All these properties, both for the cells and the notebook, can be seen and changed in the Option Inspector, which is under the Format menu.  

For example, select the Code block, then bring up the Option Inspector, then click the Cell Options tab, and within that the Evaluation Options tab.  Click the Initialization Cell option.  To see what that did, select one of the cells and choose Show Expression. What you'll see is that the InitializationCell->True property has been set.

So here it is

Don't complain if symbol names are similar.

Off[General::spell1];

This next command initializes the Tic Tac Toe game by giving initial values to a number of  global variables and then drawing the board.

init:=Module[{},
	whoseMove="X";
	otherMove="O";
	empty=" ";
	movesMade = 0;
	lastPlayersWinningLine={"O","O","O"};
	thisPlayersWinningLine={"X","X","X"};
	minMaxValue = 1;   (* 1 if whoseMove=="X"; -1 if whoseMove=="O" *)
	board = Table[empty,{3},{3}];
	drawBoard;
	displayMessage[defaultMessage];
	nPositionsLookedAt=0;
	];

What to tell the player about what's going on.

defaultMessage := Module[{},
	If[ isWinner,     Return[ "Game over : " <> ToString[otherMove] <>" wins on move "<>ToString[movesMade] ]];
	If[ movesMade==9, Return[ "Draw"]];
	Return[ToString[whoseMove]<>"'s turn : move " <> ToString[1+movesMade]];
	];

Change whose move it is.
	(Rather than re-caculating things like the row of {"X", "X", "X"} that the "X" player needs to win,
	I'm just swapping a bunch of globals around.)

switchWhoseMove := 
  Module[{tempMove=whoseMove, tempLine=lastPlayersWinningLine},
    minMaxValue = -minMaxValue;
	whoseMove=otherMove;
	otherMove=tempMove;
	lastPlayersWinningLine=thisPlayersWinningLine;
	thisPlayersWinningLine=tempLine;
  	];

Make a move on the board.  "where" is a {row,column} location.

doMove[where_]:=Module[{},
	movesMade++;
	board[[ where[[1]], where[[2]] ]] = whoseMove;
	switchWhoseMove;
	];

Remove a move from the board.  "where" is a {row,column} location.

undoMove[where_]:=Module[{},
	movesMade--;
	board[[ where[[1]], where[[2]] ]] = empty;
	switchWhoseMove;
	];

What do do after a click : make the move on the board, and then redraw it.
And a routine to generate and draw the computer analyzed best move.

doClick[row_, column_ ]:=Module[{},
      doMove[ {row,column} ];
      drawBoard;
      displayMessage[defaultMessage];
      ];

Have the computer make a move and show it.  If we're near the beginning of the game, choose one at random.

doComputerClick:=Module[{extraMessage},
	If[isWinner || movesMade==9, init];
	displayMessage["thinking..."];
	If[ movesMade < 2,
		(*then*) doMove[ randomLegalMove ]; 
				 extraMessage = " (random move)" ,
	    (*else*) doMove[ getComputerMove ];
    			 extraMessage = " (" <> ToString[nPositionsLookedAt] <> 
    			 				" positions in "<>ToString[howLong]<>")"];
    drawBoard;
    displayMessage[defaultMessage <> extraMessage];
	];

Return the best move for the computer.

getComputerMove:=Module[{},
      If[isWinner || movesMade==9, Return[{0,0}]];  (* error return *)
      nPositionsLookedAt = 0;
      howLong = Timing[ boardValue ][[1]];
      Return[bestMove];
      ];

Create a 3x3 array of X's, O's, and (where the board is blank) buttons.

makeClickableBoard:=
    Table[
      If[board[[row,column]]==" ",
        (*then*) makeButton[row,column],
        (*else*) board[[row,column]]
        ],
      {row,1,3},{column,1,3}
      ];

Create a clickable button for an empty row and column spot on the board.

makeButton[row_,column_]:=
	If [ isWinner, 
		(*then*) " ",
		(*else*) ButtonBox[
     				 RowBox[{empty}],
     				 ButtonFunction:>doClick[row,column],
     				 ButtonEvaluator->Automatic,
    				 Active->True,
    				 ButtonMargins->15,
      				 ButtonFrame->"None"
      				]
    ];

Draw the Tic Tac Toe board in the cell whose tag is "TicTacToeBoard".

drawBoard:=Module[{nb},
      nb=SelectedNotebook[];
      NotebookFind[nb,"TicTacToeBoard",All,CellTags];
       NotebookWrite[nb,
        Cell[
          BoxData[
            GridBox[
              makeClickableBoard,
              RowLines->True,
              ColumnLines->True,
              ColumnWidths->1.5,
              RowMinHeight->1.5,
              ColumnsEqual->True
              ]
            ],
          FontFamily->"Sand",
          FontSize->32,
          CellTags->{"TicTacToeBoard"},
          Editable->False,
          Selectable->False,
          CellMargins->{{100,10},{10,10}}  
          (* {left,right},{bottom,top} in "printer's points" *)
          ]
        ];
      ];

Display a message below the tic tac toe board.

displayMessage[message_]:=Module[{nb},
	nb=SelectedNotebook[];
	NotebookFind[nb,"TicTacToeMessage",All,CellTags];
	NotebookWrite[nb,
		Cell[
		 	TextData[Cell[BoxData[FrameBox[message]]]], 
			"Text",
			CellTags->TicTacToeMessage,
			FontFamily->"Comic Sans MS",
			FontSize->24
			]
		];
	];

isWinner returns True or False depending on whether the last move won the game or not.
	(I've written this use a Catch[  ... Throw[ ]] syntax we haven't seen before.  Throw[ ] is like Return[ ], but goes all the way up the Catch[ ].
	And I could have written this as Module[{},Return[Catch[ ... ]]] , but having Catch[ ] on the outside does just as well.)

leftDiagonal := Table[ board[[i,i]],{i,1,3}];
rightDiagonal := Table[ board[[i,4-i]],{i,1,3}];
isWinner:= 
	Catch[
		Do[
			If[ board[[i,All]] == lastPlayersWinningLine, Throw[True]];
        	If[ board[[All,i]] == lastPlayersWinningLine, Throw[True]],
        {i,1,3}];
        If[leftDiagonal  == lastPlayersWinningLine, Throw[True]];
     	If[rightDiagonal == lastPlayersWinningLine, Throw[True]];
		Throw[False]; (* if we haven't found a win *)
	 ];

Return a list of the empty cells where the next next person can move.

getLegalMoves:=Module[{moves={}},
	Do[
		If[ board[[row,column]]==empty,
            (*then*) AppendTo[moves,{row,column}]],
        {row,1,3},{column,1,3}];
    Return[moves];
	];

Return a random legal move in the form {row,column}

randomLegalMove:=Module[{moves=getLegalMoves},
	Return[ moves[[ Random[Integer,{1,Length[moves]}] ]] ];
	];

boardValue returns the value of the current board position.  This is a recursive routine that does the computer's thinking.
As a side effect, it saves the best move found in a global variable, bestMove.
  * If "X" has just moved and won, then the value is  positive, and equal to (10 - number of moves made).  (Winning earlier is better.)
  * If "O" has just moved and won, then the value is negative, ( number of moves made - 10).
  * If 9 moves have been made, and no one has won, then the value is 0.
  * Otherwise, the value is best value (as decided by whose move it is) of the boards you get by making all possible moves on this board.

boardValue:=Module[{moves,moveValues,bestValue,indent},
	nPositionsLookedAt++;
	(* indent = ""; Do[ indent=indent<>" ", {movesMade}]; *)
	(* Print[indent, " finding boardValue of ", board//MatrixForm," movesMade = ", movesMade ]; *)
	If[ isWinner, Return[ -minMaxValue (10-movesMade)]];
	If[ movesMade == 9, Return[0]];
	moves = getLegalMoves;
	(* Print[indent, " legal moves = ", moves]; *)
	moveValues = {};
	Do[
		(* Print[indent," making move ",moves[[m]],"..."]; *)
		doMove[ moves[[m]] ];
		AppendTo[moveValues, boardValue];
		(* Print[indent," finished with move ",moves[[m]]," moveValues is ",moveValues]; *)
		undoMove[ moves[[m]] ];
	, {m,1,Length[moves]}];
	(* Print[ indent, " moveValues = ", moveValues ]; *)
	bestValue = minMaxValue Max[ minMaxValue moveValues];
	(* Print[ indent, " bestValue = ", bestValue]; *)
	bestMove = moves[[ Position[ moveValues, bestValue,1,1 ][[1,1]] ]];  (* save best move as a global *)
	Return[bestValue];
	];

Finally, initialize the game.

init;

the Game

Click on the board to mark an X or O .
Click this button to start a new game :    Reset the game. 
Click this one for the computer's move :  Computer  move.

X' s turn  :  move 1

Scratch Space

init;
Print[" looking at the whole move tree : " ,  
        Timing[boardValue]];
Print[" number of positions examined = ",  
        nPositionsLookedAt];
Print[" total number of distinct boards = ",  
        (3^9)];
Print[" best move is ", bestMove];