Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A MiniMax (Alpha-Beta) pruning agent to play game of checkers.
from random import random
inp = open("input.txt", "r")
single = inp.readline().strip() == 'SINGLE'
white = inp.readline().strip() == 'WHITE'
remain_time = float(inp.readline().strip())
board = []
for i in range(8):
board.append( inp.readline().lstrip() )
inp.close()
max_positions = {}
min_positions = {}
for i in range(8):
y = 7-i
for x in range(8):
c = board[i][x]
if c == '.': continue
elif c=='w': max_positions[ (y,x) ] = False
elif c=='W': max_positions[ (y,x) ] = True
elif c=='b': min_positions[ (y,x) ] = False
elif c=='B': min_positions[ (y,x) ] = True
else: continue
if not white: min_positions, max_positions = max_positions, min_positions
CUTTOFF_THRESHOLD = 6
OPT_ACTION = None
if not single:
if remain_time < 30: CUTTOFF_THRESHOLD = 7
else:
pieces = len(max_positions)+len(min_positions)
CUTTOFF_THRESHOLD = (9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 6, 6, 6, 5, 5)[pieces]
def possible_moves( maxs, mins, white_chance = True, restrict_src = None ):
moves = list()
start, kill = (restrict_src, True) if restrict_src else (maxs.items(), False)
for (y, x), typ1 in start:
for r,c in ( (1,1), (1, -1), (-1, -1), (-1, 1) ):
if white_chance and not typ1 and r == -1: continue
elif not white_chance and not typ1 and r == 1: continue
ny, nx = y+r, x+c
if ny in (-1, 8) or nx in (-1, 8): continue
elif (ny, nx) in maxs: continue
elif (ny, nx) in mins:
new_p = (ny+r, nx+c)
if new_p[0] not in (-1, 8) and new_p[1] not in (-1, 8) and \
new_p not in maxs and new_p not in mins:
if not kill: moves.clear(); kill = True
moves.append( ((y,x), new_p, True) )
continue
elif not kill: moves.append( ( (y,x), (ny, nx), False) )
else: continue
return moves, kill and len(moves) > 0
def evaluate(maxs, mins):
value = random()/5
for _, k in maxs.items(): value += (7 + 3*k)
for _, k in mins.items(): value -= (7 + 3*k)
return value
def getNewPositions( maxs, mins, old_p, new_p, kill, white_chance ):
new_maxs, new_mins = maxs.copy(), mins.copy()
new_maxs[new_p] = new_maxs.pop( old_p )
if kill: new_mins.pop( ( (old_p[0]+new_p[0])//2, (old_p[1]+new_p[1])//2 ) )
king = False
if white_chance and new_p[0] == 7 and new_maxs[new_p] == 0:
new_maxs[new_p], king = 1, True
elif not white_chance and new_p[0] == 0 and new_maxs[new_p] == 0:
new_maxs[new_p], king = 1, True
else: pass
return new_maxs, new_mins, king
def max_value(maxs, mins, alpha, beta, depth, white_chance, restrict_src_for_kill = None):
if depth >= CUTTOFF_THRESHOLD: return evaluate( maxs, mins )
v = float('-inf')
global OPT_ACTION;
moves = None
if restrict_src_for_kill:
moves, kill = possible_moves(maxs, mins, white_chance,
restrict_src=[ (restrict_src_for_kill, maxs[restrict_src_for_kill]) ])
if not kill: return min_value(mins, maxs, alpha, beta, depth, not white_chance)
else: moves, kill = possible_moves(maxs, mins, white_chance)
if not moves: return evaluate(maxs, mins)
for old_p, new_p, kill in moves:
new_maxs, new_mins, king = getNewPositions( maxs, mins, old_p, new_p, kill, white_chance )
if kill and not king:
nv = max_value(new_maxs, new_mins, alpha, beta, depth+1, white_chance, restrict_src_for_kill=new_p)
if nv > v:
if not depth: OPT_ACTION = (old_p, new_p)
v = nv
else:
nv = min_value(new_mins, new_maxs, alpha, beta, depth+1, not white_chance)
if nv > v:
if not depth: OPT_ACTION = (old_p, new_p)
v = nv
if v >= beta: return v
alpha = max( alpha, v )
return v
def min_value(maxs, mins, alpha, beta, depth, white_chance, restrict_src_for_kill = None):
if depth >= CUTTOFF_THRESHOLD: return evaluate( mins, maxs )
v = float('inf')
moves = None
if restrict_src_for_kill:
moves, kill = possible_moves(maxs, mins, white_chance,
restrict_src=[ (restrict_src_for_kill, maxs[restrict_src_for_kill]) ])
if not kill: return max_value(mins, maxs, alpha, beta, depth, not white_chance)
else: moves, kill = possible_moves(maxs, mins, white_chance)
if not moves: return evaluate(mins, maxs)
for old_p, new_p, kill in moves:
new_maxs, new_mins, king = getNewPositions( maxs, mins, old_p, new_p, kill, white_chance )
if kill and not king:
v = min( v, min_value( new_maxs, new_mins, alpha, beta, depth+1, white_chance, restrict_src_for_kill=new_p))
else:
v = min( v, max_value( new_mins, new_maxs, alpha, beta, depth+1, not white_chance ))
if v <= alpha: return v
beta = min( beta, v )
return v
max_value( max_positions, min_positions, float('-inf'), float('inf'), 0, white )
fp = open("output.txt", 'w')
column_map = ["a", "b", "c", "d", "e", "f", "g", "h"]
(x1, y1), (x2, y2) = OPT_ACTION
if abs(x1-x2) > 1:
CUTTOFF_THRESHOLD = 4
moves_list = []
while abs(x1-x2) > 1:
moves_list.append(f"J {column_map[y1]}{x1+1} {column_map[y2]}{x2+1}")
max_positions, min_positions, king = getNewPositions( max_positions, min_positions, (x1, y1), (x2, y2), True, white )
if king: break
OPT_ACTION = None
max_value(max_positions, min_positions, float('-inf'), float('inf'), 0, white, restrict_src_for_kill=(x2, y2) )
if OPT_ACTION == None: break
(x1, y1), (x2, y2) = OPT_ACTION
print( "\n".join(moves_list), file=fp, end="")
else:
print(f"E {column_map[y1]}{x1+1} {column_map[y2]}{x2+1}", file=fp, end="")
fp.close()
import random
import os
from time import time, sleep
player1 = "checkers_agent.py"
player2 = "player2.py"
timep1 = timep2 = max(100, random.random() * 150) #time will be between 100 and 150 seconds
pieces1 = pieces2 = 12
PAUSE = 0.3
board = [
[".","b",".","b",".","b",".","b"],
["b",".","b",".","b",".","b","."],
[".","b",".","b",".","b",".","b"],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."],
["w",".","w",".","w",".","w","."],
[".","w",".","w",".","w",".","w"],
["w",".","w",".","w",".","w","."]
]
column_map = { "a":0, "b":1, "c":2, "d":3, "e":4, "f":5, "g":6, "h":7 }
def verifyMove(typ, start, end, board):
x1, y1 = start
x2, y2 = end
m1, m2 = (x1+x2)//2, (y1+y2)//2
if abs(x1-x2) != abs(y1-y2): return False
if typ=='E' and abs(x1-x2) != 1: return False
if typ=='J' and abs(x1-x2) != 2: return False
if x1 > 7 or x2 < 0 or y2 > 7 or y2 < 0: return False
if typ=='E' and board[x2][y2] != '.': return False
if typ=='J' and ( board[m1][m2] == '.'
or board[m1][m2].lower() == board[x1][y1].lower()
or board[x2][y2] != '.' ): return False
return True
# toss
if random.random() > 0.5:
player2, player1 = player1, player2
timep1, timep2 = timep2, timep1
pieces1, pieces2 = pieces2, pieces1
white = False
print( f"Each player has {timep1:.2f} seconds to defeat other player.")
print( f"{player1} has won the toss and is playing white." )
if os.path.exists('playdata.txt'): os.remove('playdata.txt');
game_states = dict()
p1_last = p2_last = ""
while True:
board_str = "\n".join(["".join(line) for line in board])
with open("host/input.txt", "w") as fp:
print("GAME", file=fp)
if white:
print("WHITE", file=fp)
print(f"{timep1:.2f}", file=fp)
else:
print("BLACK", file=fp)
print(f"{timep2:.2f}", file=fp)
print(board_str, file=fp)
game_states[board_str] = game_states.get(board_str,0)+1
if game_states[board_str] > 3:
print(f"Game state repeated more than 3 times!! \
{player1 if timep1>timep2 else player2} won by {abs(timep1-timep2):.4f} secs.")
with open("stats.csv", 'a') as fp: print(f"{player1 if timep1>timep2 else player2},Repeat", file=fp)
exit()
if timep1 < 0 or timep2 < 0:
if timep1 < 0: print(f"Time up, {player2} won by {timep2:.4f} secs.")
else: print(f"Time up, {player1} won by {timep1:.4f} secs.")
with open("stats.csv", 'a') as fp: print(f"{player1 if timep1>timep2 else player2},Timeout", file=fp)
exit()
if pieces2 == 0 or pieces1 == 0:
if pieces1 == 0: print(f"Game Finished!! {player2} won.")
else: print(f"Game Finished!! {player1} won.")
with open("stats.csv", 'a') as fp: print(f"{player1 if pieces2==0 else player2},Victory", file=fp)
exit()
sleep(PAUSE)
if white:
start = time()
os.system(f"python {player1} host/input.txt host/output.txt")
timep1 = timep1 - (time()-start)
else:
start = time()
os.system(f"python {player2} host/input.txt host/output.txt")
timep2 = timep2 - (time()-start)
with open("host/output.txt", "r") as fp:
output = fp.readlines()
if white:
if p1_last == "".join(output): print(f'Stalemate - No Moves left!! {player2} wins'); exit()
else: p1_last = "".join(output)
else:
if p2_last == "".join(output): print(f'Stalemate - No Moves left!! {player1} wins'); exit()
else: p2_last = "".join(output)
for line in output:
typ, start, end = tuple(line.split())
x1, y1 = int(start[1])-1, column_map[ start[0] ]
x2, y2 = int(end[1])-1, column_map[ end[0] ]
x1, x2 = 7-x1, 7-x2
if not verifyMove(typ, (x1, y1), (x2, y2), board):
print(f'Invalid Move!! {player1 if white else player2} have made an invalid move.')
exit()
if x2==7 or x2==0:
board[x2][y2] = board[x1][y1].upper()
else:
board[x2][y2] = board[x1][y1]
board[x1][y1] = '.'
if typ=="J":
board[(x1+x2)//2][(y1+y2)//2] = '.'
if white: pieces2 -= 1
else: pieces1 -= 1
white = not white
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment