/*
============================================================================
Name : 2048.c
Author : Maurits van der Schee
Description : Console version of the game "2048" for GNU/Linux
============================================================================
*/
#ifndef __NODE__
#define __NODE__
#ifndef __UTILS__
#define __UTILS__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <termios.h>
#include <stdbool.h>
#include <stdint.h>
#include <time.h>
#include <signal.h>
#define SIZE 4
#define _XOPEN_SOURCE 500
/**
* Move type
*/
typedef enum moves{
left=0,
right=1,
up=2,
down=3
} move_t;
struct ai_s{
move_t move;
int generated;
int expanded;
};
/**
* Back Propagation type
*/
typedef enum propagation{
max=0,
avg=1
} propagation_t;
/**
* Renders the board
*/
void drawBoard(uint8_t board[SIZE][SIZE], uint32_t score);
/**
* Updates the board with each action, and updates the score
*/
bool moveUp(uint8_t board[SIZE][SIZE], uint32_t* score);
bool moveLeft(uint8_t board[SIZE][SIZE], uint32_t* score);
bool moveDown(uint8_t board[SIZE][SIZE], uint32_t* score);
bool moveRight(uint8_t board[SIZE][SIZE], uint32_t* score);
/**
* Checks if game has ended
*/
bool gameEnded(uint8_t board[SIZE][SIZE]);
/**
* Counts the number of empty cells
*/
uint8_t countEmpty(uint8_t board[SIZE][SIZE]);
/**
* Given an index, returns the tile value, i is row, j is column
*/
uint32_t getTile( uint8_t board[SIZE][SIZE], unsigned i, unsigned j);
/**
* initial random board, and a function to randmoly add a tile
*/
void initBoard(uint8_t board[SIZE][SIZE], uint32_t* score);
void addRandom(uint8_t board[SIZE][SIZE]);
/**
* Executes an action, updates the board and the score, and return true if the board has changed,
* and false otherwise
*/
bool execute_move_t( uint8_t board[SIZE][SIZE], uint32_t* score, move_t move);
#endif
/**
* Data structure containing the node information
*/
struct node_s{
uint32_t priority;
int depth;
int num_childs;
move_t move;
uint8_t board[SIZE][SIZE];
struct node_s* parent;
move_t firstMove;
};
typedef struct node_s node_t;
#endif
#ifndef __AI__
#define __AI__
#include <stdint.h>
#include <unistd.h>
void initialize_ai();
struct ai_s get_next_move( uint8_t board[SIZE][SIZE], int max_depth, propagation_t propagation );
int get_max(int* scores);
int propogateBackToFirstAction(node_t* node);
bool board_different(node_t* node1, node_t* node2);
void array_add(node_t* node, node_t** explored, int numNodes );
#endif
#include "inttypes.h"
/**
* Setting up terminal to draw the game board
*/
void setBufferedInput(bool enable) {
static bool enabled = true;
static struct termios old;
struct termios new;
if (enable && !enabled) {
// restore the former settings
tcsetattr(STDIN_FILENO,TCSANOW,&old);
// set the new state
enabled = true;
} else if (!enable && enabled) {
// get the terminal settings for standard input
tcgetattr(STDIN_FILENO,&new);
// we want to keep the old setting to restore them at the end
old = new;
// disable canonical mode (buffered i/o) and local echo
new.c_lflag &=(~ICANON & ~ECHO);
// set the new settings immediately
tcsetattr(STDIN_FILENO,TCSANOW,&new);
// set the new state
enabled = false;
}
}
void signal_callback_handler(int signum) {
printf(" TERMINATED \n");
setBufferedInput(true);
printf("\033[?25h\033[m");
exit(signum);
}
/**
* Valid keys for playing
*/
bool execute_keyboard( uint8_t board[SIZE][SIZE], uint32_t* score, char c){
bool success = false;
switch(c)
{
case 97: // 'a' key
case 104: // 'h' key
case 68: // left arrow
success = moveLeft(board, score); break;
case 100: // 'd' key
case 108: // 'l' key
case 67: // right arrow
success = moveRight(board, score); break;
case 119: // 'w' key
case 107: // 'k' key
case 65: // up arrow
success = moveUp(board, score); break;
case 115: // 's' key
case 106: // 'j' key
case 66: // down arrow
success = moveDown(board, score); break;
default: success = false;
}
return success;
}
void print_usage(){
printf("To run the AI solver: \n");
printf("USAGE: ./2048 ai <max/avg> <max_depth> slow\n");
printf("or, to play with the keyboard: \n");
printf("USAGE: ./2048\n");
}
int main(int argc, char *argv[]) {
clock_t start=clock(),end;
uint32_t score=0;
uint8_t board[SIZE][SIZE];
int generated=0;
int expanded=0;
int i=0,j=0;
uint32_t maxTile=0;
int max_depth=0;
char c;
bool success;
bool ai_run = false;
propagation_t propagation=max;
bool slow = false;
struct ai_s selected_move;
selected_move.move=0;
selected_move.generated=0;
selected_move.expanded=0;
/**
* Parsing command line options
*/
if( argc > 1 && argc < 4 ){
print_usage();
return 0;
}
if (argc > 1 ) {
ai_run = true;
initialize_ai();
if( strcmp(argv[2],"avg")==0 ){
propagation = avg;
}
else if( strcmp(argv[2],"max")==0 ){
propagation = max;
}
else{
print_usage();
return 0;
}
sscanf (argv[3],"%d",&max_depth);
if(argc == 5 && strcmp(argv[4],"slow")==0 )
slow = true;
}
printf("\033[?25l\033[2J");
/**
* register signal handler for when ctrl-c is pressed
*/
signal(SIGINT, signal_callback_handler);
setBufferedInput(false);
/**
* Create initial state
*/
initBoard(board, &score);
while (true) {
/**
* AI execution mode
*/
if(ai_run){
/**
* ****** HERE IS WHERE YOUR SOLVER IS CALLED
*/
selected_move=(get_next_move( board, max_depth, propagation ));
generated+= selected_move.generated;
expanded += selected_move.expanded;
/**
* Execute the selected action
*/
success = execute_move_t( board, &score, selected_move.move);
}
else{
/**
* Keyboard execution mode
*/
c=getchar();
success = execute_keyboard(board, &score, c);
if (c=='q') {
printf(" QUIT? (y/n) \n");
c=getchar();
if (c=='y') {
break;
}
drawBoard(board,score);
}
if (c=='r') {
printf(" RESTART? (y/n) \n");
c=getchar();
if (c=='y') {
initBoard(board, &score);
}
drawBoard(board,score);
}
}
/**
* If selected action merges tiles,
* then, add a random tile and redraw the board
*/
if (success) {
drawBoard(board,score);
if(slow) usleep(150000); //0.15 seconds
addRandom(board);
drawBoard(board,score);
if (gameEnded(board)) {
printf(" GAME OVER \n");
break;
}
}
}
setBufferedInput(true);
printf("\033[?25h\033[m");
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
if(getTile(board,i,j) > maxTile){
maxTile = getTile(board,i,j);
}
}
}
end= clock();
printf("maxDepth = %i \n",max_depth);
printf("Generated = %i\n",generated);
printf("Expanded = %i\n",expanded);
printf("Time = %f\n",(float)((end-start)/1000000.0));
printf("Expanded/Second = %i \n", (int)(expanded / (float)((end-start)/1000000.0)));
printf("max_tile =" "%" PRIu32 "\n", maxTile );
printf("Score = %i\n",score );
return EXIT_SUCCESS;
}
/* Author: Eric Sciberras */
#include <time.h>
#include <stdlib.h>
#ifndef __PQ__
#define __PQ__
/**
* NIR: Adapted from https://gist.github.com/aatishnn/8265656#file-binarymaxheap-c
*/
#include <stdio.h>
#include <stdlib.h>
/**
* size is the allocated size, count is the number of elements in the queue
*/
struct heap {
int size;
int count;
node_t** heaparr;
};
int *heap, size, count;
#define initial_size 4
void heap_init(struct heap* h);
void max_heapify(node_t** data, int loc, int count);
void heap_push(struct heap* h, node_t* value);
void heap_display(struct heap* h);
node_t* heap_delete(struct heap* h);
void emptyPQ(struct heap* pq);
#endif
#include "math.h"
#include "inttypes.h"
#include <assert.h>
struct heap h;
void initialize_ai(){
heap_init(&h);
}
/**
* Find best action by building all possible paths up to depth max_depth
* and back propagate using either max or avg
*/
struct ai_s get_next_move( uint8_t board[SIZE][SIZE], int maxDepth, propagation_t propagation ){
int i=0,numNodes=0;
struct ai_s aiOutput;
aiOutput.generated=0;
aiOutput.expanded=0;
int scores[4]={0,0,0,0}; //this array holds the scores for each move choice and is used to decide how to play
int exploredSize=1000; // keeps track of the size of our explored array
move_t move=0;
node_t* node=(node_t*)calloc(1,sizeof(node_t));
node_t* newNode=(node_t*)calloc(1,sizeof(node_t)); //
node_t* tempNode=(node_t*)calloc(1,sizeof(node_t)); // temporary stores node when executing moves
node_t** explored=(node_t**)calloc(exploredSize,sizeof(node_t)); // holds all the nodes we have looked at
//just in case
assert(node);
assert(newNode);
assert(tempNode);
assert(explored);
memcpy(node->board,board,sizeof(uint8_t) * SIZE * SIZE); // put board in node
node->move=-1;
//heap_init(&h);
array_add(node,explored,numNodes);
//heap_push(&h,explored[numNodes]);
numNodes++;
//frontier_add(node);
while( (&h)->count != 0 ){
node=heap_delete(&h);
aiOutput.expanded++;
//array_add(node,explored,numNodes);
//numNodes++;
if(node->depth < maxDepth){
for(i=0;i<4;i++){
aiOutput.generated++;
// This Block handles the assignment of the Newnode (new board)
// and node (board before the move is made)
memcpy(tempNode,node, sizeof(node_t));
execute_move_t( node->board, &(node->priority), i);
memcpy(newNode,node,sizeof(node_t));
memcpy(node,tempNode,sizeof(node_t));
// if the new board is different then we will add it to the priority queue and
// trace back the score to the first move made, then we will use this data to help
// our propagation
if( board_different(node,newNode) == true ){
newNode->move = i;
newNode->depth = node->depth+1;
newNode->parent = node;
node->num_childs++;
move=propogateBackToFirstAction(newNode);
if( exploredSize <= numNodes){
explored=(node_t**)realloc(explored,2*exploredSize*sizeof(node_t));
assert(explored);
exploredSize = 2*exploredSize;
}
array_add(newNode,explored,numNodes);
numNodes++;
if(propagation==max){
if( newNode->priority > scores[move]){
scores[move]=newNode->priority;
}
}
else{ // Average propogation heuristics: very simple heuristic
// prioritises the scores closer to the current board as they are
// more liekly to be acheived due to the random tiles popping up after each turn
scores[move]+= newNode->priority/ (float)(newNode->depth);
}
}
}
}
}
for(i=0;i<numNodes;i++){
free(explored[i]);
}
free(explored);
free(newNode);
free(tempNode);
//free(node); // yes i know this 'should' be run but it seems to completely destroy my code
aiOutput.move= get_max(scores);
return (aiOutput);
}
void array_add(node_t* node, node_t** explored, int numNodes ){
node_t* tempNode=(node_t*)calloc(1,sizeof(node_t));
assert(tempNode);
memcpy(tempNode,node, sizeof(node_t));
explored[numNodes] = tempNode;
heap_push(&h,tempNode);
}
//board_different takes two nodes and compares them, it returns True if the boards are different
// or false if otherwise
bool board_different(node_t* node1, node_t* node2){
int i ,j;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
if(node1->board[i][j]!=node2->board[i][j] ){
return true;
}
}
}
return false;
}
// get_max takes an int array (4 elements) and find the index of the maximum value,
// in the case of a tie a maximum random move is chosen
int get_max(int* scores){
int i=0, max=0, matches=0;
int duplicate_scores[4]={-1,-1,-1,-1};
// get the maximum element
for (i=0;i<4;i++){
if (scores[i] >= max){
max = scores[i];
}
}
// look for duplicates
for(i=0;i<4;i++){
if(max==scores[i]){
duplicate_scores[matches]=i;
matches++;
}
}
return(duplicate_scores[rand() % matches]);
}
// propogateBackToFirstAction takes a node and finds what original move led to it
int propogateBackToFirstAction(node_t* node){
if(node->depth == 1){
return (node->move);
}
return(propogateBackToFirstAction(node->parent));
}
void heap_init(struct heap* h)
{
int i;
h->count = 0;
h->size = initial_size;
h->heaparr = (node_t **) malloc(sizeof(node_t*) * initial_size);
for(i = 0; i < initial_size; i++)
h->heaparr[i]=NULL;
if(!h->heaparr) {
printf("Error allocatinga memory...\n");
exit(-1);
}
}
void max_heapify(node_t** data, int loc, int count) {
int left, right, largest;
node_t* temp;
left = 2*(loc) + 1;
right = left + 1;
largest = loc;
if (left <= count && data[left]->priority > data[largest]->priority) {
largest = left;
}
if (right <= count && data[right]->priority > data[largest]->priority) {
largest = right;
}
if(largest != loc) {
temp = data[loc];
data[loc] = data[largest];
data[largest] = temp;
max_heapify(data, largest, count);
}
}
void heap_push(struct heap* h, node_t* value)
{
int index, parent;
// Resize the heap if it is too small to hold all the data
if (h->count == h->size)
{
h->size += 1;
h->heaparr = realloc(h->heaparr, sizeof(node_t) * h->size);
if (!h->heaparr) exit(-1); // Exit if the memory allocation fails
}
index = h->count++; // First insert at last of array
// Find out where to put the element and put it
for(;index; index = parent)
{
parent = (index - 1) / 2;
if (h->heaparr[parent]->priority >= value->priority) break;
h->heaparr[index] = h->heaparr[parent];
}
h->heaparr[index] = value;
}
void heap_display(struct heap* h) {
int i;
for(i=0; i<h->count; ++i) {
node_t* n = h->heaparr[i];
printf("priority = %d", n->priority);
printf("\n");
drawBoard( n->board, 0 );
}
}
node_t* heap_delete(struct heap* h)
{
node_t* removed;
node_t* temp = h->heaparr[--h->count];
if ((h->count <= (h->size + 2)) && (h->size > initial_size))
{
h->size -= 1;
h->heaparr = realloc(h->heaparr, sizeof(node_t) * h->size);
if (!h->heaparr) exit(-1); // Exit if the memory allocation fails
}
removed = h->heaparr[0];
h->heaparr[0] = temp;
if(temp == removed) h->heaparr[0] = NULL;
max_heapify(h->heaparr, 0, h->count);
return removed;
}
void emptyPQ(struct heap* pq) {
while(pq->count != 0) {
node_t* n = heap_delete(pq);
free(n);
//printf("<<%d", heap_delete(pq));
}
}
uint8_t scheme=0;
// i = row, j = col
uint32_t getTile( uint8_t board[SIZE][SIZE], unsigned i, unsigned j){
return (uint32_t)1<<board[j][i];
}
void getColor(uint8_t value, char *color, size_t length) {
uint8_t original[] = {8,255,1,255,2,255,3,255,4,255,5,255,6,255,7,255,9,0,10,0,11,0,12,0,13,0,14,0,255,0,255,0};
uint8_t blackwhite[] = {232,255,234,255,236,255,238,255,240,255,242,255,244,255,246,0,248,0,249,0,250,0,251,0,252,0,253,0,254,0,255,0};
uint8_t bluered[] = {235,255,63,255,57,255,93,255,129,255,165,255,201,255,200,255,199,255,198,255,197,255,196,255,196,255,196,255,196,255,196,255};
uint8_t *schemes[] = {original,blackwhite,bluered};
uint8_t *background = schemes[scheme]+0;
uint8_t *foreground = schemes[scheme]+1;
if (value > 0) while (value--) {
if (background+2<schemes[scheme]+sizeof(original)) {
background+=2;
foreground+=2;
}
}
snprintf(color,length,"\033[38;5;%d;48;5;%dm",*foreground,*background);
}
void drawBoard(uint8_t board[SIZE][SIZE], uint32_t score) {
uint8_t x,y;
char color[40], reset[] = "\033[m";
printf("\033[H");
printf("2048.c %17d pts\n\n",score);
for (y=0;y<SIZE;y++) {
for (x=0;x<SIZE;x++) {
getColor(board[x][y],color,40);
printf("%s",color);
printf(" ");
printf("%s",reset);
}
printf("\n");
for (x=0;x<SIZE;x++) {
getColor(board[x][y],color,40);
printf("%s",color);
if (board[x][y]!=0) {
char s[8];
snprintf(s,8,"%u",(uint32_t)1<<board[x][y]);
uint8_t t = 7-strlen(s);
printf("%*s%s%*s",t-t/2,"",s,t/2,"");
} else {
printf(" · ");
}
printf("%s",reset);
}
printf("\n");
for (x=0;x<SIZE;x++) {
getColor(board[x][y],color,40);
printf("%s",color);
printf(" ");
printf("%s",reset);
}
printf("\n");
}
printf("\n");
printf(" ←,↑,→,↓ or q \n");
printf("\033[A"); // one line up
}
uint8_t findTarget(uint8_t array[SIZE],uint8_t x,uint8_t stop) {
uint8_t t;
// if the position is already on the first, don't evaluate
if (x==0) {
return x;
}
for(t=x-1;t>=0;t--) {
if (array[t]!=0) {
if (array[t]!=array[x]) {
// merge is not possible, take next position
return t+1;
}
return t;
} else {
// we should not slide further, return this one
if (t==stop) {
return t;
}
}
}
// we did not find a
return x;
}
bool slideArray(uint8_t array[SIZE], uint32_t* score) {
bool success = false;
uint8_t x,t,stop=0;
for (x=0;x<SIZE;x++) {
if (array[x]!=0) {
t = findTarget(array,x,stop);
// if target is not original position, then move or merge
if (t!=x) {
// if target is zero, this is a move
if (array[t]==0) {
array[t]=array[x];
} else if (array[t]==array[x]) {
// merge (increase power of two)
array[t]++;
// increase score
(*score)+=(uint32_t)1<<array[t];
// set stop to avoid double merge
stop = t+1;
}
array[x]=0;
success = true;
}
}
}
return success;
}
void rotateBoard(uint8_t board[SIZE][SIZE]) {
uint8_t i,j,n=SIZE;
uint8_t tmp;
for (i=0; i<n/2; i++) {
for (j=i; j<n-i-1; j++) {
tmp = board[i][j];
board[i][j] = board[j][n-i-1];
board[j][n-i-1] = board[n-i-1][n-j-1];
board[n-i-1][n-j-1] = board[n-j-1][i];
board[n-j-1][i] = tmp;
}
}
}
bool moveUp(uint8_t board[SIZE][SIZE], uint32_t* score) {
bool success = false;
uint8_t x;
for (x=0;x<SIZE;x++) {
success |= slideArray(board[x], score);
}
return success;
}
bool moveLeft(uint8_t board[SIZE][SIZE], uint32_t* score) {
bool success;
rotateBoard(board);
success = moveUp(board, score);
rotateBoard(board);
rotateBoard(board);
rotateBoard(board);
return success;
}
bool moveDown(uint8_t board[SIZE][SIZE], uint32_t* score) {
bool success;
rotateBoard(board);
rotateBoard(board);
success = moveUp(board, score);
rotateBoard(board);
rotateBoard(board);
return success;
}
bool moveRight(uint8_t board[SIZE][SIZE], uint32_t* score) {
bool success;
rotateBoard(board);
rotateBoard(board);
rotateBoard(board);
success = moveUp(board, score);
rotateBoard(board);
return success;
}
uint8_t countEmpty(uint8_t board[SIZE][SIZE]) {
uint8_t x,y;
uint8_t count=0;
for (x=0;x<SIZE;x++) {
for (y=0;y<SIZE;y++) {
if (board[x][y]==0) {
count++;
}
}
}
return count;
}
bool findPairDown(uint8_t board[SIZE][SIZE]) {
bool success = false;
uint8_t x,y;
for (x=0;x<SIZE;x++) {
for (y=0;y<SIZE-1;y++) {
if (board[x][y]==board[x][y+1]) return true;
}
}
return success;
}
bool gameEnded(uint8_t board[SIZE][SIZE]) {
bool ended = true;
if (countEmpty(board)>0) return false;
if (findPairDown(board)) return false;
rotateBoard(board);
if (findPairDown(board)) ended = false;
rotateBoard(board);
rotateBoard(board);
rotateBoard(board);
return ended;
}
void addRandom(uint8_t board[SIZE][SIZE]) {
static bool initialized = false;
uint8_t x,y;
uint8_t r,len=0;
uint8_t n,list[SIZE*SIZE][2];
if (!initialized) {
srand(time(NULL));
initialized = true;
}
for (x=0;x<SIZE;x++) {
for (y=0;y<SIZE;y++) {
if (board[x][y]==0) {
list[len][0]=x;
list[len][1]=y;
len++;
}
}
}
if (len>0) {
r = rand()%len;
x = list[r][0];
y = list[r][1];
n = (rand()%10)/9+1;
board[x][y]=n;
}
}
void initBoard(uint8_t board[SIZE][SIZE], uint32_t* score) {
uint8_t x,y;
for (x=0;x<SIZE;x++) {
for (y=0;y<SIZE;y++) {
board[x][y]=0;
}
}
addRandom(board);
addRandom(board);
*score = 0;
drawBoard(board,*score);
}
/**
* Given a board configuration, apply action, and return the updated board and score
*/
bool execute_move_t( uint8_t board[SIZE][SIZE], uint32_t* score, move_t move){
bool success = false;
switch(move)
{
case left: // left arrow
success = moveLeft(board, score); break;
case right: // right arrow
success = moveRight(board, score); break;
case up: // up arrow
success = moveUp(board, score); break;
case down: // down arrow
success = moveDown(board, score); break;
default: success = false;
}
return success;
}
