A MiniMax (Alpha-Beta) pruning agent to play game of checkers.

checkers_agent.py

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()

host.py

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