Depth never reaching 0 in depth-limited minimax algorithm

Question

I have been trying to code an AI for a traditional Turkish game "3 Stones" ("3 Taş" in Turkish), a variant of Three Men's Morris.

Background: The game

The game is played as follows. The first player has 3 white stones and the second player has 3 black stones. In a first phase, players take turns to place once of their stones on the board, until they are all placed on the board. In a second phase, players move each turn one of their stones one step along a line of the board to an adjacent, free spot. The player that can move all their three stones in one connected line (vertical or horizontal) wins the game.

My approach

I implemented the minimax algorithm using Python.

The game is not necessarily finite (moves can keep repeating), so instead of using the normal minimax, I chose to make it depth limited.

The code is shown below.

import copy
import math

board=[["_","_","_"],
       ["_","_","_"],
        ["_","_","_"]]
turn="b"
black_stones=[]
white_stones=[]
win=""


def print_board():
    print(board[0])
    print(board[1])
    print(board[2])

def is_move_possible(move):
    if(len(black_stones)<3):
        if(board[int(move[0]) - 1][int(move[1]) - 1]=="_"):
            return True
        return False
def is_move_possible_after(piece,move,turn,board):


    if (abs(int(move[0])-int(piece[0]))==1 or abs(int(move[1])-int(piece[1]))==1) and not(abs(int(move[0])-int(piece[0]))==1 and abs(int(move[1])-int(piece[1]))==1):
        if(board[int(move[0]) - 1][int(move[1]) - 1]=="_") and (board[int(piece[0]) - 1][int(piece[1]) - 1]==turn):
            return True
    return False

def move_once():
    global last_move
    global turn
    global board
    if (turn == "b"):
        move = input("Move:")
        if not (is_move_possible(move)):
            return move_once()
        board[int(move[0]) - 1][int(move[1]) - 1] = turn

        white_stones.append([int(move[0])-1,int(move[1])-1])
        last_move=move
        turn="s"
    elif (turn == "s"):
        move=minimax(board,3)
        board[int(move[0])][int(move[1])] = turn
        black_stones.append([int(move[0]), int(move[1])])
        turn = "b"
def move_sonra():

    global board
    global turn


    if turn=="b":
        piece = input("piece:")
        move = input("move:")
        if not(is_move_possible_after(piece,move,turn,board)):
            return move_sonra()

        board[int(piece[0])-1][int(piece[1])-1],board[int(move[0])-1][int(move[1])-1]=board[int(move[0])-1][int(move[1])-1],board[int(piece[0])-1][int(piece[1])-1]


        turn="s"


    elif (turn=="s"):
        aimove=minimax(board,3)
        piece=aimove[0]
        move=aimove[1]








        board[int(piece[0])][int(piece[1])], board[int(move[0])][int(move[1])] = board[int(move[0])][int(move[1])], board[int(piece[0])][int(piece[1])]

        turn="b"
def winner(board):


    columns=[[board[0][0],board[1][0],board[2][0]],[board[0][1],board[1][1],board[2][1]],[board[0][2],board[1][2],board[2][2]]]
    for i in columns:
        if i==["b","b","b"]:
            win="b"
            return win
        elif i==["s","s","s"]:
            win="s"
            return win
    for i in board:
        if i==["b","b","b"]:
            win="b"
            return win
        elif i==["s","s","s"]:
            win="s"
            return win
    if(len(white_stones)+len(black_stones)==9):
        win="="
        return win
    return False


def is_finished(board):
    columns = [[board[0][0], board[1][0], board[2][0]], [board[0][1], board[1][1], board[2][1]],
               [board[0][2], board[1][2], board[2][2]]]
    for i in columns:
        if i == ["b", "b", "b"]:

            return True
        elif i == ["s", "s", "s"]:

            return True
    for i in board:
        if i == ["b", "b", "b"]:

            return True
        elif i == ["s", "s", "s"]:

            return True

    return False
