|
3-D Tic Tac Toe description:
3-D Tic Tac Toe is played on 4 4x4 boards (64 total squares) and the game is won when a player gets 4 pieces in a row along horizontal, vertical, or diagonal directions. The game uses OpenGL to allow the board to be rotated and viewed from different angles. This program is licensed under the GNU General Public License (GPL).
Background:
The algorithms and all of the code behind the actual 3-D tic-tac-toe engine were developed by John Davin and Terrence Wong as a final project for the course Artificial Intelligence, at Carnegie Mellon University.
The main algorithm is a Minimax search with alpha beta pruning to locate the best move. The evaluation function is relatively simple, but appears to work well. The only way to win a 3-D tic tac toe game against a good player is to fork him/her (create a situation where you can put a piece in either of two places, both of which would create a win). The evaluation function that we created promotes attaining forks.
The other significant design that we used was to invent a representation of the board that would allow us to more quickly calculate when there is a winning position. The most obvious way to represent a board with 64 squares would be to use an array of 64 with each member representing a square. However, we used a char for each possible row in which a player could win. This way, we can just run through the array of possible win rows and check if it is equal to the value of a winning row.
|