Why my minimax algorithm doesn't make the perfect move - 1D Chess?

Question

I'm trying to develop a minimax algorithm to play 1D chess which I'm considering the following: 8 squares aligned, 1 king, 1 knight, and 1 rook. King and rook move in the usual way and the knight moves 2 squares at a time. Additionally, it is a draw if stalemate or it's impossible to make a checkmate (only 2 kings or 2 kings and an additional knight) or 8 moves are made without the number of pieces being reduced.

These are the functions of the game itself.

from copy import deepcopy

# Board -> [list of pieces and non pieces, turn, plays without chagnge number of pieces]
# Piece -> 'K0', 'N1', 'R0', ...

def new_board():
    return [['K0','N0','R0','--','--','R1','N1','K1'], 0, 0]

# Return True if there is any piece on the position index and False otherwise
def pieceQ(board, index):
    return board[0][index][0] in ['K','N','R']

def available_piece(board, piece):
    return piece in board[0]

# Return position of the piece
def piece_index(board, piece):
    if piece in board[0]:
        return board[0].index(piece)
    else:
        return -1

# Return the piece on position index
def index_piece(board, index):
    if pieceQ(board, index):
        return board[0][index]
    else:
        return '--'
    
def print_board(board, code = -1):
    if code == -1:
        print(board[0]) 
    else:
        second_board = deepcopy(board[0])
        second_board[code] = '*'+second_board[code]+'*'
        print(second_board)
        

def available_pieces(board):
    a_pieces = []
    for x in board[0]:
        if x[1]==str(board[1]):
            a_pieces += [x]
    return a_pieces

# Returns the position of the pieces before and after the rook
def min_max_rook(board):
    rook_index = board[0].index('R'+str(board[1]))
    minim = 0
    for i in range(len(board[0][:rook_index])):
        if pieceQ(board, i):
            minim = i
            if index_piece(board, i)[1]==str(board[1]):
                minim+=1
            
    maxim = 7
    for i in range(7, rook_index, -1):
        if pieceQ(board, i):
            maxim = i
            if index_piece(board,i)[1]==str(board[1]):
                maxim-=1
    return (minim, maxim)

def available_moves(board):
    pieces = available_pieces(board)
    moves  = []
    for piece in pieces:
        piece_ind = piece_index(board, piece)
        # Move King
        if piece[0]=='K':
            # Move forward
            if piece_ind<7:
                second_board = deepcopy(board)
                if index_piece(board, piece_ind+1)[1]!=str(board[1]) and index_piece(board, piece_ind+1)[0]!='K':
                    second_board_2 = move(second_board, piece[0], piece_ind+1, free=True)
                    if not check((second_board_2[0],(second_board_2[1]+1)%2)):
                        moves += [(piece[0], piece_ind+1)]
            # Move backwards
            if piece_ind>0:
                second_board = deepcopy(board)
                if index_piece(board, piece_ind-1)[1]!=str(board[1]) and index_piece(board, piece_ind-1)[0]!='K':
                    second_board_2 = move(second_board, piece[0], piece_ind-1, free=True)
                    if not check((second_board_2[0],(second_board_2[1]+1)%2)):
                        moves += [(piece[0], piece_ind-1)]
        # Move Knight        
        elif piece[0]=='N':
            # Move forward
            if piece_ind<6:
                second_board = deepcopy(board)
                if index_piece(board, piece_ind+2)[1]!=str(board[1]) and index_piece(board, piece_ind+2)[0]!='K':
                    second_board_2 = move(second_board, piece[0], piece_ind+2, free=True)
                    if not check((second_board_2[0],(second_board_2[1]+1)%2)):
                        moves += [(piece[0], piece_ind+2)]
            # Move backwards
            if piece_ind>1:
                second_board = deepcopy(board)
                if index_piece(board, piece_ind-2)[1]!=str(board[1]) and index_piece(board, piece_ind-2)[0]!='K':                
                    second_board_2 = move(second_board, piece[0], piece_ind-2, free=True)
                    if not check((second_board_2[0],(second_board_2[1]+1)%2)):
                        moves += [(piece[0], piece_ind-2)]            
        # Move Rook    
        elif piece[0]=='R':
            minim, maxim = min_max_rook(board)
            for i in range(minim, maxim+1):
                second_board = deepcopy(board)
                if i!=piece_ind and index_piece(board, i)[0]!='K':
                    second_board_2 = move(second_board, piece[0], i, free=True)
                    if not check((second_board_2[0],(second_board_2[1]+1)%2)):
                        moves += [(piece[0], i)]
    return moves
                
def move(board, piece, position, free=False):
    if not free and (piece, position) not in available_moves(board):
        print('It is impossible to move '+piece+' to',position)
        raise # IMPOSSIBLE MOVE
        
    elif not available_piece(board, piece+str(board[1])):
        raise #PIECE NOT AVAILABLE

    else:
        n_pieces_old           = len([i for i in range(len(board[0])) if pieceQ(board,i)])
        old_position           = piece_index(board, piece+str(board[1]))
        board[0][old_position] = '--'
        board[0][position]     = piece+str(board[1])
        board[1]               = (board[1]+1)%2
        n_pieces_new           = len([i for i in range(len(board[0])) if pieceQ(board,i)])
        if n_pieces_old==n_pieces_new:
            board[2] += 1
            return [board[0],board[1],board[2]+1]
        else:
            board[2] = 0
            return [board[0],board[1],0]

# Returns True if board is in a check position for player board[1]
def check(board):
    king_index = piece_index(board, 'K'+str(board[1]))    
    if king_index+2 <= 7 and index_piece(board, king_index+2) == 'N'+str((board[1]+1)%2):
        return True        
    elif king_index-2 >= 0 and index_piece(board, king_index-2) == 'N'+str((board[1]+1)%2):
        return True 
    
    else:
        # Check with Rook
        rook_index = piece_index(board,'R'+str((board[1]+1)%2))
        if rook_index != -1:
            if abs(king_index-rook_index)==1:
                return True
            found = False
            for i in range(min(king_index, rook_index)+1, max(king_index, rook_index)):
                found = found or (pieceQ(board, i))
            if not found:
                return True
            
        # Check with king
        king_index_2 = piece_index(board, 'K'+str((board[1]+1)%2))
        if abs(king_index-king_index_2)==1:
            return True   
        else:
            return False             
        
def stalemate(board):
    return (not check(board) and len(available_moves(board))==0) or len([board[0][i] for i in range(len(board[0])) if pieceQ(board, i)])==2 or (len([x for x in board[0] if x[0] in ['K', 'N']])==3 and len([i for i in range(len(board[0])) if pieceQ(board,i)])==3) or board[2]==8
        
def checkmate(board):
    return check(board) and len(available_moves(board))==0

def game_over(board):
    return checkmate(board) or stalemate(board)

def evaluate_board(board):
    if not board[1]:
        # Defeat
        if checkmate(board):
            return -1
        # Victory
        elif checkmate([board[0], (board[1]+1)%2]):
            return 1
        else:
            return 0
    else:
        # Defeat
        if checkmate(board):
            return 1
        # Victory
        elif checkmate([board[0], (board[1]+1)%2]):
            return -1
        else:
            return 0

Here is the minimax algorithm that I have inspired in the Codecademy tic tac toe algorithm. In here I'm guaranteeing that a checkmate move will always happen.

def minimax(input_board, is_maximizing, max_depth=8):
    depth = max_depth-1
    # Base case - the game is over, so we return the value of the board
    if game_over(input_board):
        return [evaluate_board(input_board), ('','')]
    
    # The maximizing player
    elif is_maximizing:
        # The best value starts at the lowest possible value
        best_value = -float("Inf")        
        best_move = ('','')
        
        av_moves = available_moves(input_board)
        if len(av_moves)==1:
            return [best_value, av_moves[0]]
        else:
            for m in av_moves:
                new_board = deepcopy(input_board)
                move(new_board, m[0], m[1])
                if checkmate(new_board):
                    return [best_value, m]
    
            # Loop through all the available moves
            for m in av_moves:
                # Make a copy of the board and apply the move to it
                new_board = deepcopy(input_board)
                move(new_board, m[0], m[1])

                # Recursively find your opponent's best move
                if depth >= 0:
                    hypothetical_value = minimax(new_board, False, depth)[0]
                else:
                    return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]

                # Update best value if you found a better hypothetical value
                if hypothetical_value > best_value:
                    best_value = hypothetical_value
                    best_move = m
                    
            return [best_value, (best_move if best_move != ('','') else m)]
        
    # The minimizing player  
    else:
        # The best value starts at the highest possible value
        best_value = float("Inf")
        best_move = ('','')
        av_moves = available_moves(input_board)
        if len(av_moves)==1:
            return [best_value, av_moves[0]]
        else:
            for m in av_moves:
                new_board = deepcopy(input_board)
                move(new_board, m[0], m[1])
                if checkmate(new_board):
                    return [best_value, m]
            
            # Testing all potential moves
            for m in av_moves:
                # Copying the board and making the move
                new_board = deepcopy(input_board)
                move(new_board, m[0], m[1])
                # Passing the new board back to the maximizing player
                if depth >= 0:
                    hypothetical_value = minimax(new_board, True, depth)[0]
                else:
                    return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]
                # Keeping track of the best value seen so far
                if hypothetical_value < best_value:
                    best_value = hypothetical_value
                    best_move = m      
            return [best_value, (best_move if best_move != ('','') else m)]

(I considered the board with squares from 0 to 7)

The player 0 is the first one to play. The problem is I can beat the algorithm as player 0 with my moves being - N3, N5, R3, K1, N7 - but I can draw as player 1 moving - N4, K6, N2, K5. This is the game where I draw as player 1.

['K0', 'N0', 'R0', '--', '--', 'R1', 'N1', 'K1']

['K0', '--', 'R0', 'N0', '--', 'R1', 'N1', 'K1']

Piece, position: n4 ['K0', '--', 'R0', 'N0', 'N1', 'R1', '--', 'K1']

['K0', '--', 'R0', '--', 'N1', 'N0', '--', 'K1']

Piece, position: k6 ['K0', '--', 'R0', '--', 'N1', 'N0', 'K1', '--']

['--', 'K0', 'R0', '--', 'N1', 'N0', 'K1', '--']

Piece, position: n2 ['--', 'K0', 'N1', '--', '--', 'N0', 'K1', '--']

['--', '--', 'K0', '--', '--', 'N0', 'K1', '--']

I think it should go forward with the rook instead of with the king after my k6.

So that he could eventually draw instead of losing. Hope you can help me.

Thank you!

Answer 1

The problem was that the way I was using depth doesn't work. It should be at the beginning (in the base case). I think the problem is solved.