Instantly share code, notes, and snippets.

tkzw21/2048AI Created Aug 26, 2014

 /* * AI.cpp * * Created on: 2014/06/21 * Author: tkzw_21 */ #include #include #include #include #include #include #include #include #include #include #include #include #include #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 search(int n, int depth, int dir, int board[][4]) { int work[4][4]; pair p; if (n == depth) { p.first = dir; p.second = evalBoard(board); return p; } else if (n % 2 != 0) { pair 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 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 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 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; }
to join this conversation on GitHub. Already have an account? Sign in to comment