///////////////////////////////////
// Class of CNIM for playing "nim"
// Copyright (c) by Ysama, 2021
///////////////////////////////////
/*
【ルール】
（１）5列の5個、4個、3個、2個、1個のコイン群をテーブルに置き、
（２）先手、後手が一回に、一つの列から、1個以上のコインを取ってゆき、
（３）最後のコインを取ることになった方が負け
nimの双対ゲーム（https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A0）
*/

#include	<vector>
using namespace std;

//CCOINSクラスヘッダー
#include	"CCOINSW.h"

////////////////////////
//CNIMクラスヘッダー
////////////////////////
class CNIM : public CCOINS {
private:
	//メンバー変数
	vector <unsigned int> m_GameProcess;	//対戦毎の手の推移を記録
	vector <unsigned int> m_CoinsDB;		//対戦状態の記録用DB
	vector <unsigned int>::iterator m_Itr;	//m_CoinsDB用イテレーター
	unsigned int m_Record;				//対戦状態の記録用変数
	//m_Record = 0000:0000（16進数4バイト）
	//			 ①②　③
	//①評価フラグ（1バイト）0－未定、1－採用、2－忌避
	//②列数（上位4bits）→0000:0000←コイン5個の列数（2進数2バイト－16bits）
	//③コイン数区分による列数内訳	0000:0000:0000:0000（2進数2バイト－16bits）
	//(下位2バイト)					4個　3個　2個　1個
public:
	//メンバー関数
	CNIM();						//コンストラクター
	~CNIM();					//デストラクター
	void InitGame();			//ゲームの初期化
	bool IsGameOver();			//勝敗の評価および記録
	bool CheckCoins(unsigned int);	//unsigned intデータのチェック（TRUE－必勝形、FALSE－必敗形）
	bool EvalTake();			//評価して手を打つ
	bool Eval();				//コイン状況に基づく勝敗評価（TRUE－必勝形、FALSE－必敗形））
	bool ExpTake();				//経験から手を打つ
	void SetRecord(int);		//m_Coinsの状態をm_Recordに記録する
	void Register(unsigned int, bool);	//手の登録（引数：登録データ、TRUE－忌避、FALSE－採用）
	bool Search(unsigned int, int&);	//手の検索（あればTRUEで引数に評価が入る、なければFALSE）
	int CoinsCmp();				//手の比較
	int DBSize();				//DBのデータ数を返す
	bool CoinsWrite(char*);		//DBデータの書き込み
	bool CoinsRead(char*);		//DBデータの読み込み
};

//コンストラクター
CNIM::CNIM() {

	//m_CoinsDBの読み込み（ファイル名（固定）："Nim.dat"）
	//CoinsRead("Nim.dat");
	CoinsRead("Nim.dat");
}

//デストラクター
CNIM::~CNIM() {

	//m_CoinsDBの書き込み（ファイル名（固定）："Nim.dat"）
	//CoinsWrite("Nim.dat");
	CoinsWrite("Nim.dat");
}

//ゲームの初期化
void CNIM::InitGame() {

	//CCOINSの初期化
	Init();
	//Vector変数を初期化
	m_GameProcess.clear();
}

//勝敗の評価および記録
bool CNIM::IsGameOver() {

	int result = IsOver();					//勝敗判定関数IsOver（勝負中-0または敗者1、2）
	if(result) {							//勝敗がついたならば
	//1列だけの場合や2列で一方が1の必勝形の場合は登録不要なので
	//その確認を行い、その一つ前の手（必勝形に導くので採用(1)）を取得する
		int dmy;
		m_Itr = m_GameProcess.end() - 1;
		auto last = *m_Itr;
		//1行だけなら
		while((last & 0x00F00000) == 0x00100000) {
			//更にひとつ前の登録記録へ遡る
			last = *(--m_Itr);
		}
		//2行で
		while((last & 0x00F00000) == 0x00200000) {
			//少なくとも一方が1なら
			if((last & 0x0000000F) > 0) {
				//ひとつ前の登録記録へ遡る
				last = *(--m_Itr);
			}
			else
				break;						//1が無ければ先に進む
		}
		if(!Search(last, dmy)) {			//同じコイン状況が無ければ
			Register(last, CheckCoins(last));	//一手前のコイン状況を登録
		}
		return TRUE;
	}
	else {									//未勝敗ならば、勝負中(0)で記録
		SetRecord(0);						//m_Recordに最新手を更新
		m_GameProcess.push_back(m_Record);	//m_GameProcessへ記録する
		return FALSE;
	}
}

//手の評価（必勝形－TRUE、必敗形－FALSE）
//（Eval関数と平仄を合わせる）
bool CNIM::CheckCoins(unsigned int data) {

	//5列のコイン数の排他的論理和
	//但し、コイン数がすべて1の場合は逆の結果となる
	int d = ((data & 0x000F0000) >> 16) * 5;				//5個の列数
	int flag = (data & 0x000F0000) >> 16;
	for(int i = 0; i < ((data & 0x0000F000) >> 12); i++)	//4個の列数
		d ^= 4;
	flag += (data & 0x0000F000) >> 12;
	for(int i = 0; i < ((data & 0x00000F00) >> 8); i++)		//3個の列数
		d ^= 3;
	flag += (data & 0x00000F00) >> 8;
	for(int i = 0; i < ((data & 0x000000F0) >> 4); i++)		//2個の列数
		d ^= 2;
	flag += (data & 0x000000F0) >> 4;
	for(int i = 0; i < (data & 0x0000000F); i++)			//1個の列数
		d ^= 1;
	if(flag > 0)	//2個以上の列数が一つでもあれば
		return d;	//必勝形－TRUE、必敗形－FALSE
	else			//データがすべて1または0であれば
		return !d;	//必勝形－FALSE、必敗形－TRUE
}

//評価して手を打つ
bool CNIM::EvalTake() {

	int col[5], i, j;
	for(i = 0, j = 0; i < 5; i++) {		//列配列に0以外の列を入れる
		if(m_Coins[i])
			col[j++] = i;
	}
	//以下のcase 1とcase 2の明らかな勝利手は評価以前に確定
	switch(j) {
	case 1:								//1列だけの場合
		if(m_Coins[col[0]] == 1)		//1なら既に負け（手を打てない）
			break;
		else {
			m_Coins[col[0]] = 1;		//1を残してすべて取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}
	case 2:								//2列の場合
		if(m_Coins[col[0]] == 1) {		//一方が1ならば、
			m_Coins[col[1]] = 0;		//他方のすべてのコインを取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}
		else if(m_Coins[col[1]] == 1) {	//他方が1ならば、
			m_Coins[col[0]] = 0;		//一方のすベてのコインを取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}								//1でない場合はdefault処理へ
	default:							//それ以外の場合
		int coins;						//データ一時保存用変数
		for(i = 0; i < j; i++) {
			coins = m_Coins[col[i]];	//m_Coins[col[i]の値を保存する
			for(int k = 1; k <= coins; k++) {	//1から自分のコイン数迄
				m_Coins[col[i]] = coins - k;	//コインを取った想定を行い、
				if(!Eval()) {					//相手に不利であれば確定する
					m_Player = 3 - m_Player;	//先手、後手の交代
					return TRUE;		//手を打てた
				}
			}
			m_Coins[col[i]] = coins;	//元に戻す
		}
		break;
	}
	return FALSE;						//m_Player（自分）が手を打てない（投了）
}

//コイン状況に基づく勝敗評価（TRUE－必勝形、FALSE－必敗形）
//（CheckCoins関数と平仄を合わせる）
//すべての列について排他的論理和を取る
//例：0, 0, 2, 2, 0 → 排他的論理和は0（必敗形）
//但し、0でない列が1だけの場合は例外となる
//例：0, 0, 1, 1, 0 → 排他的論理和は0だが、必勝形となっている
bool CNIM::Eval() {

	int d;
	bool flag = FALSE;
	for(int i = 0; i < 5; i++) {
		if(!i)					//i == 0でコイン数を代入
			d = m_Coins[i];
		else					//以降は排他的論理和を取る
			d ^= m_Coins[i];
		if(m_Coins[i] > 1)		//コイン数が1以上であれば
			flag = TRUE;		//flagは真
	}
	if(flag)					//いずれかの列のコイン数が1以上だったら
		return d;				//排他的論理和
	else						//列のコイン数すべてが1または0だったら
		return !d;				//排他的論理和の逆
}

//経験から手を打つ
bool CNIM::ExpTake() {

	//列配列に0以外の列を入れる
	int col[5], i, j;
	for(i = 0, j = 0; i < 5; i++) {
		if(m_Coins[i])
			col[j++] = i;
	}
	//CoinsDBの'2'（禁忌）に該当した手を入れるテーブル
	char TabooTable[5][5] = {0};		//[列][個数]ゼロ初期化
	int TTCounter = 0;					//TabooTable登録数
	//以下のcase 1とcase 2の明らかな勝利手は評価以前に確定
	switch(j) {
	case 1:								//1列だけの場合
		if(m_Coins[col[0]] == 1)		//1なら既に負け（手を打てない）
			break;
		else {
			m_Coins[col[0]] = 1;		//1を残してすべて取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}
	case 2:								//2列の場合
		if(m_Coins[col[0]] == 1) {		//一方が1ならば、
			m_Coins[col[1]] = 0;		//他方のすべてのコインを取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}
		else if(m_Coins[col[1]] == 1) {	//他方が1ならば、
			m_Coins[col[0]] = 0;		//一方のすベてのコインを取る
			m_Player = 3 - m_Player;	//先手、後手の交代
			return TRUE;				//手を打てた
		}								//1でない場合はdefault処理へ
	default:							//それ以外の場合
		int coins, v;					//データ一時保存および評価用変数
		for(i = 0; i < j; i++) {
			coins = m_Coins[col[i]];		//m_Coins[col[i]の値を保存する
			for(int k = 1; k <= coins; k++) {	//1から自分のコイン数迄
				m_Coins[col[i]]= coins - k;		//コインを取った想定を行い、
				SetRecord(0);					//Searchの為、m_Recordにコイン状況を記録
				if(Search(m_Record, v)) {		//同じ手があり、その評価が「採用（1）」であれば
					if(v == 1) {				//その評価が「採用（1）」であれば
						m_Player = 3 - m_Player;	//先手、後手の交代
						return TRUE;			//手を打てた
					}
					else if(v == 2) {			//その評価が「忌避（2）」であれば
						TabooTable[col[i]][coins - k] = 1;	//禁忌テーブルに登録する
						TTCounter++;						//禁忌テーブル登録数
					}
				}						//見つからなければそのままにする
			}
			m_Coins[col[i]] = coins;	//元に戻す
		}
		/* 注意：すべての候補がTabooTableに該当すると無限ループになるので、
		   安全の為、乱数による手決めが忌避テーブル登録回数 + 1以上になった場合、
		   投了させます */
		do {
			i = rand() % j;			//値を持つ列を乱数で抽出
			//m_Coins[col[i]]のコイン数から、乱数で定めた値（1～そのコイン数）を差し引く
			v = m_Coins[col[i]] - ((rand() % m_Coins[col[i]]) + 1);
			--TTCounter;
			if(TTCounter < 0)		//（登録回数 + 1）なのでこれ以上やっても全て忌避の筈
				break;
		} while(TabooTable[i][v]);	//禁忌テーブルに引っかかれば乱数をやり直す
		m_Coins[col[i]] = v;
		m_Player = 3 - m_Player;	//先手、後手の交代
		return TRUE;				//手を打てた
	}
	return FALSE;					//打つ手がなく、「投了」
}

void CNIM::SetRecord(int result) {	//m_Coinsの状態をm_Recordに記録する

	int ln = 0, coins5 = 0, coins4 = 0, coins3 = 0, coins2 = 0, coin1 = 0;
	for(int i = 0; i < 5; i++) {
		if(m_Coins[i]) {
			ln++;
			switch(m_Coins[i]) {
			case 5:
				coins5++;
				break;
			case 4:
				coins4++;
				break;
			case 3:
				coins3++;
				break;
			case 2:
				coins2++;
				break;
			case 1:
				coin1++;
				break;
			default:
				break;
			}
		}
	}
	m_Record = result;			//先頭は0－未定、1－採用、2－忌避
	m_Record <<= 4;				//4 bits上位へシフト
	m_Record |= ln;				//0以外の数値を持つ列数
	m_Record <<= 4;				//8 bits上位へシフト
	m_Record |= (char)coins5;	//5つのコインの列数
	m_Record <<= 4;				//8 bits上位へシフト
	m_Record |= (char)coins4;	//4つのコインの列数
	m_Record <<= 4;				//4 bits上位へシフト
	m_Record |= (char)coins3;	//3つのコインの列数
	m_Record <<= 4;				//4 bits上位へシフト
	m_Record |= (char)coins2;	//2つのコインの列数
	m_Record <<= 4;				//4 bits上位へシフト
	m_Record |= (char)coin1;	//1つのコインの列数
}

//手の登録
void CNIM::Register(unsigned int data, bool flag) {

	//相手に渡す手の評価なので
	if(flag)		//「忌避」（flagがTRUE）
		data |= 0x02000000;
	else			//「採用」（flagがFALSE）
		data |= 0x01000000;
	m_CoinsDB.push_back(data);
}

//手の検索
bool CNIM::Search(unsigned int data, int& value) {

	unsigned int cmp;	//比較用変数（data & 0x0000FFFFと比較する）
	for(m_Itr = m_CoinsDB.begin(); m_Itr != m_CoinsDB.end(); m_Itr++) {
		cmp = *m_Itr & 0x000FFFFF;					//下位2バイト半のコイン状況で
		if(cmp == (data & 0x000FFFFF)) {			//dataと比較する
			value = (*m_Itr & 0xFF000000) >> 24;	//同一であればその評価を取得する
			return TRUE;
		}
	}
	return FALSE;
}

//DBのデータ数を返す
int CNIM::DBSize() {

	return m_CoinsDB.size();
}

bool CNIM::CoinsWrite(char* fn) {

	int num = DBSize();
	unsigned int data;
	HANDLE hFile = CreateFile(fn, GENERIC_WRITE,
				FILE_SHARE_WRITE, NULL,
				OPEN_ALWAYS, NULL, NULL);	//ファイルを書込でオープン
	if(hFile != INVALID_HANDLE_VALUE) {		//オープンできたか
		DWORD dwWrite;
		//先ずintでデータ数を書き込む
		WriteFile(hFile, &num, sizeof(int), &dwWrite, NULL);
		m_Itr = m_CoinsDB.begin();
		//次にm_Coinsの配列を書き込む
		for(int i = 0; i < num; i++, m_Itr++) {
			data = *m_Itr;
			WriteFile(hFile, &data, sizeof(data), &dwWrite, NULL);
		}
		CloseHandle(hFile);					//ファイルのクローズ
		return TRUE;
	}
	else
		return FALSE;
}

bool CNIM::CoinsRead(char* fn) {

	int num;
	unsigned int data;
	HANDLE hFile = CreateFile(fn, GENERIC_READ,
				FILE_SHARE_READ, NULL,
				OPEN_EXISTING, NULL, NULL);	//ファイルを読込でオープン
	if(hFile != INVALID_HANDLE_VALUE) {		//オープンできたか
		m_CoinsDB.clear();					//m_CoinsDBのデータを空にする
		DWORD dwRead;
		//先ずint numにデータ数を読み込む
		ReadFile(hFile, &num, sizeof(int), &dwRead, NULL);
		for(int i = 0; i < num; i++) {
			ReadFile(hFile, &data, sizeof(data), &dwRead, NULL);
			m_CoinsDB.push_back(data);
		}
		CloseHandle(hFile);					//ファイルのクローズ
		return TRUE;
	}
	else
		return FALSE;
}
