turn this to expectiminimax. def minimax(state, depth, a, b, is_maximizer):
    if depth == 0:
        return evaluate_state(state), state

    if is_maximizer:
        best_score = float('-inf')
        best_state = None
        for child_state in get_possible_moves(state, depth):
            score, _ = minimax(child_state, depth - 1, a, b, False)
            if score > best_score:
                best_score = score
                best_state = child_state
            if best_score > b:
                break
            a = max(a, best_score)
        return best_score, best_state
    else:
        best_score = float('inf')
        best_state = None
        for child_state in get_possible_moves(state, depth):
            if depth % 3 == 0:
                score, _ = minimax(child_state, depth - 1, a, b, True)
            else:
                score, _ = minimax(child_state, depth - 1, a, b, False)
            if score < best_score:
                best_score = score
                best_state = child_state
            if best_score < a:
                break
            b = min(b, best_score)
        return best_score, best_state
    
# def is_terminal_state(state):
#     # Check if the state is a terminal state (win, loss, or draw)
#     # Return True if it is, False otherwise
#     pass

def manhattanDistance(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def evaluate_state(state):
    pacman_position = state[0]
    ghost1_position = state[1]
    ghost2_position = state[2]

    score = 0
    # Calculate the Manhattan distance between Pacman and each ghost
    distance_to_ghost1 = abs(pacman_position[0] - ghost1_position[0]) + abs(pacman_position[1] - ghost1_position[1])
    distance_to_ghost2 = abs(pacman_position[0] - ghost2_position[0]) + abs(pacman_position[1] - ghost2_position[1])
    if board[pacman_position[1]][pacman_position[0]] == 1 or board[pacman_position[1]][pacman_position[0]] == 2:
        score = 100
    # else:
    #     score = -100
    
    else:
        counter, minD, dd = food(pacman_position)
        cnt = closest(pacman_position)
        if (cnt == -1):
            cnt = minD
        score += min(distance_to_ghost1, distance_to_ghost2) / (cnt * 100)

    if distance_to_ghost1 == 0 or distance_to_ghost2 == 0:
        score -= 100000
    elif distance_to_ghost1 <= 5 or distance_to_ghost2 <= 5:
        score -= 10000
    else:
        score += 1000

    
    if py == iy and py == cy:
        if (px > ix and px < cx) or (px > cx and px < ix):
            score -= 1000
    if px == ix and px == cx:
        if (py > iy and py < cy) or (py > cy and py < iy):
            score -= 1000

    return score
    
def closest(pos):
    queue = []
    queue.append((pos, 1))
    while len(queue) != 0:
        if(len(queue) > 2000):
            return -1
        top = queue.pop(0)
        x, y = top[0]
        cnt = top[1]
        if x < len(board[0]) - 1:
            if board[y][x + 1] < 3:
                if board[y][x + 1] != 0:
                    return cnt
                queue.append(((x + 1, y),cnt+1))
        if x > 0:
            if board[y][x - 1] < 3:
                if board[y][x - 1] != 0:
                    return cnt                
                queue.append(((x - 1, y),cnt+1)) 
        if y < len(board) - 1:
            if board[y + 1][x] < 3:
                if board[y + 1][x] != 0:
                    return cnt                
                queue.append(((x, y+1),cnt+1))
        if y > 0:
            if board[y - 1][x] < 3:
                if board[y - 1][x] != 0:
                    return cnt                
                queue.append(((x, y-1),cnt+1))

def food(pos):
    minD = float('inf')
    dd = 0
    counter = 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if j == pos[0] and i == pos[1]:
                continue
            if (board[i][j] == 1 or board[i][j] == 2):
                dis = manhattanDistance(pos, (j, i))
                dd += dis
                if dis < minD:
                    minD = dis
                counter += 1
    return counter, minD, dd

def get_possible_moves(state, depth):
    pacman_position = state[0]
    ghost1_position = state[1]
    ghost2_position = state[2]
    
    possible_moves = []
    
    # Check all four possible directions for Pacman
    if depth % 3 == 0:
        for direction in range(4):
            new_pacman_position = move(pacman_position[0], pacman_position[1], direction)
            
            # Check if the new position is within the board and not a wall (less than 3)
            if (0 <= new_pacman_position[0] < len(board[0])) and (0 <= new_pacman_position[1] < len(board)) and (board[new_pacman_position[1]][new_pacman_position[0]] < 3):
                new_state = [new_pacman_position, ghost1_position, ghost2_position]
                possible_moves.append(new_state)
    elif depth % 3 == 2:
        for direction in range(4):
            new_ghost1_position = move(ghost1_position[0], ghost1_position[1], direction)
            
            # Check if the new position is within the board and not a wall (less than 3)
            if (0 <= new_ghost1_position[0] < len(board[0])) and (0 <= new_ghost1_position[1] < len(board)) and (board[new_ghost1_position[1]][new_ghost1_position[0]] < 3):
                new_state = [pacman_position, new_ghost1_position, ghost2_position]
                possible_moves.append(new_state)
    
    elif depth % 3 == 1:
        for direction in range(4):
            new_ghost2_position = move(ghost2_position[0], ghost2_position[1], direction)
            
            # Check if the new position is within the board and not a wall (less than 3)
            if (0 <= new_ghost2_position[0] < len(board[0])) and (0 <= new_ghost2_position[1] < len(board)) and (board[new_ghost2_position[1]][new_ghost2_position[0]] < 3):
                new_state = [pacman_position, ghost1_position, new_ghost2_position]
                possible_moves.append(new_state)        
    
    return possible_moves