const int FIVE_SCORE = 1000; // continuous 5
const int OPEN_FOUR_SCORE = 250; // open 4
const int CLOSE_FOUR_SCORE = 60; // half-open 4, jump 4
const int OPEN_THREE_SCORE = 50; // open 3, jump 3
const int OTHER_SCORE = 3; // half-open 3 or open 2 or jump 2

#define SIZE 15

#include "MCTS.h"
#include "game.h"

class CGoBangDlg : public CDialogEx
{
public:
	CGoBangDlg(CWnd* pParent = nullptr);

#ifdef AFX_DESIGN_TIME
	enum { IDD = IDD_GOBANG_DIALOG };
#endif

protected:
	virtual void DoDataExchange(CDataExchange* pDX);
	bool IsPlaying = false;
	bool AIPlaying = false;
	bool NowColor;
	int ChessBoard[SIZE][SIZE];
	int index;
	CPoint order[SIZE * SIZE];
	int GetChessBoardColor(int ,int);
	void SetChessBoardColor(int ,int,int);
	void EndGame();
	void CleanChessBoard();
	void OpenFile(CString filename);
	int GetChessCount(int,int);
	int GetWinner();
	bool AI_step();
	bool Human_step(CPoint point);
	MCTS ai;
	Game g;

protected:
	HICON m_hIcon;

	virtual BOOL OnInitDialog();
	afx_msg void OnPaint();
	afx_msg HCURSOR OnQueryDragIcon();
	DECLARE_MESSAGE_MAP()
public:
	afx_msg void OnBnClickedStart();
	afx_msg void OnBnClickedQuit();
	afx_msg void OnLButtonUp(UINT nFlags, CPoint point);
	afx_msg BOOL OnSetCursor(CWnd* pWnd, UINT nHitTest, UINT message);
	afx_msg void OnClose();
	afx_msg void OnBnClickedEndgame();
	afx_msg void OnBnClickedRepentance();
	afx_msg void OnBnClickedSave();
	afx_msg void OnBnClickedOpen();
	afx_msg void OnStartAIButtonClicked();
	afx_msg void OnBnClickedButtonAi();
};

class Board
{
public:
	enum Chess;
	enum ChessDirection;
	enum GridType;

	enum ChessPriority;
	Board();

	void Clear();

	bool IsWin(int id);
	bool IsLose(int id);
	void GetGridsByPriority(ChessPriority priority, array<uint8_t, GRID_NUM> &result, int &count);
	int CalcBoardScore(int side);

	void UpdatScoreInfo(int id, int turn);
	
	static int Coord2Id(int row, int col);
	static void Id2Coord(int id, int &row, int &col);
	static bool IsValidCoord(int row, int col);
	static void Direction2DxDy(ChessDirection direction, int &dx, int &dy);
	static int CalcDistance(int id1, int id2);

	static int hitCount;
	static int totalCount;

	uint8_t	keyGrid;
	array<char, GRID_NUM> grids;
	array<short, GRID_NUM> scoreInfo[2];
	array<array<int, GRID_NUM>, 4> keyInfo[2];
	array<char, GRID_NUM> gridCheckStatus;
	array<bool, E_GRID_TYPE_MAX> hasGridType;
	array<bool, E_PRIORITY_MAX + 1> hasPriority;

private:
	char GetGrid(int row, int col);
	bool SetGrid(int row, int col, char value);

	void InitKeyInfo();
	void UpdateKeyInfo(int row, int col);
	void UpdateScore(int row, int col, int rowX, int colX, ChessDirection direction, int side);
	void UpdateScoreOpt(int row, int col, ChessDirection direction, int side);
	void UpdateGridsInfo(int i0);
	void FindOtherGrids(int i0, int id, GridType type);
	static bool RestrictedMoveRule;
	static bool IsRestrictedMove(int id);
	static void InitLineScoreDict(); 
	static short CalcLineScore(array<char, 9> line);
	static array<int, LINE_ID_MAX> lineScoreDict;
	static bool isLineScoreDictReady;
	static array<array<int, GRID_NUM>, 4> keyInfoOrigin;
	static bool isKeyInfoOriginReady;
};

class GameBase
{
public:
	enum State;

	GameBase();
	void Init();
	bool PutChess(int id);
	int GetSide();
	void UpdateValidGrids();
	bool UpdateValidGridsExtra();
	int GetNextMove();
	int CalcBetterSide();

	Board board;
	int state;
	int turn;
	int lastMove;
	int validGridCount;
	array<uint8_t, GRID_NUM> validGrids;
};

class Game : private GameBase
{
public:

	int GetState() { return state; }
	int GetTurn() { return turn; }

	bool PutChess(int id);
	void Regret(int step = 2); // 默认为2，方便人悔棋顺便把AI下的删了
	void Reset();

	const vector<uint8_t>& GetRecord() { return record; }
	static int Str2Id(const string &str);
	static string Id2Str(int id);

private:
	void RebuildBoard();
	vector<uint8_t> record;
};

class TreeNode
{
public:
	TreeNode(TreeNode *p);
	void Clear();

	int visit;
	float value;
	float winRate;
	float expandFactor;
	int validGridCount;
	int gridLevel;
	GameBase *game;

	TreeNode *parent;
	list<TreeNode*> children;
	array<uint8_t, GRID_NUM> validGrids;
};

class MCTS
{
public:
	MCTS(int mode = 0);
	~MCTS();
	int Search(Game *state);

private:
	static void SearchThread(int id, int seed, MCTS *mcts, clock_t startTime);

	// 标准MCTS
	TreeNode* TreePolicy(TreeNode *node);
	TreeNode* ExpandTree(TreeNode *node);
	TreeNode* BestChild(TreeNode *node, float c);
	float DefaultPolicy(TreeNode *node, int id);
	void UpdateValue(TreeNode *node, float value);

	// 魔改优化
	bool PreExpandTree(TreeNode *node);
	int CheckBook(GameBase *state);
	void ClearNodes(TreeNode *node);
	float CalcScore(const TreeNode *node, float expandFactorParent_c);
	TreeNode* NewTreeNode(TreeNode *parent);
	void RecycleTreeNode(TreeNode *node);
	void ClearPool();
	
	int maxDepth, fastStopSteps, fastStopCount;
	GameBase gameCache[THREAD_NUM_MAX];
	list<TreeNode*> pool;
	TreeNode *root;
	int mode;
};

const float Cp = 2.0f;  // UCB值中的Cp
const float SEARCH_TIME = 1.0f;   // 搜索时间上限
const int	EXPAND_THRESHOLD = 3;   // expand的阈值
const bool	ENABLE_MULTI_THREAD = true;   // 是否使用多线程，建议开启
const float	FAST_STOP_THRESHOLD = 0.1f;   // 剪枝
const float	FAST_STOP_BRANCH_FACTOR = 0.01f;
const bool	ENABLE_TRY_MORE_NODE = true; // 如果模拟太多，换一个点模拟
const int	TRY_MORE_NODE_THRESHOLD = 1000;