Source code for easyAI.AI.NonRecursiveNegamax
"""
The standard AI algorithm of easyAI is Negamax with alpha-beta pruning.
This version does not use recursion. It also does not support transposition
tables, but it does REQUIRE the `tt_entry` method in the game.
It does not make use of 'unmake_move', though having it will not cause a
problem.
It also requires a reverse function: 'ttrestore' that takes the value from
'ttentry' and restores the game state.
"""
LOWERBOUND, EXACT, UPPERBOUND = -1, 0, 1
INF = float('infinity')
# integer keys for 'state':
IMAGE = 0
MOVE_LIST = 1
CURRENT_MOVE = 2
BEST_MOVE = 3
BEST_SCORE = 4
PLAYER = 5
ALPHA = 6
BETA = 7
DOWN = 1
UP = 2
class StateObject(object):
def __init__(self):
self.image = None
self.move_list = []
self.current_move = 0
self.best_move = 0
self.best_score = -INF
self.player = None
self.alpha = -INF
self.beta = INF
def prune(self):
index = self.current_move + 1
self.move_list = self.move_list[0:index]
def out_of_moves(self):
''' we are at or past the end of the move list '''
return self.current_move >= len(self.move_list) - 1
def goto_next_move(self):
self.current_move += 1
return self.move_list[self.current_move]
def swap_alpha_beta(self):
(self.alpha, self.beta) = (self.beta, self.alpha)
class StateList(object):
def __init__(self, target_depth):
self.state_list = [StateObject() for _ in range(target_depth + 2)]
def __getitem__(self, key):
return self.state_list[key + 1]
def negamax_nr(game, target_depth, scoring, alpha=-INF, beta=+INF):
################################################
#
# INITIALIZE AND CHECK ENTRY CONDITIONS
#
################################################
if not hasattr(game, "ttentry"):
raise AttributeError('Method "ttentry()" missing from game.')
if not hasattr(game, "ttrestore"):
raise AttributeError('Method "ttrestore()" missing from game.')
if game.is_over():
score = scoring(game)
game.ai_move = None
return score
if target_depth == 0:
current_game = game.ttentry()
move_list = game.possible_moves()
best_move = None
best_score = -INF
for move in move_list:
game.make_move(move)
score = scoring(game)
if score > best_score:
best_move = copy.copy(move)
best_score = score
game.ttrestore(current_game)
game.ai_move = best_move
return best_score
states = StateList(target_depth)
################################################
#
# START GRAND LOOP
#
################################################
depth = -1 # proto-parent
states[depth].alpha = alpha
states[depth].beta = beta
direction = DOWN
depth = 0
while True:
parent = depth - 1
if direction == DOWN:
if (depth < target_depth) and not game.is_over(): # down, down, we go...
states[depth].image = game.ttentry()
states[depth].move_list = game.possible_moves()
states[depth].best_move = 0
states[depth].best_score = -INF
states[depth].current_move = 0
states[depth].player = game.nplayer
states[depth].alpha = -states[parent].beta # inherit alpha from -beta
states[depth].beta = -states[parent].alpha # inherit beta from -alpha
index = states[depth].current_move
game.make_move(states[depth].move_list[index])
game.switch_player()
direction = DOWN
depth += 1
else: # reached a leaf or the game is over; going back up
leaf_score = -scoring(game)
if leaf_score > states[parent].best_score:
states[parent].best_score = leaf_score
states[parent].best_move = states[parent].current_move
if states[parent].alpha < leaf_score:
states[parent].alpha = leaf_score
direction = UP
depth = parent
continue
elif direction == UP:
prune_time = states[depth].alpha >= states[depth].beta
if states[depth].out_of_moves() or prune_time: # out of moves
bs = -states[depth].best_score
if bs > states[parent].best_score:
states[parent].best_score = bs
states[parent].best_move = states[parent].current_move
if states[parent].alpha < bs:
states[parent].alpha = bs
if depth <= 0:
break # we are done.
direction = UP
depth = parent
continue
# else go down the next branch
game.ttrestore(states[depth].image)
game.nplayer = states[depth].player
next_move = states[depth].goto_next_move()
game.make_move(next_move)
game.switch_player()
direction = DOWN
depth += 1
best_move_index = states[0].best_move
best_move = states[0].move_list[best_move_index]
best_value = states[0].best_score
game.ai_move = best_move
return best_value
[docs]class NonRecursiveNegamax:
"""
This implements Negamax without recursion. The following example shows
how to setup the AI and play a Connect Four game:
>>> from easyAI.games import ConnectFour
>>> from easyAI import NonRecursiveNegamax, Human_Player, AI_Player
>>> scoring = lambda game: -100 if game.lose() else 0
>>> ai_algo = NonRecursiveNegamax(8, scoring) # AI will think 8 turns in advance
>>> game = ConnectFour([Human_Player(), AI_Player(ai_algo)])
>>> game.play()
This algorithm also *REQUIRES* that the game class support the ``ttentry`` and
``ttrestore`` methods.
This algorithm ignores any optional ``unmake_move`` method in the game class.
This version of Negamax does not support transposition tables.
Parameters
-----------
depth:
How many moves in advance should the AI think ?
(2 moves = 1 complete turn)
scoring:
A function f(game)-> score. If no scoring is provided
and the game object has a ``scoring`` method it will be used.
win_score:
Score above which the score means a win.
tt:
A transposition table (a table storing game states and moves). Currently,
this parameter is ignored.
"""
def __init__(self, depth, scoring=None, win_score=+INF, tt=None):
self.scoring = scoring
self.depth = depth
self.tt = tt
self.win_score = win_score
def __call__(self, game):
"""
Returns the AI's best move given the current state of the game.
"""
scoring = self.scoring if self.scoring else (
lambda g: g.scoring()
)
temp = game.copy()
self.alpha = negamax_nr(
temp,
self.depth,
scoring,
-self.win_score,
+self.win_score
)
return temp.ai_move
