davidbau.com Tutorial: Tic Tac Toe

Tutorial: Tic Tac Toe

Continuing with the javascript tutorials - tic-tac-toe.html (view source) is an example of a bare-bones board game AI.

It uses recursion to fully explore the tic-tac-toe tree and play a perfect game against you. The code is short, but I am concerned it is probably too difficult for kids to understand. The other problem is that (at least on my laptop) IE is too slow to run the AI on move #1 without a "script appears hung" warning.

Nevertheless, "how to program Tic-Tac-Toe" is an extremely common request from the kids, so it goes into the pile of examples.

Let me know if you come up with a way of simplifying the code.

Posted by David at April 10, 2010 11:56 AM

You could add some simple alpha beta pruning to make it faster, though that'll likely make it yet trickier to understand for kids :)

Posted by: David Ebbo at April 12, 2010 11:07 AM

Instead, I've just added a "depth" to limit the depth of the search. Reducing the depth by one level, to seven steps ahead, seems to speed things up enough for IE.

Posted by: David at April 13, 2010 11:22 AM

A cleverly coded game, but the computer will not make a winning move. It only seems intent on blocking.

What level of student are you aiming this at? I think it's way too hard for most.

Have you looked at a more graphical enviroment like Scratch? I use it to teach my 13 and 14 year old students. They love it.

Regards

Peter.

Peter

Posted by: Peter at September 27, 2010 06:27 AM

Scratch is a great introduction: my 12 year old son uses it for programming a lot of games. My main problem with it is that its lack of functions prevents you from writing interesting algorithms like the AI in "tic tac toe".

I am aiming "tic tac toe" at motivated middle-schoolers who already know how to program and who want to answer the question "how can computers think?" Understanding the program is hard, but I think it can be made understandable to a middle-schooler if it is taught. Recursion is easier to learn when you're young.

Posted by: David at October 24, 2010 10:57 AM