#include "hatpuzzle.h" #include #include #include using namespace std; const double EPSILON = .00001; int getHatConfigBit(int hatConfig, int n, int i) { return (hatConfig & (1 << (n - i - 1))) >> (n - i - 1); } int curViewFromHatConfig(int hatConfig, int n, int cur) { int bottomBits = hatConfig & ((1 << (n - cur - 1)) - 1); int topBits = hatConfig >> (n - cur); return bottomBits + (topBits << (n - cur - 1)); } // Returns what guesses a strategy will produce given a hat configuration. void strategyGuesses(const vector& strategy, int n, int hatConfig, vector& guesses) { guesses.reserve(n); int guessesPerPerson = 1 << (n - 1); for (int i = 0; i < n; ++i) { int curHatView = curViewFromHatConfig(hatConfig, n, i); guesses[i] = strategy[guessesPerPerson * i + curHatView]; } return; } void mutateStrategy(vector& strategy, double mutationProb) { for (vector::iterator it = strategy.begin(); it != strategy.end(); ++it) { if (((double) rand())/((double) RAND_MAX) < mutationProb) { Guess curGuess = *it; while (*it != curGuess) { *it = (Guess) (rand() % 3); } } } } vector breedParents(const vector& strat1, const vector& strat2, double mutationProb) { vector child; child.resize(strat1.size()); bool useFirstPartOf1 = (((double) rand())/((double) RAND_MAX) > .5); int divisionPoint = (int) ((((double) rand())/((double) RAND_MAX)) * strat1.size()); if (useFirstPartOf1) { copy(strat1.begin(), strat1.begin() + divisionPoint, child.begin()); copy(strat2.begin() + divisionPoint, strat2.end(), child.begin() + divisionPoint); } else { copy(strat2.begin(), strat2.begin() + divisionPoint, child.begin()); copy(strat1.begin() + divisionPoint, strat1.end(), child.begin() + divisionPoint); } mutateStrategy(child, mutationProb); return child; } vector preCalculateWeightedStrategy(const vector, double> >& generation, double totalScore) { vector toReturn; toReturn.reserve(generation.size() + 1); double accum = 0.0; toReturn.push_back(accum); for (vector, double> >::const_iterator it = generation.begin(); it != generation.end(); ++it) { accum += it->second; toReturn.push_back(accum); } return toReturn; } vector selectWeightedStrategy(const vector, double> >& generation, double totalScore, const vector& preCalc) { double r = (((double) rand())/((double) RAND_MAX)) * totalScore; double accum = 0.0; vector, double> >::const_iterator it; int i, low, high; for (low = -1, high = preCalc.size(); high-low > 1;) { i = (high + low) / 2; // See if we've found it. if (r < preCalc[i]) { if (preCalc[i-1] <= r) { return generation[i-1].first; } high = i; } else { low = i; } } /*for (it = generation.begin(); (it != generation.end() && accum < r); ++it) { accum += it->second; }*/ /*if (it == generation.end()) { --it; } return it->first;*/ return generation[i-1].first; } void breedGeneration(vector, double> >& generation, int n, double mutationProb) { vector > newGeneration; newGeneration.resize(generation.size()); // Sort the current generation by score. sort(generation.begin(), generation.end(), LessRight()); double scoreSum = 0.0; for (vector, double> >::const_iterator it = generation.begin(); it != generation.end(); ++it) { // cull out really low scores // Always take the first 60 of the generation, and then any scores above // .1, as long as they're not in the last 100 scores. if ((it - generation.begin() <= 60 || it->second > 0.1) && (generation.end() - it) > 100) { scoreSum += it->second; } } vector preCalc = preCalculateWeightedStrategy(generation, scoreSum); for (int i = 0; i < generation.size(); ++i) { vector parent1 = selectWeightedStrategy(generation, scoreSum, preCalc); vector parent2 = selectWeightedStrategy(generation, scoreSum, preCalc); newGeneration[i] = breedParents(parent1, parent2, mutationProb); } for (int i = 0; i < generation.size(); ++i) { generation[i].first = newGeneration[i]; generation[i].second = 0.0; } } double scoreStrategy(const vector& strategy, int n) { int successes = 0; int possible = 1 << n; vector guesses; for (int curHatConfig = 0; curHatConfig < possible; ++curHatConfig) { strategyGuesses(strategy, n, curHatConfig, guesses); bool allGuessesCorrect = true; bool haveGuessed = false; for (int i = 0; i < n; ++i) { if (guesses[i] != GuessNone) { haveGuessed = true; allGuessesCorrect = allGuessesCorrect && (guesses[i] == getHatConfigBit(curHatConfig, n, i)); if (!allGuessesCorrect) { break; } } } if (haveGuessed && allGuessesCorrect) { ++successes; } } return ((double) successes) / ((double) possible); //strategyGuesses(strategy, n, } Guess guessFromChar(const char& ch) { if (ch == 'B') { return GuessBlue; } else if (ch == 'R') { return GuessRed; } else { return GuessNone; } } vector strategyFromString(const string& strategy) { vector toReturn; for (string::const_iterator it = strategy.begin(); it != strategy.end(); ++it) { toReturn.push_back(guessFromChar(*it)); } return toReturn; } void setFirstStrategy(vector& strategy, int n) { strategy.clear(); int guessesPerPerson = 1 << (n - 1); long numElems = guessesPerPerson * n; for (long i = 0; i < numElems; ++i) { strategy.push_back(GuessNone); } } // Returns whether the strategy is valid or not. (i.e. whether we haven't // reached the end bool incrementStrategy(vector& strategy, int n) { int rollOver = 0; int ss = strategy.size(); while (rollOver < ss && strategy[ss - 1 - rollOver] == GuessRed) { rollOver++; } if (rollOver == ss) { return false; } for (int i = 0; i < rollOver; ++i) { strategy[ss - 1 - i] = GuessNone; } if (strategy[ss - 1 - rollOver] == GuessNone) { strategy[ss - 1 - rollOver] = GuessBlue; } else { strategy[ss - 1 - rollOver] = GuessRed; } return true; } vector findBestStrategyExhaustive(int n) { double bestScore = 0.0; vector bestStrategy; vector curStrategy; setFirstStrategy(curStrategy, n); bool keepGoing = true; while (keepGoing) { double curScore = scoreStrategy(curStrategy, n); if (curScore > bestScore) { bestScore = curScore; bestStrategy = curStrategy; cout << "New best: " << bestStrategy << " (score " << bestScore << ")" << endl; } keepGoing = incrementStrategy(curStrategy, n); /*if (!keepGoing) { cout << "last is " << curStrategy << endl; }*/ } return bestStrategy; } void setRandomStrategy(vector& strategy, int n) { for (long i = 0; i < strategy.size(); ++i) { strategy[i] = (Guess) (rand() % 3); } } vector findBestStrategyRandom(int n, int numIter) { vector curStrategy; double bestScore = 0.0; vector bestStrategy; int guessesPerPerson = 1 << (n - 1); long numElems = guessesPerPerson * n; curStrategy.resize(numElems); for (int i = 0; i < numIter; ++i) { setRandomStrategy(curStrategy, n); double curScore = scoreStrategy(curStrategy, n); if (curScore > bestScore) { bestScore = curScore; bestStrategy = curStrategy; cout << "New best: " << bestStrategy << " (score " << bestScore << ")" << endl; } } return bestStrategy; } vector findBestStrategyHillClimbRestart(int n, int numIter, int steps) { int iterCount = 0; vector curStrategy; double bestScore = 0.0; vector bestStrategy; int guessesPerPerson = 1 << (n - 1); long numElems = guessesPerPerson * n; curStrategy.resize(numElems); while (iterCount < numIter) { setRandomStrategy(curStrategy, n); double curScore = scoreStrategy(curStrategy, n); if (curScore > bestScore) { bestScore = curScore; bestStrategy = curStrategy; cout << "New best: " << bestStrategy << " (score " << bestScore << ")" << endl; } if (++iterCount >= numIter) { return bestStrategy; } for (int i = 0; i < steps; ++i) { vector startStrategy = curStrategy; double startScore = curScore; for (int j = 0; j < curStrategy.size(); ++j) { Guess orig = curStrategy[j]; for (int curG = 0; curG < 3; ++curG) { if (orig != curG) { curStrategy[j] = (Guess) curG; curScore = scoreStrategy(curStrategy, n); if (curScore > bestScore) { bestScore = curScore; bestStrategy = curStrategy; cout << "New best: " << bestStrategy << " (score " << bestScore << ")" << endl; } if (curScore > startScore) { startScore = curScore; startStrategy = curStrategy; } if (++iterCount >= numIter) { return bestStrategy; } } } curStrategy[j] = orig; } if (fabs(curScore - startScore) < EPSILON) { // We're making no progress. Quit. i = steps; } curStrategy = startStrategy; curScore = startScore; } } } vector findBestStrategyGenetic(int n, int numIter, int generationSize, double mutationProb) { if (generationSize % 2 != 0) { cerr << "generationSize must be even! (is " << generationSize << ")" << endl; exit(1); } int iterCount = 0; int generationIndex = 0; vector, double> > curGeneration; double bestScore = 0.0; vector bestStrategy; int guessesPerPerson = 1 << (n - 1); long numElems = guessesPerPerson * n; curGeneration.resize(generationSize); // Initialize the generation. for (int i = 0; i < generationSize; ++i) { curGeneration[i].first.resize(numElems); setRandomStrategy(curGeneration[i].first, n); curGeneration[i].second = scoreStrategy(curGeneration[i].first, n); if (curGeneration[i].second > bestScore) { bestScore = curGeneration[i].second; bestStrategy = curGeneration[i].first; cout << "New best: " << bestStrategy << " (score " << bestScore << ", generation 0)" << endl; } if (++iterCount >= numIter && numIter != -1) { return bestStrategy; } } while (iterCount < numIter || numIter == -1) { // Score this generation. for (int i = 0; i < generationSize; ++i) { curGeneration[i].second = scoreStrategy(curGeneration[i].first, n); if (curGeneration[i].second > bestScore) { bestScore = curGeneration[i].second; bestStrategy = curGeneration[i].first; cout << "New best: " << bestStrategy << " (score " << bestScore << ", generation " << generationIndex << ")" << endl; } if (++iterCount >= numIter && numIter != -1) { return bestStrategy; } } // Breed this generation based on above scores. breedGeneration(curGeneration, n, mutationProb); ++generationIndex; } } int main() { srand(time(NULL)); runTests(); vector bestStrat = findBestStrategyExhaustive(3); cout << "3: " << bestStrat << " with score " << scoreStrategy(bestStrat, 3) << endl; //vector bestStrat = findBestStrategyHillClimbRestart(7, 10000000, 20); // vector bestStrat = findBestStrategyGenetic(7, -1, 50000, .01); // cout << "7: " << bestStrat << " with score " << scoreStrategy(bestStrat, 7) << endl; /*vector bestStrat = findBestStrategyExhaustive(4); cout << "4: " << bestStrat << " with score " << scoreStrategy(bestStrat, 4) << endl; bestStrat = findBestStrategyExhaustive(5); cout << "5: " << bestStrat << " with score " << scoreStrategy(bestStrat, 5) << endl;*/ return 0; } void runTests() { assert(0, (strategyFromString("").size()), "stratFromString() on empty"); vector v1 = strategyFromString("RB"); assert(2, (v1.size()), "stratFromString() on v1"); assert(GuessRed, v1[0], "stratFromString() on v1[0]"); assert(GuessBlue, v1[1], "stratFromString() on v1[1]"); vector v2 = strategyFromString("NRN"); assert(3, (v2.size()), "stratFromString() on v2"); assert(GuessNone, v2[0], "stratFromString() on v2[0]"); assert(GuessRed, v2[1], "stratFromString() on v2[1]"); assert(GuessNone, v2[2], "stratFromString() on v2[2]"); assert(0, curViewFromHatConfig(0, 5, 0), "curViewFromHatConfig 1"); assert(0, curViewFromHatConfig(0, 5, 3), "curViewFromHatConfig 2"); assert(0, curViewFromHatConfig(0, 5, 10), "curViewFromHatConfig 3"); assert(6, curViewFromHatConfig(6, 4, 0), "curViewFromHatConfig 4"); assert(2, curViewFromHatConfig(6, 4, 1), "curViewFromHatConfig 5"); assert(2, curViewFromHatConfig(6, 4, 2), "curViewFromHatConfig 6"); assert(3, curViewFromHatConfig(6, 4, 3), "curViewFromHatConfig 7"); assert(1, getHatConfigBit(14, 4, 0), "getHatConfigBit 1"); assert(1, getHatConfigBit(14, 4, 1), "getHatConfigBit 2"); assert(1, getHatConfigBit(14, 4, 2), "getHatConfigBit 3"); assert(0, getHatConfigBit(14, 4, 3), "getHatConfigBit 4"); assert(fabs(scoreStrategy(strategyFromString("N"), 1) - 0.00) < EPSILON, "strategyFromString(N)"); assert(fabs(scoreStrategy(strategyFromString("RRRR"), 2) - 0.25) < EPSILON, "strategyFromString(RRRR)"); vector guesses; strategyGuesses(strategyFromString("RNBRNBRNBRNB"), 3, 0, guesses); assert(GuessRed, guesses[0], "strategyGuesses 1 1"); assert(GuessNone, guesses[1], "strategyGuesses 1 2"); assert(GuessBlue, guesses[2], "strategyGuesses 1 3"); strategyGuesses(strategyFromString("RNBRNBRNBRNB"), 3, 5, guesses); assert(GuessNone, guesses[0], "strategyGuesses 2 1"); assert(GuessNone, guesses[1], "strategyGuesses 2 2"); assert(GuessNone, guesses[2], "strategyGuesses 2 3"); strategyGuesses(strategyFromString("BBNRRNBNNRBN"), 3, 6, guesses); assert(GuessNone, guesses[0], "strategyGuesses 3 1"); assert(GuessBlue, guesses[1], "strategyGuesses 3 2"); assert(GuessNone, guesses[2], "strategyGuesses 3 3"); assert(fabs(scoreStrategy(strategyFromString("RNNBRNNBRNNB"), 3) - 0.75) < EPSILON, "scoreStrategy(RNNBRNNBRNNB)"); assert(fabs(scoreStrategy(strategyFromString("BNNRBNNRBNNR"), 3) - 0.25) < EPSILON, "scoreStrategy(BNNRBNNRBNNR)"); assert(fabs(scoreStrategy(strategyFromString("BBBBBBBBBBBB"), 3) - 0.125) < EPSILON, "scoreStrategy(BBBBBBBBBBBB)"); assert(fabs(scoreStrategy(strategyFromString("NNNNNNNNNNNN"), 3) - 0.0) < EPSILON, "scoreStrategy(NNNNNNNNNNNN)"); vector strats; setFirstStrategy(strats, 3); assert(12, strats.size(), "setFirst size"); assert(GuessNone, strats[0], "setFirst 1"); assert(GuessNone, strats[1], "setFirst 2"); assert(GuessNone, strats[2], "setFirst 3"); assert(GuessNone, strats[strats.size() - 1], "setFirst 4"); assert(true, incrementStrategy(strats, 3), "iS 1 1"); assert(GuessNone, strats[strats.size() - 2], "iS 1 2"); assert(GuessBlue, strats[strats.size() - 1], "iS 1 3"); assert(true, incrementStrategy(strats, 3), "iS 2 1"); assert(GuessNone, strats[strats.size() - 2], "iS 2 2"); assert(GuessRed, strats[strats.size() - 1], "iS 2 3"); assert(true, incrementStrategy(strats, 3), "iS 3 1"); assert(GuessBlue, strats[strats.size() - 2], "iS 3 2"); assert(GuessNone, strats[strats.size() - 1], "iS 3 2"); assert(true, incrementStrategy(strats, 3), "iS 4 1"); assert(GuessBlue, strats[strats.size() - 2], "iS 4 2"); assert(GuessBlue, strats[strats.size() - 1], "iS 4 2"); for (int i = 0; i < strats.size(); ++i) { strats[i] = GuessRed; } assert(false, incrementStrategy(strats, 3), "iS end"); } void assert(bool b, const string& message) { if (!b) { cerr << "Test failed: " << message << endl; exit(1); } } template void assert(T expected, U actual, const string& message) { if (!(expected == actual)) { cerr << "Test failed: " << message << " (expected " << expected << ", got " << actual << ")" << endl; exit(1); } }