Created
December 24, 2013 06:43
-
-
Save richard-to/8109617 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment