2048 puzzle game

2048.cpp

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

int USER = 1;
int COMPUTER = 0;

#define LEFT 0
#define RIGHT 1
#define UP 2
#define DOWN 3

#define DEPTH 5

const int board_size = 4;

struct result {
    int direction;
    int score;
};

class Board {
    static const int target = 2048;
    static const int max_score = 18432;
    int ** board;
    unsigned int score;
public:
    Board() {
        board = new int * [board_size];
        for (int i = 0; i < board_size; i++) {
            board[i] = new int[board_size];
            for (int j = 0; j < board_size; j++) {
                board[i][j] = 0;
            }
        }
        addRandomCell();
        addRandomCell();
        score = 0;
    }
    Board(const Board & b) {
        board = b.board;
        score = b.score;
    }
    vector<int> getEmptyCells() {
        vector<int> v;
        for (int i = 0; i < board_size; i++) {
            for (int j = 0; j < board_size; j++) {
                if(board[i][j] == 0)
                    v.push_back(i*board_size+j);
            }
        }
        return v;
    }

    bool addRandomCell() {
        double d = ((double) rand() / (RAND_MAX));
        int num = d < 0.9 ? 2:4;
        vector<int> emptyCells=getEmptyCells();
        if(emptyCells.size() == 0)
            return false;
        int pos = rand() % emptyCells.size();
        pos = emptyCells[pos];
        board[pos/board_size][pos%board_size] = num;
        return true;
    }
    int move (int direction, bool check=false) {
        int points=0;
        //rotate the board to make simplify the merging algorithm
        if(direction == UP) {
            rotateLeft();
        } else if(direction == RIGHT) {
            rotateLeft();
            rotateLeft();
        } else if(direction == DOWN) {
            rotateRight();
        }
        for (int i = 0; i < board_size; i++) {
            int last_merge = 0;
            for (int j = 1; j < board_size; j++) {
                if(board[i][j] == 0) {
                    continue; // skip moving zeros
                }
                int prev = j-1;
                while(prev >last_merge && board[i][prev]==0) { //skip all the zeros
                    --prev;
                }
                if(prev==j) {
                    //we can't move this at all
                }

                else if(board[i][prev]==0) {
                    //move to empty value
                    board[i][prev]=board[i][j];
                    board[i][j]=0;
                }
                else if(board[i][prev]==board[i][j]){
                    //merge with matching value
                    board[i][prev]*=2;
                    board[i][j]=0;
                    points+=board[i][prev];
                    last_merge=prev+1;

                }
                else if(board[i][prev]!=board[i][j] && prev+1!=j){
                    board[i][prev+1]=board[i][j];
                    board[i][j]=0;
                }
            }
        }
        if(!check)
            score += points;
        //reverse back the board to the original orientation
        if(direction==UP) {
            rotateRight();
        }
        else if(direction==RIGHT) {
            rotateRight();
            rotateRight();
        }
        else if(direction==DOWN) {
            rotateLeft();
        }
        if(!check)
            addRandomCell();
        // printf("%d\n", points);
        return points;
    }
    /**
     * Rotates the board on the left
     */
    void rotateLeft() {
        int ** rotatedBoard;
        rotatedBoard = new int * [board_size];
        for(int i=0;i< board_size;++i) {
            rotatedBoard[i] = new int [board_size];
        }
        for(int i=0;i< board_size;++i) {
            for(int j=0;j< board_size;++j) {
                rotatedBoard[board_size-j-1][i] = board[i][j];
            }
        }
        for(int i=0;i< board_size;++i) {
            delete board[i];
        }
        delete board;
        board=rotatedBoard;
    }

