#include <cstdio>
#include <memory.h>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cmath>
#include <omp.h>
#include <atomic>
#include "chesspi.h"

static const unsigned int table_cost[16] = {1000000,150,150,150,150,150,150,500,500,150,150,100,100,100,100,100};
float calc_cost(const int coordx[/*32*/], const int coordy[/*32*/],const int alive[/*32*/],const int killed,const int idx)
{

	//	 * 帅士士相相马马车车炮炮兵兵兵兵兵  將仕仕象象馬馬車車砲砲卒卒卒卒卒

	assert(idx >= 16);

	unsigned int rescost = table_cost[idx%16];
	//位置加权
	switch (idx % 16) {
	//相士双全时击杀价值高
	case 1:
	case 2:
	case 3:
	case 4:
		if (alive[(idx-1)/2*2+1] || alive [(idx-1)/2*2+2])
			rescost *= 2;
		break;
	//马战线挺进，以及后期击杀价值高
	case 5:
	case 6:
		if (idx<16 )
			rescost *= 1+(coordy[idx]/3.0);
		else
			rescost *= 1+((11-coordy[idx])/3.0);
		rescost *= 1 + killed / 4.0;
		break;
	//车战线击杀高
	case 7:
	case 8:
		if (idx<16 )
			rescost *= 1+(coordy[idx]/3.0);
		else
			rescost *= 1+((11-coordy[idx])/3.0);
		break;
	//炮前期击杀高
	case 9:
	case 10:
		if (idx<16 )
			rescost *= 1+(coordy[idx]/3.0);
		else
			rescost *= 1+((11-coordy[idx])/3.0);
		rescost *= 1 + (32 - killed) / 4.0;
		break;
	//卒过河击杀高
	case 11:
	case 12:
	case 13:
	case 14:
	case 15:
		if (idx<16 )
			rescost *= coordy[idx]>5?4:1;
		else
			rescost *= coordy[idx]<6?4:1;
		//当头卒价值高
		if (coordx[idx]==5 && (coordy[idx]==4 || coordy[idx]==7))
			rescost *=10;
		break;
	default:
		break;
	}



	return rescost;
}

std::vector<chess_node> build_tree(const chess_node & root, const int side,const std::vector<chess_node> & history)
{
	std::vector<chess_node> tree;
	std::unordered_set <std::string> dict;
	for (const chess_node & n: history)
		dict.insert(node2hash(n.coords,n.alive));
	tree.push_back(root);
	tree[0].side = side % 2;
	tree[0].depth = 0;

	size_t curr_i = 0;
	size_t max_nodes = 1024*1024*4;
	while (tree.size()<=max_nodes && curr_i<tree.size())
	{
		const size_t ts = tree.size();
		const int cores = omp_get_num_procs();
		std::vector<std::vector<chess_node> > vec_appends;
		for (int i=0;i<cores;++i)
			vec_appends.push_back(std::vector<chess_node>());
		std::atomic<int> new_appends (0);
#pragma omp parallel for
		for (int i=curr_i;i<ts;++i)
		{
			if (new_appends + ts >=max_nodes)
				continue;
			const unsigned char clock = tree[i].depth;
			const int tid = omp_get_thread_num();
			if ((tree[i].alive & 0x00010001)==0x00010001)
			{
				const int curr_side = (side + clock) % 2;
				std::vector<chess_node> next_status =
						expand_node(tree[i],curr_side);

				const size_t sz = next_status.size();
				//有无结束
				bool ppz = false;
//				for (size_t j=0;j<sz && !ppz;++j)
//				{
//					if (next_status[j].jump_cost[0]==table_cost[0] || next_status[j].jump_cost[1]==table_cost[0])
//						ppz = true;
//				}
				for (size_t j=0;j<sz;++j)
				{
					if (ppz && next_status[j].jump_cost[0]<table_cost[0] &&  next_status[j].jump_cost[1]<table_cost[0] )
						continue;
					std::string ha = node2hash(next_status[j].coords,next_status[j].alive);
					bool needI = false;
#pragma omp critical
					{
						if (dict.find(ha)==dict.end())
						{
							needI = true;
							dict.insert(ha);
						}
					}
					if (needI)
					{
						next_status[j].parent = i;
						next_status[j].side = curr_side;
						next_status[j].depth = clock+1;
						vec_appends[tid].push_back(next_status[j]);
						++tree[i].leaves;
						++new_appends;
					}
				}
			}
		}
		for (int i=0;i<cores;++i)
		{
			if (vec_appends[i].size())
				std::move(vec_appends[i].begin(),vec_appends[i].end(),std::back_inserter(tree));
		}
		curr_i += (ts - curr_i);
	}

	//printf ("\nDepth = %d\n",tree.rbegin()->depth);

	return tree;
}

size_t judge_tree(std::vector<chess_node> & tree)
{
	const size_t total_nodes = tree.size();
	if (total_nodes<2)
		return 0;
	int side = tree[0].side;
	size_t i = total_nodes - 1;
	while (i > 0)
	{
		if (tree[i].side==0)
		{
			float ratio = sqrt((tree[i].jump_cost[1]+1) / (tree[i].jump_cost[0]+1)/ sqrt(tree[i].jump_cost[0]+1));
			tree[i].weight = ratio;
		}
		else
		{
			float ratio = sqrt((tree[i].jump_cost[0]+1) / (tree[i].jump_cost[1]+1)/ sqrt(tree[i].jump_cost[1]+1));
			tree[i].weight = ratio;
		}
		size_t parent = tree[i].parent;
		tree[parent].jump_cost[0] += tree[i].jump_cost[0] * tree[i].weight/tree[i].depth/tree[i].depth;
		tree[parent].jump_cost[1] += tree[i].jump_cost[1] * tree[i].weight/tree[i].depth/tree[i].depth;
		--i;
	}

	size_t p = 1;
	float max_v = 0;
	int max_p = 1;
	while (p<total_nodes)
	{
		if (tree[p].parent)
			break;
		//float v = (tree[p].jump_cost[1-side]+1)/(tree[p].jump_cost[side]);
		float v = (tree[p].weight);
		if (v > max_v)
		{
			max_v = v;
			max_p = p;
		}
		++p;
	}
	return max_p;
}