game2048.py

#!python
"""
game2048.py
bot to play 2048 game by http://gabrielecirulli.com/
as submission for https://www.hackerrank.com/contests/2048-game/challenges/2048
best score 157.2
"""
import copy
import random
import math

board_pos = []
for y in xrange(4):
    for x in xrange(4):
        board_pos.append((y, x))

def get_random_point(board=None, prob=None):
    while True:
        y,x = board_pos[random.randint(0, len(board_pos)-1)]
        if board is not None:
            if board[y][x] == 0:
                break
    if prob is None:
        return y,x
    else:
        accum = []
        total = 0.0
        for k,v in prob.items():
            total += v
            accum.append((k, total))
        sel = accum[0][0]
        rv = random.random()
        for k, a in accum:
            if rv < a:
                sel = k
                break
        return y, x, sel

class Game:
    def __init__(self, parent=None):
        self.parent = parent
        
        if parent is not None:
            self.score = parent.score
            self.board = copy.deepcopy(parent.board)
            self.num_moved = parent.num_moved
        else:
            self.num_moved = 0
            self.score = 0
            self.board = [[0 for x in xrange(4)] for x in xrange(4)]
            y, x = get_random_point(self.board)
            self.board[y][x] = 2
            y, x = get_random_point(self.board)
            self.board[y][x] = 2
            
    def isFull(self):
        numzero = 0
        for y in xrange(4):
            for x in xrange(4):
                if self.board[y][x] == 0: 
                    numzero += 1
        return numzero == 0
            
    def load(self, filename=None):
        if filename is None:
            for i in range(0, 4):
                self.board[i] = map(int, raw_input().strip().split(" "))
        else:
            with open(filename) as f:
                i = 0
                for line in f:
                    self.board[i] = map(int, line.strip().split(" "))
                    i += 1
                    if i>3: break
            
    def putRandom(self):
        if not self.isFull():
            y, x, tile = get_random_point(self.board, {2: 0.75, 4:0.25})
            self.board[y][x] = tile
                
    def left(self):
        num_moved = 0
        for yy in xrange(4):
            #collect nonzero tile in current row
            row = []
            for xx in xrange(4):
                tile = self.board[yy][xx]
                if tile != 0:
                    if len(row)>0 and row[-1]==tile:
                        row[-1] += tile
                        self.score += row[-1]
                    else:
                        row.append(tile)
                    self.board[yy][xx] = 0
            if len(row)<4: num_moved += 1
            #put row from left
            for column, tile in enumerate(row):
                self.board[yy][column] = tile
        if num_moved>0: self.putRandom()
        self.num_moved = num_moved
        return num_moved>0
        
    def right(self):
        num_moved = 0
        for yy in xrange(4):
            #collect nonzero tile in current row
            row = []
            for xx in xrange(4):
                tile = self.board[yy][3-xx]
                if tile != 0:
                    if len(row)>0 and row[-1]==tile:
                        row[-1] += tile
                        self.score += row[-1]
                    else:
                        row.append(tile)
                    self.board[yy][3-xx] = 0
            if len(row)<4: num_moved += 1
            #put row from left
            for column, tile in enumerate(row):
                self.board[yy][3-column] = tile
        if num_moved>0: self.putRandom()
        self.num_moved = num_moved
        return num_moved>0
        
    def up(self):
        num_moved = 0
        for xx in xrange(4):
            #collect nonzero tile in current row
            row = []
            for yy in xrange(4):
                tile = self.board[yy][xx]
                if tile != 0:
                    if len(row)>0 and row[-1]==tile:
                        row[-1] += tile
                        self.score += row[-1]
                    else:
                        row.append(tile)
                    self.board[yy][xx] = 0
            if len(row)<4: num_moved += 1
            #put row from left
            for yy, tile in enumerate(row):
                self.board[yy][xx] = tile
        if num_moved>0: self.putRandom()
        self.num_moved = num_moved
        return num_moved>0
        
    def down(self):
        num_moved = 0
        for xx in xrange(4):
            #collect nonzero tile in current row
            row = []
            for yy in xrange(4):
                tile = self.board[3-yy][xx]
                if tile != 0:
                    if len(row)>0 and row[-1]==tile:
                        row[-1] += tile
                        self.score += row[-1]
                    else:
                        row.append(tile)
                    self.board[3-yy][xx] = 0
            if len(row)<4: num_moved += 1
            #put row from left
            for yy, tile in enumerate(row):
                self.board[3-yy][xx] = tile
        if num_moved>0: self.putRandom()
        self.num_moved = num_moved
        return num_moved>0
        
    def __repr__(self):
        return "\n".join(["\t".join(map(str, self.board[i])) for i in xrange(4)])
        
def play(game, nextFn):
    action = nextFn(game.board)
    if action == "UP": game.up()
    elif action == "LEFT": game.left()
    elif action == "RIGHT": game.right()
    elif action == "DOWN": game.down()
    return action
   
#weighting score is counterproductive   
#factor = {"LEFT":1.0, "DOWN":1.0, "RIGHT":1.0}
    
def oneStep(board):
    orig = Game()
    orig.board = copy.deepcopy(board)
    alt = {}
    
    #g = Game(orig)
    #if g.up(): alt["UP"] = g
    g = Game(orig)
    if g.left(): alt["LEFT"] = g
    g = Game(orig)
    if g.down(): alt["DOWN"] = g
    g = Game(orig)
    if g.right(): alt["RIGHT"] = g
    if len(alt.keys())==0: return "FAIL"
    
    options = [(k, g.score+math.exp(g.num_moved)) for k,g in alt.items()]
    
    options = sorted(options, key=lambda x:x[1], reverse=True)
    choice = options[0]
    if choice[1] == 0:
        choice = options[random.randint(0, len(options)-1)]
    return choice[0]
        
def nextMove_greedyN(board, step=3):
    orig = Game()
    orig.board = copy.deepcopy(board)
    alt = {}
    #g = Game(orig)
    #if g.up(): alt["UP"] = g
    g = Game(orig)
    if g.left(): alt["LEFT"] = g
    g = Game(orig)
    if g.down(): alt["DOWN"] = g
    g = Game(orig)
    if g.right(): alt["RIGHT"] = g
    if len(alt.keys())==0: return "FAIL"
    
    #for step in xrange(step):
    for step in xrange(random.randint(1,step)):
        for d,g in alt.items():
            play(g, oneStep)
    
    #options = [(k, g.score+math.exp(g.num_moved)) for k,g in alt.items()]
    options = [(k, g.score+2**g.num_moved) for k,g in alt.items()]
    
    options = sorted(options, key=lambda x:x[1], reverse=True)
    choice = options[0]
    if choice[1] == 0:
        choice = options[random.randint(0, len(options)-1)]
    return choice[0]
    
def nextMove_random(board):
    moves = ['DOWN']*6+['LEFT']*3+['RIGHT']*3
    random.shuffle(moves)
    return moves[random.randint(0, len(moves)-1)]
        
def nextMove(board):
    return nextMove_greedyN(board, 2)
    #return nextMove_random(board)
        
if __name__ == "__main__":
    game = Game()
    #print "enter board starting config"
    #game.load("2048.txt")
    print game
    oldscore = 0
    for i in xrange(10000):
        oldscore = game.score
        act = play(game, nextMove)
        print act
        print game
        print "score: ", game.score, oldscore, game.num_moved
        #raw_input()
        if any(map(lambda x: 256 in x, game.board)):
            print "WIN!"
            break
        if game.isFull() and act=="FAIL":
            print "GAME OVER"
            break
    print "num moves : ", i