Michael J. Swart

January 18, 2010

Tic Tac Toe vs. T-SQL

Filed under: SQLServerPedia Syndication,Tongue In Cheek — Michael J. Swart @ 11:50 pm

It's learning

It's learning

Stephen Horne (aka BlueDog67) threw down the challenge last week to Create An Unbeatable Tic-Tac-Toe Game. He did that in this post.

So that’s what I did. Here’s my crack at it (which I also left as a comment):

The curious can download http://michaeljswart.com/wp-content/uploads/2010/01/tictactoe.zip

The zipped file contains two files:

  • One is a bcp output file that contains data. (It is used by the script)
  • The other is a sql script that creates the following tables and procedures:
    • TABLE tttBoard (spaceId, value)
    • TABLE tttMoves(id, turn, bestNextMove)
    • PROCEDURE s_CleanBoard()
    • PROCEDURE s_PrintBoard()
    • PROCEDURE s_MakeMove(@spaceId, @letter)
    • PROCEDURE s_ComputerMove

I decided to use a look up table (tttMoves) to find the best move. I thought it fitting to develop a solution that uses a set of data rather than an algorithm because of it is T-SQL after all. Here are three things I learned.

  • The size of tttMoves is extremely small. Roughly 4500. Think about it. If you take nine ordered spaces on a tic-tac-toe board and put every combination of X, O, or space, there’s still a manageable number of boards to deal with. I removed completed boards and boards showing games that were invalid. 4500 were left. Of these game boards, only about 400 were more complicated than a simple win or a block for their best move.
  • The whole process was a lot quicker than it took the eighties super-computer to learn tic tac toe in WarGames. (Who remembers that? To this day, joshua is a terrible password)
  • A T-SQL tip: This should have been obvious but remember that order of columns in a table matters when using BULK INSERT with a data file using native formatting.

1 Comment »

  1. Thank you sir! Very interesting analysis and solution. I really need to finish my attempt at a solution.

    “Would you like to play a game?” I hear they may do a remake of WarGames – not sure what I think about that!

    Comment by Stephen Horne — January 19, 2010 @ 12:01 am

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress