richard-to
12/24/2013 - 6:43 AM

Owari with Alpha Beta Pruning and MySQL transposition table. Can't remember if this code actually works anymore, but was using it to try to

Owari with Alpha Beta Pruning and MySQL transposition table. Can't remember if this code actually works anymore, but was using it to try to find all possible moves in Owari. Unfortunately there are probably over a hundred million moves and my old desktop ran out of RAM at about 22 million. Only 4GB installed.

import time
import MySQLdb as mdb

from warnings import filterwarnings

import config

filterwarnings('ignore', category = mdb.Warning)

conn = mdb.connect(*config.db)
c = conn.cursor()
c.execute('''CREATE TABLE IF NOT EXISTS owari_cache (id bigint unsigned not null primary key auto_increment, state char(60), outcome tinyint, index(state))''')
conn.commit()

memcache = {}

recordsCommitLimit = 5000
recordsInserted = 0

def storeCache(state, score):
    global memcache
    global c
    global conn
    global recordsInserted
    global recordsCommitLimit

    if checkCache(state) is None:
        try:
            c.execute("INSERT INTO owari_cache(state,outcome) VALUES (\'" + str(state) + "'," + str(score) + ")")
            memcache[str(state)] = score
            recordsInserted += 1
            if recordsInserted >= recordsCommitLimit:
                conn.commit()
                recordsInserted = 0
                memcache = {}
        except:
            pass


def checkCache(state):
    global memcache
    if str(state) in memcache:
        return memcache[str(state)]
    else:
        c.execute("""SELECT state, outcome FROM owari_cache where WHERE state = %s""", (str(state),))
        r = c.fetchone()
        if r is not None:
            return r[1]
        else:
            return None


class OwariAlphaBeta(object):
    def decision(self, board):
        bestMove = -1000
        bestBoard = None
        move = 0
        alpha = -1000
        beta = 1000
        for nextMove in xrange(6):
            newBoard = makeMoveP1(nextMove, board)
            if newBoard:
                predictedMove = self.minValue(newBoard, alpha, beta, 0, 10)
                if predictedMove > bestMove:
                    bestMove = predictedMove
                    move = nextMove
                    bestBoard = newBoard
            
            break
        return bestBoard

    def maxValue(self, board, alpha, beta, currentDepth, maxDepth=None):
        status = checkForWinner(board)
        if status == 0:
            return -1
        elif status == 1:
            return 1
        elif status == 2:
            return 0
        else:
            cachedMoveValue = checkCache(board)
            if cachedMoveValue is not None:
                return cachedMoveValue
            else:
                bestMoveValue = -1000
                moveValue = 0
                bestCache = []
                for i in xrange(6):
                    newBoard = makeMoveP1(i, board)
                    if newBoard is not None:
                        moveValue = self.minValue(newBoard, alpha, beta, currentDepth + 1, maxDepth)
                        if moveValue > bestMoveValue:
                            bestMoveValue = moveValue
                            bestCache = [newBoard, bestMoveValue]

                        if bestMoveValue >= beta:
                            storeCache(bestCache[0], bestCache[1])
                            return bestMoveValue

                        if bestMoveValue > alpha:
                            alpha = bestMoveValue

                storeCache(bestCache[0], bestCache[1])
                return bestMoveValue

    def minValue(self, board, alpha, beta, currentDepth, maxDepth=None):
        status = checkForWinner(board)
        if status == 0:
            return -1
        elif status == 1:
            return 1
        elif status == 2:
            return 0
        else:
            bestMoveValue = 1000
            moveValue = 0
            for i in xrange(7, 13):
                newBoard = makeMoveP2(i, board)
                if newBoard is not None:
                    moveValue = self.maxValue(newBoard, alpha, beta, currentDepth + 1, maxDepth)
                    if moveValue < bestMoveValue:
                        bestMoveValue = moveValue

                    if bestMoveValue <= alpha:
                        return bestMoveValue

                    if bestMoveValue < beta:
                        beta = bestMoveValue
            return bestMoveValue


def getComputerPlayerMove(player, board):
    start = time.time()
    ai = OwariAlphaBeta()
    result = ai.decision(board)
    print time.time() - start
    return result


def makeMoveP2(move, board):
    if board[move] == 0:
        return None

    newBoard = board[:]
    next = (move + 1) % 14
    seeds = newBoard[move]
    newBoard[move] = 0

    while seeds > 0:
        if next != 6:
            newBoard[next] += 1;
            if seeds == 1 and newBoard[next] == 1 and next >= 7 and next <= 12:
                newBoard[13] += newBoard[12 - next]
                newBoard[12 - next] = 0
            seeds -= 1
        next = (next + 1) % 14
    return newBoard


