2048AI

/*
 * 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;
}