Tuesday, June 28, 2011

Computer Opponent: Noughts & Crosses

The next task on my list for making a strategy game is writing a computer opponent. In the tutorial I describe how I’ve used variations on the minimax algorithm to play noughts and crosses (tic-tac-toe). I chose noughts and crosses because it’s finite (always ends in 5-9 moves) and simple, yet there are thousands of different solutions. Eventually, I plan on using a minimax type algorithm for a game which will use the hex board tutorial I created in Unity earlier.

The C# source code for this project is available here.
The tutorial is available here.

The end result of this project is a console application that plays noughts and crosses with itself. It cycles through games using negamax, alpha-beta pruning and negascout. Every game is, of course, a draw. (You may notice that negascout is slower than alpha-beta pruning. This is because I haven’t ordered the search tree, it’s such a simple game that it isn’t worth it.) There is also a test project that runs a number of tests to make sure that the algorithms are doing what I expect them to do.

No comments:

Post a Comment