import random
 
class ZobristTicTacToe:
    # Constants for pieces
    EMPTY = 0
    PIECE_X = 1
    PIECE_O = 2
 
    def __init__(self):
        # Board: 9 cells (3x3)
        self.board = [self.EMPTY] * 9
        self.current_hash = 0
        
        # Pre-generate 64-bit random values: table[cell_index][piece_type]
        # piece_type index: 0 for X, 1 for O
        self.zobrist_table = [
            [random.getrandbits(64) for _ in range(2)] 
            for _ in range(9)
        ]
 
    def get_hash(self):
        return self.current_hash
 
    def make_move(self, cell, piece):
        """Plays a move at cell, updating the hash in O(1) time."""
        if self.board[cell] != self.EMPTY:
            raise ValueError("Cell is already occupied")
 
        self.board[cell] = piece
        piece_idx = 0 if piece == self.PIECE_X else 1
        
        # XOR the new piece state into the hash
        self.current_hash ^= self.zobrist_table[cell][piece_idx]
 
    def undo_move(self, cell, piece):
        """Reverts a move at cell, updating the hash in O(1) time."""
        if self.board[cell] != piece:
            raise ValueError("No matching piece to undo at this cell")
 
        self.board[cell] = self.EMPTY
        piece_idx = 0 if piece == self.PIECE_X else 1
        
        # XORing the same value again cancels it out, restoring the prior hash
        self.current_hash ^= self.zobrist_table[cell][piece_idx]
 
# Example Usage
if __name__ == "__main__":
    game = ZobristTicTacToe()
    print(f"Empty Board Hash: {game.get_hash():016X}")
    
    # X plays cell 4 (center)
    game.make_move(4, ZobristTicTacToe.PIECE_X)
    hash_after_x = game.get_hash()
    print(f"Hash after X on 4: {hash_after_x:016X}")
    
    # O plays cell 0 (top-left)
    game.make_move(0, ZobristTicTacToe.PIECE_O)
    print(f"Hash after O on 0: {game.get_hash():016X}")
    
    # Undo O plays cell 0
    game.undo_move(0, ZobristTicTacToe.PIECE_O)
    print(f"Hash after undo O: {game.get_hash():016X} (Matches hash_after_x? {game.get_hash() == hash_after_x})")

#include <iostream>
#include <vector>
#include <random>
#include <iomanip>
#include <stdexcept>
 
class ZobristTicTacToe {
public:
    static const int EMPTY = 0;
    static const int PIECE_X = 1;
    static const int PIECE_O = 2;
 
private:
    std::vector<int> board;
    unsigned long long currentHash;
    // Table size: 9 cells, 2 pieces
    unsigned long long zobristTable[9][2];
 
public:
    ZobristTicTacToe() : board(9, EMPTY), currentHash(0) {
        // Seed random engine
        std::mt19937_64 rng(1337); // Fixed seed for reproducibility
        std::uniform_int_distribution<unsigned long long> dist;
 
        // Populate table with random 64-bit integers
        for (int i = 0; i < 9; ++i) {
            zobristTable[i][0] = dist(rng); // Value for X
            zobristTable[i][1] = dist(rng); // Value for O
        }
    }
 
    unsigned long long getHash() const {
        return currentHash;
    }
 
    void makeMove(int cell, int piece) {
        if (board[cell] != EMPTY) {
            throw std::runtime_error("Cell is already occupied");
        }
        board[cell] = piece;
        int pieceIdx = (piece == PIECE_X) ? 0 : 1;
        
        // XOR piece state in O(1)
        currentHash ^= zobristTable[cell][pieceIdx];
    }
 
    void undoMove(int cell, int piece) {
        if (board[cell] != piece) {
            throw std::runtime_error("No matching piece to undo at this cell");
        }
        board[cell] = EMPTY;
        int pieceIdx = (piece == PIECE_X) ? 0 : 1;
 
        // XOR again to cancel out
        currentHash ^= zobristTable[cell][pieceIdx];
    }
};
 
int main() {
    ZobristTicTacToe game;
    std::cout << std::hex << std::uppercase << std::setfill('0');
    std::cout << "Empty Board Hash: " << std::setw(16) << game.getHash() << "\n";
 
    game.makeMove(4, ZobristTicTacToe::PIECE_X);
    unsigned long long hashAfterX = game.getHash();
    std::cout << "Hash after X on 4: " << std::setw(16) << hashAfterX << "\n";
 
    game.makeMove(0, ZobristTicTacToe::PIECE_O);
    std::cout << "Hash after O on 0: " << std::setw(16) << game.getHash() << "\n";
 
    game.undoMove(0, ZobristTicTacToe::PIECE_O);
    std::cout << "Hash after undo O: " << std::setw(16) << game.getHash() 
              << " (Matches? " << (game.getHash() == hashAfterX ? "Yes" : "No") << ")\n";
 
    return 0;
}