find best move using alphabeta TicTacToe

Question

Trying to find the best move as well as the score. I have gotten my program to correctly return the score of the game, but I want it to return the move as well. How can I change my code so that it does this? Similar to this and this. See my failed code here, the None returned if the game is over should be the move instead.

def alphabeta(game_state, alpha, beta, our_turn=True):
    if game_state.is_gameover():
         return game_state.score()
    if our_turn:
        score = -9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, True)
            temp_max = alphabeta(child, alpha, beta, False) 
            if temp_max > score:
                score = temp_max
            alpha = max(alpha, score)
            if beta <= alpha:
                break
        return score
    else:
        score = 9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, False)
            temp_min = alphabeta(child, alpha, beta, True)
            if temp_min < score:
                score = temp_min
            beta = min(beta, score)
            if beta <= alpha:
                break
        return score

Holy shnikes, you are me 15 years ago. Developing an unbeatable Tic Tac Toe game was my gateway drug into programming. I seem to remember a fantastic tree of unreadable if..then statements that I never quite got working. It was my first lesson into the importance of readable code. EDIT: Oh wait, alpha-beta-pruning? Never mind, you are way ahead of where I was. — CivFan, Dec 12 '16 at 23:28

Julien · Accepted Answer · 2016-12-12T23:35:19.873

2

You could keep track of best move so far, something like:

    if game_state.is_gameover():
         return game_state.score(), None
    if our_turn:
        score = -9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, True)
            temp_max, _ = alphabeta(child, alpha, beta, False) # _ to disregard the returned move
            if temp_max > score:
                score = temp_max
                best_move = move
            alpha = max(alpha, score)
            if beta <= alpha:
                break
        return score, best_move

and similar for other case

edited Dec 12 '16 at 23:35

answered Dec 12 '16 at 23:24

Julien

13,986
5
29
53

Yes, but then when I want to return the score, best_move pair if `game_state.is_gameover()`, it isn't defined yet. – PAS Dec 12 '16 at 23:25
Defined as `None` – Julien Dec 12 '16 at 23:26

find best move using alphabeta TicTacToe

1 Answers1