    /**
     * Rotates the board on the right
     */
    void rotateRight() {
        int ** rotatedBoard;
        rotatedBoard = new int * [board_size];
        for(int i=0;i< board_size;++i) {
            rotatedBoard[i] = new int [board_size];
        }
        for(int i=0;i< board_size;++i) {
            for(int j=0;j< board_size;++j) {
                rotatedBoard[i][j]=board[board_size-j-1][i];
            }
        }
        for(int i=0;i< board_size;++i) {
            delete board[i];
        }
        delete board;
        board=rotatedBoard;
    }
    void print() {
        printf("\n------------------------\n");
        printf("   SCORE: %10d", score);
        printf("\n------------------------\n");
        for(int i=0;i< board_size;++i) {
            for(int j=0;j< board_size;++j) {
                printf("%6d", board[i][j]);
            }
            cout << endl;
        }
        printf("------------------------\n");
    }
    bool hasWon() {
        if(score< max_score) { //speed optimization
            return false;
        }
        for(int i=0;i<board_size;++i) {
            for(int j=0;j<board_size;++j) {
                if(board[i][j]>= target) {
                    return true;
                }
            }
        }
        return false;
    }
    int free_cell_count() {
    	int free_cnt = 0;
        for(int i=0;i< board_size;++i) {
            for(int j=0;j< board_size;++j) {
                if (board[i][j] == 0)
                	free_cnt ++;
            }
        }
        return free_cnt;
    }
    bool is_gameover() {
        int ** new_board; bool over=false;
        new_board = new int * [board_size];
        for (int i = 0; i < board_size; i++) {
            new_board[i] = new int [board_size];
        }
        memcpy(new_board, board, board_size*board_size* sizeof(int));
        if(free_cell_count() == 0 && !(move(LEFT, true) || move(RIGHT, true) || move(UP, true) || move(DOWN, true))) {
            over = true;
        }
        memcpy(board, new_board, board_size*board_size* sizeof(int));
        return over;
    }
    int ** copy_grid() {
        int ** new_board;
        new_board = new int * [board_size];
        for (int i = 0; i < board_size; i++) {
            new_board[i] = new int [board_size];
        }
        memcpy(new_board, board, board_size*board_size* sizeof(int));
        return new_board;
    }
    void set_grid(int ** grid) {
        memcpy(board, grid, board_size*board_size* sizeof(int));
    }
    int getScore() {
        return score;
    }
    void setEmptyCell(int id, int value) {
        board[id/board_size][id%board_size] = value;
    }
};

result min_max(Board board, int depth, int player);
int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore);
int calculateClusteringScore(int ** board);

int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
    int score = (int) (actualScore + log(actualScore)*numberOfEmptyCells - clusteringScore);
    return max(score, min(actualScore, 1));
}

result min_max(Board board, int depth, int player) {
    result best, curr; Board newBoard;
    cout << "A";
    if(depth == 0 || board.is_gameover()) {
        best.score = heuristicScore(board.getScore(), board.free_cell_count(), 1); // calculateClusteringScore(board.copy_grid())
    } else {
        if(player == USER) {
            best.score = INT_MIN;
            for(int i=0; i<4; i++) {
                newBoard = board;
                int points = newBoard.move(i);
                if(points == 0 && memcmp(newBoard.copy_grid(), board.copy_grid(), sizeof(int)*16) == 0)
                    continue;
                curr = min_max(board, depth-1, COMPUTER);
                if(curr.score > best.score) {
                    best.score = curr.score;
                    best.direction = i;
                }
            }
        } else {
            best.score = INT_MAX;
            vector<int> free_cells = board.getEmptyCells();
            if(free_cells.size() == 0) {
                best.score = 0;
            }
            for (int i = 0; i < free_cells.size(); i++) {
                newBoard = board;
                newBoard.setEmptyCell(free_cells[i], 2);
                result curr = min_max(board, depth-1, USER);
                if(curr.score < best.score) {
                    best.score = curr.score;
                }
                Board newBoard = Board(board);
                newBoard.setEmptyCell(free_cells[i], 4);
                curr = min_max(board, depth-1, USER);
                if(curr.score < best.score) {
                    best.score = curr.score;
                }
            }
        }
        return best;
    }
}

int calculateClusteringScore(int ** board) {
    int clusteringScore=0;
    int neighbours[] = {-1,0,1};
    for(int i=0; i < 4; ++i) {
        for(int j=0; j<4; ++j) {
            if(board[i][j]==0) {
                continue; //ignore empty cells
            }
            //clusteringScore-=boardArray[i][j];
            //for every pixel find the distance from each neightbors
            int numOfNeighbors = 0;
            int sum = 0;
            for(int k=0; k < 3; k) {
                int x = i+neighbours[k];
                if(x<0 || x >= 4) {
                    continue;
                }
                for(int l; l < 3; l++) {
                    int y = j+neighbours[l];
                    if(y<0 || y>=4) {
                        continue;
                    }
                    if(board[x][y]>0) {
                        ++numOfNeighbors;
                        sum += abs(board[i][j]-board[x][y]);
                    }
                }
            }
            clusteringScore+=sum/numOfNeighbors;
        }
    }
    return clusteringScore;
}

int get_move(Board board){
    result res = min_max(board, 2, 1);
}

int main(int argc, char const *argv[]) {
    srand(time(NULL));
    Board board;
    // board->init();
    int direction=0;
    board.print();
    while(!board.hasWon()) {
        // cout << "B";
        // direction = get_move(board);
        direction = rand()%board_size;
        printf("AI said to move %d\n", direction);
        if(board.move(direction) == 0 && board.is_gameover()) {
            board.print();
            printf("GameOver !! %d\n", board.is_gameover());
            break;
        }
        board.print();
        sleep(0.5);
    }
    return 0;
}