TMCTF2015-prog500.cpp

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

typedef unsigned int uint_t;
typedef long double real_t;

uint_t hashParam[11];

int cardCount;
int cardLeft[11];

struct TCardDesk{
	int cards[11];
	bool changed;
	int _score;
	uint_t hash;
	int count;
	TCardDesk(){
		reset();
	}
	inline void reset(){
		changed = false;
		_score = 0;
		hash = 0;
		count = 0;
		memset(cards,0,sizeof(cards));
	}
	inline void addCard(int score){
		count++;
		cardCount--;
		cards[score]++;
		cardLeft[score]--;
		hash += hashParam[score];
		changed = true;
	}
	inline void removeCard(int score){
		count--;
		cardCount++;
		cards[score]--;
		cardLeft[score]++;
		hash -= hashParam[score];
		changed = true;
	}
	inline int score(){
		if(!changed) return _score;
		changed = false;
		int r=0;
		for(int i=1;i<=10;i++) r+=cards[i]*i;//scoring for all cards
		for(int i=cards[1];i>0 && r<=11;i--) r+=10;//scoring for ace
		return _score = r;
	}
};

TCardDesk P, D;

void reset(){
	for(int i=1;i<=9;i++) cardLeft[i]=8;//A to 9
	cardLeft[10]=4*8;//10,J,Q,K
	cardCount = 8*9+4*8;
	P.reset();D.reset();
}

bool hashUniqueDFS(set<uint_t>& s, TCardDesk& d, int lastUse){
	if(d.score()>21) return false;
	if(s.find(d.hash)!=s.end()){
		printf("Hash conflict\n");
		exit(-1);
	}
	s.insert(d.hash);
	for(int i=lastUse;i<=10;i++){
		if(cardLeft[i]>0){
			d.addCard(i);
			hashUniqueDFS(s,d,i);
			d.removeCard(i);
		}
	}
	return true;
}

void hashUnique(){
	set<uint_t> s;
	reset();
	hashUniqueDFS(s,P,1);
	printf("Hash check OK, total size: %lu.\n",s.size());
}

real_t skipFactor = 1e-15;

real_t dealerTurn(real_t factor){
	if(D.score()>21) return 1;
	if(D.score()>=17) return D.score()>=P.score()?0:1;
	
	if(factor<skipFactor) return 0;
	
	static map<pair<uint_t,uint_t>, real_t> cache;
	auto it = cache.find(make_pair(P.hash,D.hash));
	if(it!=cache.end()) return it->second;
	
	real_t total_deal_score = 0;
	int currentCardCount = cardCount;
	
	for(int i=1;i<=10;i++){
		if(cardLeft[i]>0){
			D.addCard(i);
			total_deal_score += dealerTurn(factor*(cardLeft[i]+1)/currentCardCount) * (cardLeft[i]+1);//+1 due to addCard
			D.removeCard(i);
		}
	}
	
	return cache[make_pair(P.hash,D.hash)] = total_deal_score / cardCount;
}

real_t playerTurn(real_t factor){
	if(factor<skipFactor) return 0;
	
	if(P.score()>21) return 0;
	
	static map<uint_t, real_t> cache;
	auto it = cache.find(P.hash);
	if(it!=cache.end()) return it->second;
	
	//first case: DEAL
	real_t total_deal_score = 0;
	int currentCardCount = cardCount;
	for(int i=1;i<=10;i++){
		if(cardLeft[i]>0){
			P.addCard(i);
			total_deal_score += playerTurn(factor*(cardLeft[i]+1)/currentCardCount) * (cardLeft[i]+1);//+1 due to addCard
			P.removeCard(i);
		}
	}
	
	real_t deal_score = total_deal_score / currentCardCount;
	
	//second case: STAND
	real_t stand_score = dealerTurn(factor);
	
	return cache[P.hash] = max(deal_score, stand_score);
}

int main(int argc, char *argv[]) {
	hashParam[0]=1;
	for(uint_t i=1;i<=10;i++) hashParam[i] = hashParam[i-1]*97;
	
	hashUnique();
	
	reset();
	P.addCard(1);P.addCard(2);
	D.addCard(3);
	
	printf("TMCTF{HIT:%.4Lf:STAND:%.4Lf}",playerTurn(1.),dealerTurn(1.));
	
	return 0;
}