EHS Caching Strategies for CFR Poker Training

Overview

This document compares two approaches to caching Expected Hand Strength (EHS) values during CFR poker training: random pre-computed caching vs. bucket-based caching. The analysis shows why random pre-computation is ineffective and how bucket-based abstraction dramatically improves cache hit rates.

1. State Space Complexity

State Space Sizes by Street

Coverage Analysis

Key Problem: Pre-computing 100k random samples provides less than 0.001% coverage on turn/river, leading to >99% cache miss rate during training.

2. Problem: Random Pre-computed EHS Approach

Why It Doesn’t Work

Flow: Current Random Pre-computation

Why cache misses are so high:

1. Random paths: Each CFR iteration explores different random game trajectories
2. Massive state space: 2.8B river combinations, only 100k cached
3. No locality: Random pre-computation doesn’t align with training access patterns
4. Single-use entries: Cached values are rarely visited again in subsequent iterations

3. Solution: Bucket-Based Caching

Abstraction Strategy

Instead of caching exact (hole, board) combinations, cache by abstracted buckets:

Bucket Space Reduction

Example bucket scheme:

• 5 preflop buckets (pairs, suited, offsuit, etc.)
• 10 flop buckets (made hands, draws, etc.)
• 10 turn buckets (strength categories)
• 10 river buckets (final strength)
• Total: 5 × 10 × 10 × 10 = 5,000 bucket combinations

Flow: Bucket-Based Caching

Why cache hits are high:

1. Locality: Many exact states map to same bucket
2. Small space: Only 5,000 buckets vs. billions of states
3. Reuse: Same buckets visited repeatedly across iterations
4. Coverage: 100% of state space maps to some bucket

4. Comparison: Random vs. Bucket-Based

Performance Impact

5. Implementation Considerations

Bucket-Based Caching Implementation

class BucketEHSCache:
    def __init__(self):
        # Cache: (preflop_bucket, street_bucket) -> EHS value
        self.cache = {}

    def get_ehs(self, hole_cards, board):
        # Get abstraction buckets
        preflop_bucket = get_preflop_bucket(hole_cards)
        street_bucket = get_street_bucket(hole_cards, board)

        key = (preflop_bucket, street_bucket)

        if key in self.cache:
            return self.cache[key]  # Cache hit

        # Cache miss: compute average EHS for all hands in bucket
        bucket_ehs = compute_bucket_average_ehs(preflop_bucket, street_bucket, board)
        self.cache[key] = bucket_ehs

        return bucket_ehs

Key Design Decisions

1. Bucket Granularity: Balance between precision and cache size

   • Fewer buckets = higher hit rate, lower precision
   • More buckets = lower hit rate, higher precision
   • Sweet spot: 5-10 buckets per street

2. Precomputation Strategy:

   • Pre-compute all 5,000 bucket EHS values before training
   • Or compute lazily during training (cold start penalty)

3. Bucket Definition:

   • Hand strength percentiles
   • Equity distributions
   • Potential (made hand + draws)

Profiling Update: The Real Story

UPDATE (2025-12-03): After profiling, we discovered the analysis above is partially incorrect.

What Profiling Revealed

Total _compute_ehs calls:  27,398
Actual GPU compute calls:     720
In-memory cache hits:     26,678  (97.4% hit rate!)

The existing in-memory _ehs_cache in PostflopAbstraction already achieves 97.4% hit rate!

Why Pre-computed Tables Don’t Help

Corrected Understanding

Actual Optimization Opportunities

Conclusion

Random pre-computed EHS caching is ineffective because:

• Minuscule coverage of massive state space Actually: In-memory cache already has 97.4% hit rate
• Random access patterns don’t align with training Actually: Cache grows organically with training paths
• >99% cache miss rate Actually: Only 2.6% miss rate

Bucket-based caching would NOT help significantly because:

• In-memory cache already provides excellent coverage
• The bottleneck is per-call GPU overhead, not cache misses
• ~720 GPU calls × 23.8ms = 17.1s regardless of caching strategy

Actual recommendation: Focus on reducing per-call GPU overhead:

1. Reduce Monte Carlo samples from 100 to 50
2. Batch EHS queries across multiple tree branches
3. Optimize combinatorial index computation