NetLogo User Community Models
by Bertram Zinner (Submitted: 08/18/2004)
WHAT IS IT?
This is the familiar Tic Tac Toe game programmed in NetLogo where you can play against the computer.
HOW IT WORKS
The program collects all possible Tic Tac Toe positions in a list and then rearranges the list by the number of moves that have been made. There are at most 9 moves possible in a game. After 9 moves it is easy to determine who won or whether or not it was a tie. The program then partitions all positions of length k, k=1,2,...,8 (that is k moves have been made) into three lists: a list of winning positions, a list of loosing positions, and a list of tie positions. The list of winning positions of length k consists of all positions of length k where the player whose move it is next can force a win. The list of loosing positions of length k consists of all positions of length k where the player whose move it is next either lost with the k-th move or the other player can force a win. If such a partitioning has been established for positions of length k then it can be established for positions of length k-1 as follows. The program assigns each position of length k-1 to the winning, loosing or tie list depending on what happens with every possible next move. Note that for each given position there are only a few possible next moves. The program proceeds inductively working its way from k=8 to k=1.
After all positions have been partitioned into winning, loosing, and tie, the game can begin. The computer first checks if there is a winning move. If there is none, it picks a tie move. This is only possible because the lists of tie moves of length 1 and length 2 are not empty. Since the list of winning moves of length 1 is empty, neither the first nor the second player can force a win.
HOW TO USE IT
First click on the setup-game button. This may take a while, but you only have to do it once. Next click on the play-game button. If the switch "computer-first?" is on then the computer will make the first move. Otherwise the computer waits for your move. In order to make a move simply click on the playing field of your choice. You need to give the computer about 1 second to make a move, otherwise you may encounter an error.
THINGS TO NOTICE
The computer never looses.
CREDITS AND REFERENCES
This program was written by Bertram Zinner, 2004.
(back to the NetLogo User Community Models)