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.

8 comments:

rchatsiri said...

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

Marios - Greece said...

Nice Job.

Anonymous 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


Unknown said...

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

Unknown 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.

Emma Customer Service said...

Showcase your best experiences via Emma Customer Service Number. Emma is an easy to use platform which provides support for large-scale enterprise as well as email marketing solutions for businesses, organizations, and agencies around the world. In addition, Emma enables businesses to create and send promotions/invitations, welcomes trigger emails, tailors each message to the right audience, organizes contacts, connects with customers using free surveys and forms, sees who opens, clicks and shares campaigns on social networks. Since Emma comprises of attractive features but also faces technical issues sometimes. If you want to remove all tech glitches, just call at Emma Customer Service which will definitely help your account to properly set up. Contact technical customer services if you have any questions. Our experts and professionals are always ready to sort out each issue without any delay.