Friday, June 22, 2007

Tic-Tac-Toe

After reading this java.net article on making a nim playing computer program, I attempted to make a tic-tac-toe playing one in Python. This exercise also served as a refresher for my old AI mini-max lessons (although it would be difficult for me to forget the person who taught me).
I'm unable to reproduce the full code here due to space reasons.

class Node:
def computeMiniMax(self):
if len(self.children) == 0:
winner = self.board.getWinPos()
if winner == 'X': self.score = 1
elif winner == 'O': self.score = -1
else: self.score = 0
else:
for child in self.children:
child.computeMiniMax()
if self.player == 'X':
self.score = max([node.score for node in self.children])
else:
self.score = min([node.score for node in self.children])


Here's where I build the game tree:


def buildGameTree(self):

winner = self.board.getWinPos()
if winner == 'X' or winner == 'O' :
return

if self.player == 'X':
newplayer = 'O'
else:
newplayer = 'X'

for i in range(3):
for j in range(3):
char = self.board.getcell(i,j)
if char == '.':
newboard = self.board.clone()
newboard.setcell(i, j, self.player)
node = Node(newboard, newplayer)
self.children.append(node)
node.buildGameTree()

Here is a sample run:

Who plays first? (1=computer 2=human)2
.|.|.
.|.|.
.|.|.
Your choice:1,0
Building game tree...
Done..
Computing node scores...
Done..
X|.|.
O|.|.
.|.|.
Your choice:1,1
X|.|.
O|O|X
.|.|.
Your choice:0,2
X|.|O
O|O|X
X|.|.
Your choice:2,2
X|X|O
O|O|X
X|.|O
Your choice:2,1
X|X|O
O|O|X
X|O|O
It is a draw !

0 comments: