Code vs Output

This was one of my projects I’ve completed for an AI class I took during my college term. The project goal is to implement an AI game using one of the key algorithms we learned, Alpha-beta pruning. The game idea is simple: The player is to play against an AI. The win factor is that the player should have 4 pieces consecutively in a row or column. The programming language used was  Python 3.1.


What is Alpha-beta pruning?

Read an clear explanation on Wikipedia, our implementation follows it directly. Here is the implementation for my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def alphabeta(problem, alpha, beta, MaxPlayer, limit):
	global starttime
	if (time.clock() - starttime) >= limit or problem[0].isfull(): return problem
	if MaxPlayer: return maxstate(problem[0], alpha, beta, MaxPlayer)
	else: return minstate(problem[0], alpha, beta, MaxPlayer)
 
def maxstate(problem, alpha, beta, MaxPlayer):
	for child in problem.getsuccessors('X'):
		clone = copy.deepcopy(problem)
		clone.move(child[1][0], child[1][1], 'X')
		node = (clone, child[1])
		alpha = max(alpha, alphabeta(node, alpha, beta, not MaxPlayer, limit))
		if beta[0].h <= alpha[0].h: break;
	return alpha
 
def minstate(problem, alpha, beta, MaxPlayer):
	for child in problem.getsuccessors('O'):
		clone = copy.deepcopy(problem)
		clone.move(child[1][0], child[1][1], 'O')
		node = (clone, child[1])
		beta = min(beta, alphabeta(node, alpha, beta, not MaxPlayer, limit))
		if beta[0].h <= alpha[0].h: break;
	return beta

How the AI chooses the best possible move:

I will give a very general explanation. Please read the Wikipedia link for a elaborate explanation.

1.) Given an player’s move, the AI will generate a minimax tree till the search limit time is reached. In other words: Predict player’s next move and then find my best move. Iterate this n-levels deep.

2.) For each move the AI predicts, give it an score. The evaluation function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def getsum(self, string):
	sum = 0
	superbad = -5000
	bad1 = -100
	bad2 = -75
	bad3 = -50
	bad4 = -25
	bad5 = -1
	supergood = 5000
	good1 = 100
	good2 = 75
	good3 = 50
	good4 = 25
	good5 = 1
	#opponent
	if 'OOOO' in string: sum += superbad
	if '-OOO-' in string: sum += bad1
	if 'OOO-' in string: sum += bad1
	if '-OOO' in string: sum += bad1
	if 'OO-O' in string: sum += bad2
	if 'O-OO' in string: sum += bad2
	if 'O-OO-' in string: sum += bad2
	if '-OO-O' in string: sum += bad2
	if '-O-OO' in string: sum += bad2
	if 'OO-O-' in string: sum += bad2
	if '-OO-' in string: sum += bad2
	if '-OO' in string: sum += bad3
	if 'OO-' in string: sum += bad3
	if 'O-O-' in string: sum += bad4
	if '-O-O' in string: sum += bad4
	if '-O-O-' in string: sum += bad2
	if 'O-O' in string: sum += bad5
	if 'OO' in string: sum += bad5
	if '-O-' in string: sum += bad5
        .....

3.) The AI will consider all the player’s moves that are against itself and find its worse case.

4.) The AI evaluates itself to find it’s best move to counter the player’s move.

Disadvantage:

Our Design: Too many combinations of player’s moves to evaluate, therefore AI may not make the best move in our consideration.

Strength:

Python’s fast sorting. Alpha-beta pruning which cuts off any worse-off moves from consideration.

Try it out!

An python installation is required. Please make sure you have already installed on your computer, Python 3.1+.

connect4.py [Download]

Download the above file and open it. Enter an time you want the AI to search for an solution. For example, enter 5 for 5 seconds.