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!
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.