game.py

# coding=utf-8

import copy
import random
import sys
import numpy as np
import time

BOARD_SIZE = 4


class Direction(object):
    """Define the possible operation."""
    current = -1
    left = 0
    right = 1
    up = 2
    down = 3


class Game(object):
    def __init__(self):
        random.seed(time.time() * 1000)

        # Reset variable part.
        self.score_ = 0             # game score
        self.action_counter_ = 0    # action counter

        # Internally, we store a 1-D array for the matrix.
        self.before_board_ = [0.0] * (BOARD_SIZE * BOARD_SIZE)
        self.board_ = [0.0] * (BOARD_SIZE * BOARD_SIZE)
        self.random_gen()

        self.action_dict = {}
        # The possible next action list.
        self._next_valid_actions = [0, 1, 2, 3]

        # Define the static matrix used to shuffle the board.
        self.action_dict[Direction.left] = [[a + 4 * b for a in xrange(0, 4)] for b in xrange(0, 4)]
        self.action_dict[Direction.right] = [[a + 4 * b for a in xrange(3, -1, -1)] for b in xrange(3, -1, -1)]
        self.action_dict[Direction.up] = [[a * 4 + b for a in xrange(0, 4)] for b in xrange(0, 4)]
        self.action_dict[Direction.down] = [[a * 4 + b for a in xrange(3, -1, -1)] for b in xrange(3, -1, -1)]

    def reset(self):
        """
        Reset the internal variable.
        """
        # The currents score of game.
        self.score_ = 0
        self.action_counter_ = 0
        # Internally, we store a 1-D array for the matrix.
        self.before_board_ = [0.0] * (BOARD_SIZE * BOARD_SIZE)
        self.board_ = [0.0] * (BOARD_SIZE * BOARD_SIZE)
        self.random_gen()

    def load_board(self, new_board):
        self.board_ = new_board
        self._next_valid_actions = self.check_left_right() + self.check_up_down()

    @staticmethod
    def shuffle(target_list):
        """
        Shuffle a row of elements into concise mode
        For example:
            [2, 2, 0, 8] -> [4, 8, 0, 0]
            [2, 2, 2, 2] -> [4, 4, 0, 0]
        Args:
            target_list: input array of elements.

        Returns:
            output_list: concise array of elements.
            incremental_score: score generated by this movement.
        """
        non_zero_pos = [i for i, e in enumerate(target_list) if e != 0]
        concise_list = [target_list[i] for i in non_zero_pos]
        concise_list.extend([0] * (len(target_list) - len(non_zero_pos)))
        target = 0
        i = 0
        output_list = [0] * len(concise_list)
        incremental_score = 0

        while i < len(concise_list):
            if i != len(concise_list) - 1 and concise_list[i] == concise_list[i + 1] and concise_list[i] != 0:
                output_list[target] = 2 * concise_list[i]
                incremental_score += output_list[target]
                target += 1
                i += 1
            elif i == len(concise_list) - 1 or concise_list[i] != 0:
                # Process the last element.
                output_list[target] = concise_list[i]
                target += 1
            i += 1

        return output_list, incremental_score

    def move(self, direction, update=True):
        """
        Move the board on a specific direction
        (left, right, up, down) -> (0, 1, 2, 3)
        Args:
          direction: The movement direction.
          update: True will update the internal board, score,
                and generate a new element on the board.
        Returns:
          The board after movement and the incremental score.
        """
        scan_list = self.action_dict[direction]
        new_board = [0.0] * BOARD_SIZE * BOARD_SIZE
        total_incremental_score = 0
        for positions in scan_list:
            target_scan_list = [self.board_[i] for i in positions]
            output_list, shot_incremental_score = Game.shuffle(target_scan_list)
            total_incremental_score += shot_incremental_score
            for i in xrange(0, BOARD_SIZE):
                new_board[positions[i]] = output_list[i]
        before_board = copy.deepcopy(self.board_);
        if update:
            self.board_ = new_board
            self.score_ += total_incremental_score
            self.action_counter_ += 1
            self.random_gen()

        return new_board, total_incremental_score, before_board

    def random_move(self):
        directions = self.get_valid_directions()
        direction = random.choice(directions)

        actions = np.zeros(4)
        actions[direction] = 1.0
        _, inc_score, before_gen_board = self.move(direction)
        return actions, inc_score, before_gen_board

    def score_move(self, action_score):
        """
        Args:
            action_score: The score on each action.
        Returns:
            actions is 0,1 based action array
            inc_score is the score for this movement.
        """
        directions = self.get_valid_directions(False)
        for i in xrange(0, 4):
            if directions[i] == -1:
                action_score[i] = -sys.float_info.max
        direction = np.argmax(action_score)
        actions = np.zeros(4)
        actions[direction] = 1.0
        _, inc_score, before_gen_board = self.move(direction)

        return actions, inc_score, before_gen_board

    def max_move(self):
        directions = self.get_valid_directions(False)
        board_score_dict = self.get_next_boards(directions)
        directions_score = np.array(
            [board_score_dict[direction][1]
             for direction in [Direction.left, Direction.right, Direction.up, Direction.down]])
        if max(directions_score) == min(directions_score):
            return self.random_move()
        else:
            return self.score_move(directions_score)

    def play_to_end(self):
        """play to the end of game.

        Returns:
        The counter of movement.
        """
        directions = self.get_valid_directions()
        counter = 0
        while len(directions) > 0:
            action, directions = self.random_move()
            counter += 1
        return counter

    def get_valid_directions(self, filter_none=True):
        """
        Please note the order of output is left, right, up, down
        Args:
            filter_none: If true the result will filter those -1 elements.
        Returns:
            The valid direction element array.
        """
        if filter_none:
            return filter(lambda x: x != -1, self._next_valid_actions)
        else:
            return self._next_valid_actions

    def is_end(self):
        """ Check if this game already end. """
        return len(self.get_valid_directions()) == 0

    def get_next_boards(self, directions=[0, 0, 0, 0]):
        """
        Args:
          directions: The direction list, which could contain None.
                      Which means the illegal direction.
        Returns:
          The board score list according to the input directions. If the input direction
          is not None, the element should be the board after movement,
          other wise the element should be the original (board, score) tuple.
        """
        # Initialize the dict with current board and score.
        board_score_dict = {Direction.current: (self.get_board(), self.get_score())}
        # Adds the corresponding next step board and incremental score.
        for direction in [Direction.left, Direction.right, Direction.up, Direction.down]:
            if directions[direction] != -1:
                board_score_dict[direction] = self.move(direction, False)
            else:
                board_score_dict[direction] = (self.get_board(), 0, self.get_before_board())
        return board_score_dict

    def get_eval_boards(self):
        next_boards = self.get_next_boards()
        return [next_boards.get(Direction.left)[0],
                next_boards.get(Direction.right)[0],
                next_boards.get(Direction.up)[0],
                next_boards.get(Direction.down)[0]]

    def get_eval_inc(self):
        next_boards = self.get_next_boards()
        return [[next_boards.get(Direction.left)[1]],
                [next_boards.get(Direction.right)[1]],
                [next_boards.get(Direction.up)[1]],
                [next_boards.get(Direction.down)[1]]]

    def check_left_right(self):
        ret_dict = {}
        for x in xrange(0, BOARD_SIZE):
            for y in xrange(0, BOARD_SIZE - 1):
                if self.board_[x * BOARD_SIZE + y] == self.board_[x * BOARD_SIZE + y + 1] and self.board_[x * BOARD_SIZE + y] != 0:
                    return [Direction.left, Direction.right]
                elif self.board_[x * BOARD_SIZE + y] == 0 and self.board_[x * BOARD_SIZE + y + 1] != 0:
                    ret_dict[Direction.left] = 1
                elif self.board_[x * BOARD_SIZE + y + 1] == 0 and self.board_[x * BOARD_SIZE + y] != 0:
                    ret_dict[Direction.right] = 1
                elif len(ret_dict) == 2:
                    return [Direction.left, Direction.right]

        if len(ret_dict) > 0:
            if ret_dict.has_key(Direction.left):
                return [Direction.left, -1]
            else:
                return [-1, Direction.right]
        else:
            return [-1, -1]

    def check_up_down(self):
        ret_dict = {}
        for x in xrange(0, BOARD_SIZE - 1):
            for y in xrange(0, BOARD_SIZE):
                if self.board_[x * BOARD_SIZE + y] == self.board_[(x + 1) * BOARD_SIZE + y] and self.board_[x * BOARD_SIZE + y] != 0:
                    return [Direction.up, Direction.down]
                elif self.board_[x * BOARD_SIZE + y] == 0 and self.board_[(x + 1) * BOARD_SIZE + y] != 0:
                    ret_dict[Direction.up] = 1
                elif self.board_[(x + 1) * BOARD_SIZE + y] == 0 and self.board_[x * BOARD_SIZE + y] != 0:
                    ret_dict[Direction.down] = 1
                elif len(ret_dict) == 2:
                    return [Direction.up, Direction.down]
        if len(ret_dict) > 0:
            if ret_dict.has_key(Direction.up):
                return [Direction.up, -1]
            else:
                return [-1, Direction.down]
        else:
            return [-1, -1]

    def random_gen(self):
        # Randomly generate one element in any available position.
        next_value = random.random() > 0.9 and 4 or 2
        self.before_board_=copy.deepcopy(self.board_)
        self.board_[random.choice([i for i, e in enumerate(self.board_) if e == 0])] = next_value
        # refresh the internal states
        self._next_valid_actions = self.check_left_right() + self.check_up_down()

    def get_board(self):
        return copy.deepcopy(self.board_)

    def get_before_board(self):
        return copy.deepcopy(self.before_board_)

    def set_board(self, board):
        self.before_board_ = copy.deepcopy(board)
        self.board_ = copy.deepcopy(board)

    def get_score(self):
        return self.score_

    def get_action_counter(self):
        return self.action_counter_

    def display(self, board):
        a = ("┌", "├", "├", "├", "└")
        b = ("┬", "┼", "┼", "┼", "┴")
        c = ("┐", "┤", "┤", "┤", "┘")
        for i in range(BOARD_SIZE):
            print a[i] + ("─" * 5 + b[i]) * 3 + ("─" * 5 + c[i])
            for j in range(4):
                print "│%4s" % (board[i * BOARD_SIZE + j] if board[i * BOARD_SIZE + j] else ' '),
            print "│"
        print a[4] + ("─" * 5 + b[4]) * 3 + ("─" * 5 + c[4])

    def __repr__(self):
        return "score: %d step: %d" % (self.score_, self.action_counter_)

if __name__ == '__main__':
    game = Game()

    # Random movement.
    game.move(2)
    game.display(game.get_board())
    game.display(game.get_before_board())
    print game.get_next_boards()
    print game.get_eval_boards()

    game.display(game.get_next_boards().get(Direction.left)[0])
    game.display(game.get_next_boards().get(Direction.right)[0])
    game.display(game.get_next_boards().get(Direction.up)[0])
    game.display(game.get_next_boards().get(Direction.down)[0])

    # Confirmed movement.
    game.set_board([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 8, 32])
    game.move(2)
    game.display(game.get_board())
    game.display(game.get_before_board())
#    with open(sys.argv[1], 'w') as wfile:
#        for x in xrange(1, 10000):
#            game = Game()
#            while len(game.get_valid_directions()) > 0:
#                game.max_move()
#            wfile.write('%d:%d\n' % (x, game.get_score()))
#            print '%d:%d-%d' % (x, game.get_score(), game.get_action_counter())
#    print "finished"