The Friday Fragment

Published on 6 November 2010
This post thumbnail

It's Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week's Fragment

We'll continue in our tic-tac-toe "game bot" vein with the next step:

Write code to score the results of calling two tic-tac-toe web services playing each other. Check for wins, ties, and illegal moves.

To “play along,” provide either the URL or the code for the solution. You can post it as a comment or send it via email. If you’d like, you can build atop results from our last Friday Fragment.

Last Week's Fragment - Solution

Last week's puzzle was a tic-tac-toe "bot":

Code a simple REST web service to play tic-tac-toe. It should accept a nine-character string representing the current "game board" with space, X, or O in each position (starting from the top left, going left-to-right and down). It should return a nine-character string with your next move added.

Here's my Q&D, brute-force solution in PHP, with room for improvement. I added vertical bar wrappers to preserve spaces on the GET request, so pass it ?board=|         | to start.


   if (!ereg('^\|{1}[XO ]{9}\|{1}$', $board=$_REQUEST['board']))
   $board = substr($board, 1, 9);
   $mypiece = (substr_count($board, ' ') & 1) ? 'X' : 'O';

   // The best move is with two plays and one space to win or block.
   // The rest is not much better than random.
   for ($plays=2; $plays>=0; $plays--)
     for ($spaces=1; $spaces<4-$plays; $spaces++)
       if (!is_null($result = find_move($board, $mypiece, $spaces, $plays)))


   function find_move($board, $piece, $spaces, $plays) {

     $wins = array( array(0,1,2), array(3,4,5), array(6,7,8),
                    array(0,3,6), array(1,4,7), array(2,5,8),
                    array(0,4,8), array(2,4,6) );

     for ($i=0; $i<8; $i++) {
       for ($j=0, $mycount=0, $spacecount=0; $j<3; $j++) {
         if ($board[$win[$j]] == $piece)
         elseif ($board[$win[$j]] == ' ') {
           $spaceplace = $j;
       $opponentcount = 3 - $mycount - $spacecount;

       if ($spacecount == $spaces) {
         if ($mycount == $plays) {              // win
           $board[$win[$spaceplace]] = $piece;
           return $board;
         } elseif ($opponentcount == $plays) {  // block
           $board[$win[$spaceplace]] = $piece;
           return $board;
     return null;

Can you write a tic-tac-toe bot that'll beat it?