Skip to main content
The TranspositionTable class is a specialized hash table that caches position evaluations to dramatically speed up the solver. In Connect 4, the same position can be reached through different move sequences (called a “transposition”), and this table allows the solver to skip re-evaluating positions it has already seen.

​
Overview

​
What is a Transposition?

A transposition occurs when different move sequences lead to the same board position: 
Sequence A: [4, 3, 5]  →  [same position]  ←  Sequence B: [5, 3, 4]
Without a transposition table, the solver would analyze the same position multiple times. With the table, it evaluates the position once and reuses the result.

​
How it Works

  1. Unique Position Key: Each position has a unique 64-bit key generated by Position::key()
  2. Hash Index: The key is mapped to a table index using modulo: index = key % table_size
  3. Storage: Each entry stores the position key and its evaluated score
  4. Collision Handling: Newer entries overwrite older ones at the same index (replacement strategy)

​
Memory Usage

The default table size is 8,388,608 entries (2^23), which uses approximately 64 MB of memory:
  • Each entry: 16 bytes (8-byte key + 8-byte value with padding)
  • Total: 8,388,608 × 16 bytes ≈ 134 MB

​
Entry Structure

struct Entry {
    uint64_t key = 0;   // Position key (0 means empty)
    int8_t value = 0;   // Stored score
};
​
key
uint64_t
Unique position identifier. A value of 0 indicates an empty entry.
​
value
int8_t
The evaluated score for this position (-128 to 127).

​
Constructor

explicit TranspositionTable(size_t size = 8388608);
Creates a transposition table with the specified number of entries.
​
size
size_t
default:"8388608"
Number of entries in the table. Should ideally be a power of 2 for optimal performance. Default is 2^23 = 8,388,608 entries.
Memory calculation:
  • Default (8M entries): ~64 MB
  • 16M entries: ~128 MB
  • 4M entries: ~32 MB
Example: 
// Default size (8M entries, ~64 MB)
TranspositionTable tt1;

// Custom size (4M entries, ~32 MB)
TranspositionTable tt2(4194304);

// Larger table (16M entries, ~128 MB)
TranspositionTable tt3(16777216);

​
Public Methods

​
put()

void put(uint64_t key, int8_t value);
Stores a position’s evaluated score in the table.
​
key
uint64_t
Unique position key from Position::key()
​
value
int8_t
The evaluated score to store (typically from negamax search)
Note: If there’s already an entry at this index (collision), the new entry overwrites the old one. Example: 
TranspositionTable tt;
Position pos;

// Evaluate position and store result
uint64_t key = pos.key();
int8_t score = 5;  // Hypothetical evaluation result
tt.put(key, score);

​
get()

int8_t get(uint64_t key) const;
Retrieves a previously stored score for the given position.
​
key
uint64_t
Unique position key from Position::key()
Returns: int8_t - The stored score, or 0 if not found Important: A return value of 0 could mean either:
  • The position was never stored
  • The position was stored with a score of 0 (draw)
  • The entry was overwritten by a collision
In practice, the solver handles this by checking if the retrieved value is valid before using it. Example: 
TranspositionTable tt;
Position pos;

uint64_t key = pos.key();
int8_t cached_score = tt.get(key);

if (cached_score != 0) {
    // Use cached result
    std::cout << "Found cached score: " << (int)cached_score << std::endl;
} else {
    // Evaluate position and cache it
    int8_t score = evaluate(pos);
    tt.put(key, score);
}

​
reset()

void reset();
Clears all entries in the table by setting all keys to 0 and all values to 0. Use cases:
  • Starting a new game
  • Running benchmarks
  • Freeing memory for other uses
Example: 
TranspositionTable tt;

// Use table for first game
for (int i = 0; i < 100; i++) {
    // ... solver operations ...
}

// Clear for second game
tt.reset();

// Use table for second game
for (int i = 0; i < 100; i++) {
    // ... solver operations ...
}

​
Usage in Solver

The Solver class uses a TranspositionTable internally. Here’s a conceptual example of how it’s used during negamax search: 
class Solver {
private:
    TranspositionTable tt_;
    
    int negamax(Position pos, int alpha, int beta) {
        uint64_t key = pos.key();
        
        // Check if we've seen this position before
        int8_t cached = tt_.get(key);
        if (cached != 0) {
            return cached;  // Return cached result
        }
        
        // ... evaluate position using negamax ...
        int score = /* computed score */;
        
        // Store result for future use
        tt_.put(key, score);
        
        return score;
    }
};

​
Performance Impact

The transposition table provides dramatic speedups:
  • Without TT: May evaluate millions of duplicate positions
  • With TT: Each unique position evaluated at most once
  • Speedup: Often 10x-100x faster depending on the position
Example benchmark output: 
Without transposition table: 5,234,891 nodes analyzed
With transposition table:      423,156 nodes analyzed
Speedup: 12.4x

​
Implementation Details

​
Hash Function

size_t index(uint64_t key) const { 
    return key % size_; 
}
The table uses simple modulo hashing. While not the fastest hash function, it’s:
  • Simple and predictable
  • Sufficient for Connect 4 (positions are well-distributed)
  • Easy to understand and debug

​
Collision Strategy

When two different positions hash to the same index (a collision), the newer entry overwrites the older one. This is called a “replacement strategy.” Tradeoffs:
  • Simple to implement
  • Always stores the most recent evaluation
  • May occasionally discard useful data
  • In practice, the table is large enough that this rarely matters

​
Memory Optimization

The table uses int8_t (1 byte) for scores instead of int (4 bytes) to save memory:
  • Range: -128 to +127
  • Sufficient for Connect 4 (max score is ±22, since max moves is 42)
  • 4x memory savings compared to using int

​
Best Practices

  1. Size Selection: Use a power of 2 for the table size (better performance on some systems)
  2. Memory Budget: Default 64 MB is usually fine; increase if you have RAM to spare
  3. Reset Between Games: Call reset() when starting a new independent search
  4. Don’t Reset During Search: Keep the table intact during a single game analysis

​
Example: Custom Table Size

If you’re memory-constrained or have extra memory available: 
// Small table for embedded systems (~16 MB)
TranspositionTable small_tt(2097152);  // 2^21 entries

// Large table for servers (~256 MB)
TranspositionTable large_tt(33554432);  // 2^25 entries

// Use in solver
class CustomSolver {
private:
    TranspositionTable tt_;
    
public:
    CustomSolver(size_t table_size) : tt_(table_size) {}
    
    int solve(const Position& pos) {
        // ... use tt_ internally ...
    }
};

// Create solver with custom table size
CustomSolver solver(16777216);  // 16M entries, ~128 MB

Build docs developers (and LLMs) love

Get started for freeTalk to us