def actions_before(board):
    moves=[]
    for i in range(0,len(board)):
        for j in range(0,len(board[i])):
            if(board[i][j]=="_"):
                moves.append([i,j])
    return moves
def actions_after(board,turn):

    moves=[]
    beyaz_pullar2 = []
    for i in range(0, len(board)):
        for j in range(0, len(board[i])):
            if (board[i][j] == "b"):
                beyaz_pullar2.append([i, j])


    if(turn=="b"):
        for piece in beyaz_pullar2:
            for move in actions_before(board):




                if(is_move_possible_after([piece[0]+1,piece[1]+1],[move[0]+1,move[1]+1],"b",board)):

                    moves.append([piece,move])
    elif(turn=="s"):
        siyah_pullar2=[]
        for i in range(0,len(board)):
            for j in range(0,len(board[i])):
                if(board[i][j]=="s"):

                    siyah_pullar2.append((i,j))


        for piece in siyah_pullar2:
            for move in actions_before(board):

                if(is_move_possible_after([piece[0]+1,piece[1]+1],[move[0]+1,move[1]+1],turn,board)):
                    moves.append([piece,move])
    return moves
def player(board):


      b_count = 0
      s_count = 0
      for row in board:

          for cell in row:
              if (cell == "b"):
                  b_count += 1
              if (cell == "s"):
                  s_count += 1

      if (b_count == s_count):
          return "b"
      return "s"
def result_before(board,move):
    copyboard=copy.deepcopy(board)
    copyboard[move[0]][move[1]]=player(board)
    return copyboard
def result_after(board,move):
    copyboard=copy.deepcopy(board)
    piece=move[0]
    place=move[1]
    copyboard[piece[0]][piece[1]],copyboard[place[0]][place[1]]=copyboard[place[0]][place[1]],copyboard[piece[0]][piece[1]]
    return copyboard
def utility(board):
    if((winner(board)=="s")):
        return 100
    elif(winner(board)=="b"):
        return -100
    else:
        return 0
def eval(board,depth,turn):
    print("Depth:",depth)


    black_stones = []
    for i in range(0, len(board)):
        for j in range(0, len(board[i])):
            if (board[i][j] == "s"):
                black_stones.append((i, j))


    if(is_finished(board)):

        return utility(board)
    elif(depth<=0):

        return 0





    elif(len(black_stones)<3):
        if(turn=="s"):
            v=-math.inf
            for move in actions_before(board):
                black_stones.append(move)


                score=eval(result_before(board,move),depth-1,"b")

                v=max(v,score)
                black_stones.pop(-1)


            print("girdi")
            return v
        elif (turn == "b"):
            v = math.inf
            for move in actions_before(board):




                score= eval(result_before(board,move),depth-1,"s")

                v = min(v,score )

            return v

    else:




        if (turn == "s"):



            v = -math.inf
            actions=actions_after(board,turn)


            for move in actions:

                score=eval(result_after(board,move),depth-1,"b")

                v = max(v, score)




            return v
        elif (turn== "b"):


            v = math.inf
            actions=actions_after(board,turn)

            for move in actions:


                score = eval(result_after(board, move), depth-1, "s")

                v = min(v, score)
          

            return v
def minimax(board,depth):

    if(len(black_stones)<3):
        if (player(board) == "s"):
            v = -math.inf
            best_move=actions_before(board)[0]

            for move in actions_before(board):
                black_stones.append(move)

                score=eval(result_before(board,move),depth-1,"b")

                if(score>v):
                    v=score
                    best_move=move
                black_stones.pop(-1)

            return best_move
    else:
        if (player(board) == "s"):
            v = -math.inf
            actions=actions_after(board)
            best_move=actions[0]
            for move in actions:
                score=eval(result_after(board, move),depth-1,"b")

                if(score>v):
                    v=score
                    best_move=move



            return best_move