def makeMoveP1(move, board):
    if board[move] == 0:
        return None

    newBoard = board[:]
    next = (move + 1) % 14
    seeds = newBoard[move]
    newBoard[move] = 0

    while seeds > 0:
        if next != 13:
            newBoard[next] += 1;
            if seeds == 1 and newBoard[next] == 1 and next >= 0 and next <= 5:
                newBoard[6] += newBoard[12 - next]
                newBoard[12 - next] = 0
            seeds -= 1
        next = (next + 1) % 14
    return newBoard


def calcScoreDiff(board):
    p1Score = board[0] + board[1] + board[2] + board[3] + board[4] + board[5] + board[6]
    p2Score = board[7] + board[8] + board[9] + board[10] + board[11] + board[12] + board[13]
    return p2Score - p1Score


def checkForWinner(board):
    p1SeedSum = board[0] + board[1] + board[2] + board[3] + board[4] + board[5]
    p2SeedSum = board[7] + board[8] + board[9] + board[10] + board[11] + board[12]
    if p1SeedSum == 0 or p2SeedSum == 0:
        p1Score = p1SeedSum + board[6]
        p2Score = p2SeedSum + board[13]
        if p1Score < p2Score:
            return 0
        elif p1Score > p2Score:
            return 1
        else:
            return 2

    else:
        return 3


def printBoard(board):
    print ''.join(["North: ", str(list(reversed(board[7:14])))])
    print ''.join(["South: ", str(board[0:7])])


def printScore(p0Score, p1Score):
    print ' '.join(["Score:", str(p0Score), str(p1Score)])


def getWhoMovesFirst():
    decision = raw_input("Do you want to go first (Y/n)? ")
    return True if decision == 'Y' else False


def getHumanPlayerMove(validPits, board):
    validPitsAsStr = [str(pitNum) for pitNum in validPits]
    validMove = False
    move = None
    while validMove is False:
        input = (raw_input(''.join(["Pick a pit ", str(validPits), "? "]))).strip()
        if input in validPitsAsStr:
            move = int(input)
            if board[move] > 0:
                validMove = True
            else:
                print "Please select pit with seeds in it!"
        else:
            print "Please select a pit that belongs to you!"
    return makeMove(move, board)


def makeMove(move, board):
    if move < 6:
        goal = 6
        skip = 13
        min = 0
        max = 5
    else:
        goal = 13
        skip = 6
        min = 7
        max = 12

    newBoard = board[:]
    if newBoard[move] == 0:
        return None

    seeds = newBoard[move]
    newBoard[move] = 0
    size = len(newBoard)
    next = (move + 1) % size

    while seeds > 0:
        if next != 13:
            newBoard[next] += 1
            if seeds == 1 and newBoard[next] == 1 and next >= min and next <= max:
                newBoard[goal] += newBoard[12 - next]
                newBoard[12 - next] = 0
            seeds -= 1
        next = (next + 1) % size
    return newBoard


def checkEmptyPits(pPits, board):
    for pit in pPits:
        if board[pit] > 0:
            return False
    return True


def calcScore(playerGoal, playerPits, board):
    score = board[playerGoal]
    for pit in playerPits:
        score += board[pit]
    return score


def determineWinner(p0Score, p1Score):
    if p1Score > p0Score:
        return 1
    elif p0Score > p1Score:
        return 0
    else:
        return 2


def main():
    board = [3, 3, 3, 3, 3, 3, 0, 3, 3, 3, 3, 3, 3, 0]
    player0Pits = [0, 1, 2, 3, 4, 5]
    player0Goal = 6
    player1Pits = [7, 8, 9, 10, 11, 12]
    player1Goal = 13

    playerOrder = [
        [player0Pits, getComputerPlayerMove],
        [player1Pits, getHumanPlayerMove]
    ]

    if getWhoMovesFirst():
        playerOrder.reverse()

    while True:
        for playerPits, moveFunc in playerOrder:
            printBoard(board)

            board = moveFunc(playerPits, board)
            player0Score = calcScore(player0Goal, player0Pits, board)
            player1Score = calcScore(player1Goal, player1Pits, board)
            printScore(player0Score, player1Score)

            if checkEmptyPits(playerPits, board):
                break

        if checkEmptyPits(playerPits, board):
            break

    status = determineWinner(player0Score, player1Score)
    if status == 1:
        print "You won!"
    elif status == 0:
        print "You lost!"
    else:
        print "You tied!"


if __name__ == '__main__':
    main()