Tuesday, July 31, 2007

Simple Tic-Tac-Toe AI in JavaScript

Click here to see the Tic-Tac-Toe game in action! (open in new window)

Last year, I was challenged by the thread at Thaiadmin to implement a two-player OX (or Tic-Tac-Toe, XO, what you may call) game. I had done this kind of program in VB6 before, so I decided to implement the one-player JavaScript version.

The hardest part of of this project is debugging the JavaScript. I had to write the value of each variable and things done in each step to the screen (as you see in the bottom of the figure above) to diagnose the problems. I was so embarrassed that I did not know any of the great web developer's tools such as FireBug.

The ideas behind the decisions making part (or the AI) are to search every possible moves and take the best one. In each move, We assumed that the opponent chose his best move and we chose our best move. This method is "Minimax" method. As described in Wikipedia:

Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. Alternatively, it can be thought of as maximizing the minimum gain (maximin). It started from two player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves. It has also been extended to more complex games and to general decision making in the presence of uncertainty.

The Minimax method can be applied to many other board games too. But in some complex games such as Chess, there was so many game states that you cannot search into them entirely (it would take many many years on an ordinary computer). So some heuristic must be used to approximately determine value of each state and the search must be limited at a fixed level (deeper level of search makes the AI cleverer).

In my case, there was not too many game states so I can search on them entirely. You can test my game here - http://m3rlinez.googlepages.com/oxai.htm. Choose View->Source to view the JavaScript source code.

7 comments:

~inSiderboy said...

It's cool.I'm weak spot it. - -''

Marios - Greece said...

Nice Job.

Paul said...
This comment has been removed by a blog administrator.
ระบบ no hdd harddiskless said...

Good job. I follow your blog from Thaiadmin too.

Anonymous said...

the AI isnt too bad but:
1.you should use css
2.dont share id's
3.dont pass row,col in onclick you can put that in the id and refer to it with sender.id


Natthawut Kulnirundorn said...

Thanks. This was written in 2007 when good JavaScript practices and CSS weren't cool yet :)

adam estes said...

This AI is terrible. At multiple points it tends to play at a place that gives zero possible chance to win.

For example. If you play the top right, then the bottom right, and then the middle left, the ai will play the top right even though it is already blocked.