while True:
    if(len(black_stones)<3):
        move_once()
        print_board()

    else:
        print_board()

        move_sonra()
        print_board()

    if(is_finished(board))==True:
        break

if(winner(board)=="s"):
    print("KAZANAN SİYAH")
elif(winner(board)=="b"):
    print("KAZANAN BEYAZ")

Problem

In the evaluation function the depth sometimes never reaches 0. Yet I always decrease the depth by 1 when doing recursion... So the value returned from the evaluation can sometimes be None which causes errors.

I believe the problem is in the function eval, which is the function for evaluation.

This is the output or error I get:

How can I fix this?

Answer 1

The problem is that your player function does not give the correct result once both players have placed their three discs on the board. From that moment onwards, player will always return "b" even when that player had last moved. In essence, in the second phase of the game you cannot know from the number of discs on the board whose turn it is, because there will continually be three black and three white discs, no matter whose turn it is.

And although minimax is called after having ensured it is the turn of "s", with this code:

    elif (turn == "s"):
        move=minimax(board,3)

...minimax will call player(board) to determine itself whose turn it is and get "b" in the above described situation. minimax has no code to execute when the player is "b" and silently returns None which is the cause of the problem.

In short, you need to revise your code so that either the player() function has the tools to really determine whose turn it is, or you have to omit this function and instead ensure that the turn variable correctly reflects whose turn it is, also when performing the minimax search.

Other remarks

There is a lot to wish for in this code:

