[C++] Hjälp med Transposition table!

Hej!

Gårdagens artikel om Googles AI (http://www.sweclockers.com/nyhet/21679-googles-ai-knacker-man...) fick mig att börja nöta på AI's igen och jag bestämde mig för att göra ett enkelt Tic-tac-toe spel med en AI som är baserad på en MiniMax algoritm (https://en.wikipedia.org/wiki/Minimax) . Detta är något jag tidigare har gjort och den jag har implementerat nu (med Alpha-Beta pruning) fungerar utan problem, men för att göra det lite svårare nu när jag har lite fri tid över under helgen så tänkte jag även implementera en s.k. Transposition table.

Det är just här jag har fastnat. Min MiniMax algoritm med Alpha-Beta pruning ser ut på följande sätt:

int miniMax(const state &STATE, int alpha, int beta, int depth, bool maxPlayer) {

    ... // lite annat

    if (STATE.isEndOfGame() || depth == 0) {
        return score(STATE); // returnerar det heuristiska värdet för noden
    }
 
    if (maxPlayer) { // true
        for (int i = 0; i < allPossibleMoves.size(); i++) {
            alpha = std::max(alpha, miniMax(allPossibleMoves[i], alpha, beta, depth - 1, false));
            if (alpha >= beta) {
                return beta; // beta cut-off -> prune!
            }
        }
        return alpha;
    }
    if (!maxPlayer) { // false
        for (int i = 0; i < allPossibleMoves.size(); i++) {
            beta = std::min(beta, miniMax(allPossibleMoves[i], alpha, beta, depth - 1, true));
            if (alpha >= beta) {
                return alpha; // alpha cut-off -> prune!
            }
        }
        return beta;
    }
}

Mitt mål är att implementera en Transposition table (en hashtabell) som innehåller hashade värden för varje STATE som genomgås i miniMax() så att mitt spel slipper gå igenom samma positioner om och om igen och på så sätt snabba upp programmet (jag vill nämligen göra programmet så snabbt som möjligt och även omöjligt att slå, ungefär som denna: http://perfecttictactoe.herokuapp.com/ ). Hash-funktionen jag planerar att använda är den s.k. Zobrist key (https://en.wikipedia.org/wiki/Zobrist_hashing).

Om jag har förstått det rätt så måste jag först skapa en 9x2 array (9 rutor och 2 spelare) och fylla denna med random number (helst 64-bitars int). Jag har gjort det på följande sätt:

unsigned long long int rand64() {
  return rand()^((U64)rand()<<15)^((U64)rand()<<30)^((U64)rand()<<45)^((U64)rand()<<60); // hittade denna här:
  // http://aghaznawi.comuf.com/computer%20chess/winglet/16repetit...
}

unsigned long long int tTable() {
  unsigned long long int tt[9][2];
  for (unsigned int i = 0; i < 9; i++) {
    for (unsigned int j = 0; j < 2; j++) {
      tt[i][j] = rand64();
    }
  }
  return tt;  // Går ej att returnera en array, jag vet - ska lösa det senare på ett annat sätt!
}

Det är här jag har fastnat. Jag vet att jag bör använda XOR (som ska tydligen vara väldigt snabbt) för att lagra olika STATEs i min Zobrist key, och har kommit fram till följande sätt (med hjälp av Wikipedia):

	unsigned long long int zobristKey = 0;
	int player;
	for (int i = 0; i < 9; i++) {
		player = STATE.at(i);
		if (player &PLAYER_X) {
			zobristKey ^= tt[i][1];
		}
		else if (player &PLAYER_X) {
			zobristKey ^= tt[i][2];
		}
	}
	return zobKey;

Hur implementerar man allt detta i en MiniMax algoritm exakt? Var ska jag lagra alla dessa STATEs min algoritm kommer fram till och hur kan min algoritm kontrollera att de inte har körts redan? Och främst av allt - vilka STATEs bör jag lagra? Jag har läst på en massa olika sidor (verkar vara mest implementeringar i Schack) men ju mer jag läser om Transposition tables och hashning, desto mer förvirrad verkar jag bli.

Alla tips uppskattas enormt!