Skip to content

Instantly share code, notes, and snippets.

@vhqtvn vhqtvn/TMCTF2015-prog500.cpp Secret
Created Sep 28, 2015

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.