• To avoid to have to recalculate whose turn it is, and how many stones have been played, don't copy the board when performing the minimax search. Instead use the current board, and after recursion, undo the move on that board. That way your variables, including turn, fully describe the state the board is in that is being evaluated.
• Avoid casting move[0] to int every time and do this conversion immediately and permanently after the user input has been received
• Avoid this +1 and -1 that appears everywhere in your code to switch between 0-based and 1-based indexing, and use 0-indexing everywhere (convert the user's 1-based input immediately)
• Format your code with blank lines between functions, but not randomly between code lines
• Don't put if conditions in parentheses
• Use else instead of elif if there are no other cases possible (for instance turn can only have two values, so if it isn't the one, we don't have to test it is the other).
• Don't compare a boolean with True, testing the boolean is enough. So not if is_finished(board) == True:, but if is_finished(board):
• Make use of tuple assignment. So instead of piece = aimove[0]; move = aimove[1] do piece, move = aimove
• As your code does not mutate moves, don't do [move[0], move[1]] but just move. And even if you need to pass a copy, then just do move[:]
• last_move serves no purpose. Remove it.
• win should not have to be a global variable. It can be defined locally where needed. Remove it.
• white_stones and black_stones are only used to know their lengths, not for their contents. Moreover, you can derive these lengths from the number of moves played so far. So just work with a num_played_moves or something similar.
• It is a bit inconsistent that you define board and turn as globals, but then pass them as argument to is_move_possible_after. Same thing with some other functions.
• Don't use the global keyword if your function is not assigning to that variable. For instance, global board is not needed when you don't have board = in your code. But:
• Avoid global variables and instead work with a class where these state variables are instance attributes (like self.turn).
• is_move_possible has a case where it returns None. Make sure it always returns a boolean. This is also the case in a few other functions.
• minimax currently is only designed to work for player "s", but it requires little effort to generalise it so it can work for both players, and this way you also avoid that None return that was the cause of your initial problem.
• The condition len(white_stones) + len(black_stones) == 9 could never be true as there are only 6 pieces in the game.
• is_finished repeats code from winner: avoid this code repetition.
• The distinction made between moves-before and moves-after is not helping to make your code generic and elegant. It means that everywhere in your code you have to make this distinction. Reduce this distinction and design one type of move that covers all. For instance, it could be the piece + move design, but where piece is None when the move represents adding a new piece on the board.
• To avoid code duplication in eval and minimax, merge them and have them return a tuple of score and best move. The caller can then select the part they are interested in.

Here is the code that is heavily adapted with the above remarks:

class ThreeMenMorris:
    def __init__(self):
        self.board = [["_", "_", "_"], 
                      ["_", "_", "_"], 
                      ["_", "_", "_"]]
        self.turn = "b"
        self.num_played_moves = 0

    def __repr__(self):
        return "\n".join(map(repr, self.board))
        
    def is_move_possible(self, piece, move):
        return (
            # Must place new stone on board in first 6 plies, and must not do that in other moves
            (not piece) == (self.num_played_moves < 6) and
            # Target field must be free
            self.board[move[0]][move[1]] == "_" and 
            # Either a new piece or a move with taxicab distance of 1 with a piece of own color
            not piece or (abs(move[0]-piece[0]) + abs(move[1]-piece[1]) == 1 and 
                          self.board[piece[0]][piece[1]] == self.turn)
        )
        
    def play_move(self, piece, move):
        self.board[move[0]][move[1]] = self.turn
        if piece:
            self.board[piece[0]][piece[1]] = "_"
        self.num_played_moves += 1
        self.turn = "b" if self.turn == "s" else "s"

    def undo_move(self, piece, move):
        self.turn = "b" if self.turn == "s" else "s"
        self.num_played_moves -= 1
        if piece:
            self.board[piece[0]][piece[1]] = self.turn
        self.board[move[0]][move[1]] = "_"

    def winner(self):
        columns = [[self.board[0][0], self.board[1][0], self.board[2][0]], 
                   [self.board[0][1], self.board[1][1], self.board[2][1]], 
                   [self.board[0][2], self.board[1][2], self.board[2][2]]]
        for lines in (columns, self.board):
            for line in lines:
                if "".join(line) in ("bbb", "sss"):
                    return line[0]
        return False

    def actions(self):
        moves = []
        for i, row in enumerate(self.board):
            for j, content in enumerate(row):
                if content == "_":
                    moves.append((None, (i, j)))  # Always include piece
        if self.num_played_moves >= 6:
            targets = moves
            moves = []
            for i, row in enumerate(self.board):
                for j, content in enumerate(row):
                    if content == self.turn:
                        piece = (i, j)
                        for _, move in targets:
                            if self.is_move_possible(piece, move):
                                moves.append((piece, move))
        return moves

    def utility(self):
        win = self.winner()
        if win == "s":
            return 100
        if win == "b":
            return -100
        return 0

    def minimax(self, depth):
        best_move = None
        best_score = self.utility()
        if best_score == 0 and depth > 0:
            optimal = (min, max)[self.turn == "s"]  # Choose min or max as optimalisation function
            best_score = -optimal(-float("inf"), float("inf"))
            for piece, move in self.actions():
                self.play_move(piece, move)
                score = self.minimax(depth - 1)[0]  # extract score
                if optimal(best_score, score) != best_score:
                    best_score = score
                    best_move = (piece, move)
                self.undo_move(piece, move)
        return best_score, best_move  # return both the score and the move


def get_input(prompt):
    while True:  # Don't use recursion to get user input until it is valid
        move = input(prompt)
        if len(move) == 2 and move[0] in "123" and move[1] in "123":
            return [int(x) - 1 for x in move]  # immediately convert to zero-based int
        print("Invalid format. Type two digits, each between 1 and 3.")

def main():
    DEPTH = 2
    game = ThreeMenMorris()
    print(game)
    winner = False
    while not winner:
        if game.turn == "b":
            while True:
                piece = None
                if game.num_played_moves >= 6: 
                    piece = get_input("Piece:")
                move = get_input("Move:")
                if game.is_move_possible(piece, move):
                    break
                print("Invalid move. Retry:")
        else:
            piece, move = game.minimax(DEPTH)[1]  # Extract the move
            print("AI has moved:")
        game.play_move(piece, move)
        print(game)
        winner = game.winner()

    print(("Black wins", "White wins")[winner == "b"])

main()