April 10, 2010
Tutorial: Tic Tac Toe
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 :)
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.
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.
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.