Create a gist now

Instantly share code, notes, and snippets.

@tkzw21 /2048AI
Created Aug 26, 2014

What would you like to do?
/*
* AI.cpp
*
* Created on: 2014/06/21
* Author: tkzw_21
*/
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cmath>
#include<utility>
#define CLEAR 2048
#define INF 100000
#define N 50
using namespace std;
bool equalBoard(int board1[][4], int board2[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board1[i][j] != board2[i][j])
return false;
}
}
return true;
}
void addTile(int work[][4], int r, int c, int scale) {
if (work[r][c] == 0)
work[r][c] = scale * 2;
return;
}
void moveTile(int work[][4], int dir) {
for (int c = 0; c <= 1; c++) {
if (dir == 2 || dir == 0 || (c == 0 && dir == 1)
|| (c == 1 && dir == 3))
continue;
int dr[4] = { 0, 1, 2, 3 };
int dc[][4] = { { 0, 1, 2, 3 }, { 3, 2, 1, 0 } };
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (work[dr[i]][dc[c][j]] == 0) {
for (int k = j + 1; k < 4; k++)
if (work[dr[i]][dc[c][k]] != 0) {
work[dr[i]][dc[c][j]] = work[dr[i]][dc[c][k]];
work[dr[i]][dc[c][k]] = 0;
j--;
break;
}
} else {
for (int k = j + 1; k < 4; k++) {
if (work[dr[i]][dc[c][j]] != work[dr[i]][dc[c][k]]
&& work[dr[i]][dc[c][k]] != 0)
break;
if (work[dr[i]][dc[c][j]] == work[dr[i]][dc[c][k]]) {
work[dr[i]][dc[c][j]] *= 2;
work[dr[i]][dc[c][k]] = 0;
break;
}
}
}
}
}
}
for (int r = 0; r <= 1; r++) {
if (dir == 1 || dir == 3 || (r == 0 && dir == 0)
|| (r == 1 && dir == 2))
continue;
int dc[4] = { 0, 1, 2, 3 };
int dr[][4] = { { 0, 1, 2, 3 }, { 3, 2, 1, 0 } };
for (int j = 0; j < 4; j++) {
for (int i = 0; i < 4; i++) {
if (work[dr[r][i]][dc[j]] == 0) {
for (int k = i + 1; k < 4; k++)
if (work[dr[r][k]][dc[j]] != 0) {
work[dr[r][i]][dc[j]] = work[dr[r][k]][dc[j]];
work[dr[r][k]][dc[j]] = 0;
i--;
break;
}
} else {
for (int k = i + 1; k < 4; k++) {
if (work[dr[r][i]][dc[j]] != work[dr[r][k]][dc[j]]
&& work[dr[r][k]][dc[j]] != 0)
break;
if (work[dr[r][i]][dc[j]] == work[dr[r][k]][dc[j]]) {
work[dr[r][i]][dc[j]] *= 2;
work[dr[r][k]][dc[j]] = 0;
break;
}
}
}
}
}
}
return;
}
void showBoard(int board[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
printf("%6d", board[i][j]);
}
cout << endl;
}
cout << endl;
}
bool judgeBoard(int board[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] == 0)
return true;
if (j < 3)
if (board[i][j] == board[i][j + 1]
|| board[j][i] == board[j + 1][i])
return true;
}
}
return false;
}
void addBoard(int board[][4]) {
int cnt = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] != 0)
cnt++;
else
break;
}
}
if (cnt == 16)
return;
int r, c, num;
while (1) {
r = rand() % 4, c = rand() % 4;
num = (rand() % 2 + 1) * 2;
if (board[r][c] == 0) {
board[r][c] = num;
break;
}
}
}
int evalBoard(int board[][4]) {
int ret = 0;
//1,2,4,8,16,32,64,128,256,512,1024,2048,4096
double mask[4][4] = { { 2, 0, 0, 0 }, { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 0,
0, 0, 0 } };
int empty = 0, sum = 0, Max = 0, sa = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
Max = max(Max, board[i][j]);
if (j > 0)
sa += abs(board[i][j] - board[i][j - 1]);
if (i > 0)
sa += abs(board[i][j] - board[i - 1][j]);
if (board[i][j] == 0)
empty += 1;
sum += mask[i][j] * board[i][j];
}
}
if (judgeBoard(board) == false)
return -1 * sa;
ret = sum;
return -1 * sa + sum;
}
void boardCpy(int work[][4], int board[][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
work[i][j] = board[i][j];
}
}
return;
}
pair<int, int> search(int n, int depth, int dir, int board[][4]) {
int work[4][4];
pair<int, int> p;
if (n == depth) {
p.first = dir;
p.second = evalBoard(board);
return p;
} else if (n % 2 != 0) {
pair<int, int> p2;
int value = INF, cnt = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 1; k <= 2; k++) {
boardCpy(work, board);
addTile(work, i, j, k);
if (equalBoard(board, work) && cnt != 31) {
cnt++;
continue;
}
p2 = search(n + 1, depth, dir, work);
if (p2.second < value) {
value = p2.second;
p = p2;
}
}
}
}
return p;
} else {
pair<int, int> p2;
int value = -100000, cnt = 0;
for (int i = 0; i < 4; i++) {
boardCpy(work, board);
moveTile(work, i);
if (equalBoard(work, board) && cnt != 3) {
cnt++;
continue;
}
p2 = search(n + 1, depth, i, work);
if (p2.second > value) {
value = p2.second;
p.first = i;
p.second = p2.second;
}
}
return p;
}
}
int main() {
//時間測定用変数
clock_t start;
//実際のゲーム表示,処理用配列
int board[4][4];
//連続結果格納
map<int, int> hash;
//連続時間
double sec = 0;
srand(time(0));
//ボードの初期状態
memset(board, 0, sizeof(board));
//開始時間を代入
start = clock();
addBoard(board);
while (judgeBoard(board)) {
static int cnt = 0;
//ボードに新しいタイルの追加
addBoard(board);
//空き数を数える
int empty = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (board[i][j] == 0)
empty++;
//探索深度
int depth = 3;
if (empty < 4)
depth = 4;
pair<int, int> p = search(0, depth * 2 - 1, 3, board);
int dir = p.first;
cout << cnt++ << "\t" << "direction=" << p.first << "\t" << "value="
<< p.second << endl;
//決めた方向へboardを動かす
moveTile(board, dir);
//ボードの表示
showBoard(board);
}
int Max = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
Max = max(Max, board[i][j]);
//結果の表示
cout << "Game Over!!" << endl;
cout << "Result : ";
//時間
printf("%.2fsec\n", (double) (clock() - start) / CLOCKS_PER_SEC);
cout << "Maximum Number = " << Max << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment