# MCTS-Optimized Scoring Algorithm Design

## Problem Statement

We need a scoring algorithm that makes MCTS perform well by providing score differences in the right range:

- **Standard Scorer**: Returns unbounded relative scores. Small differences get amplified in MCTS UCB formula, causing over-exploitation (commits to 1-2 high-scoring nodes too early).
- **Retired bounded-ratio scorer**: Returned scores in [0,1] range with power transformation (exponent=0.1). Differences were too compressed (~0.02-0.05), causing over-exploration (all nodes explored equally, AI made bad choices).

### MCTS Requirements

After ~100 visits, the **exploitation term** (cumulative_score / visits) should be comparable to the **exploration term** (C * sqrt(ln(parent_visits) / visits)).

With C=1.41 and typical parent visits ~10000:
- Exploration term: 1.41 * sqrt(ln(10000) / 100) ≈ 0.42
- **Target exploitation differences: 0.5 to 2.0**

This means individual scores should differ by **0.5 to 2.0** between meaningfully different positions.

## Scale Analysis from Codebase

### Unit Values
- Single unit context-free value: 500-3000 (depends on battalion type, stats, size)
- With modifiers (castle, terrain, ranged): 1000-6000 per unit
- Full army (10 units max): 10,000-40,000
- Typical strong army: ~20,000

### Victory Condition Scores
- Castle held by defender: -(battalion_size + vigor) * distance_debuf ≈ -800 per castle
- Distance debuf: 0.0 (adjacent) to 1.0 (unreachable), typically 0.9-0.95
- 3 castles held by defender at medium distance: ≈ -2400
- Range: 0 (all captured) to -3000 (all held, far away)

### Terminal States
- Victory: INT_MAX
- Defeat: INT_MIN
- Flee/Draw: 0
- Captured unit: -10,000
- Captured VIP: -25,000

## Proposed Algorithm: Bounded Linear Scorer

### Design Principles

1. **Normalized scale**: Map scores to approximately [-15, +15] range
2. **Separate components**: Units and victory conditions contribute separately
3. **Preserve relative importance**: Victory conditions dominate early, units become important as advantage grows
4. **Round-based weighting**: Similar to Standard scorer, weight units by rounds remaining

### Constants

```cpp
constexpr double UNITS_SCORE_SCALE = 80.0;      // Max contribution from proportional unit advantage
constexpr double VICTORY_SCORE_SCALE = 400.0;   // Normalizer for victory conditions (also proportional)
constexpr double MIN_REFERENCE_VALUE = 1000.0;  // Avoid division by zero in edge cases
```

**Key insights**:
1. Both unit scores AND victory condition scores scale proportionally with battle size (victory scores use battalion.size() in their calculation). Therefore, we normalize both by the **actual total army value** rather than a fixed reference.

2. **MCTS requires stronger signal than minimax**: Minimax (Iterative Deepening) just picks argmax, so even tiny score differences (0.01) work fine. MCTS needs score differences comparable to the exploration term (~0.4-0.5) to guide search effectively. We use 10x larger scale constants to amplify tactical differences like positioning, distance to objectives, and incremental unit advantages.

### Attacker Score Formula

```cpp
auto CombineAttackerScores(
    const UnitsScoreComponents &components,
    double victoryConditionScore,
    int roundsRemaining) const -> ScoreValue {

    // Use actual total army value as reference (scales with battle size)
    const double totalArmyValue = components.attackerUnitsValue + components.defenderUnitsValue;
    const double reference = std::max(totalArmyValue, MIN_REFERENCE_VALUE);

    // Normalize proportional unit difference to [-8, +8] range
    const double unitsDiff = components.attackerUnitsValue - components.defenderUnitsValue;
    const double unitsScore = (unitsDiff / reference) * UNITS_SCORE_SCALE;

    // Normalize victory condition (also proportional to army size) to approximately [-10, 0] range
    const double victoryScore = (victoryConditionScore / reference) * VICTORY_SCORE_SCALE;

    // Weight units by rounds remaining (early: units matter less, late: units dominate)
    const double unitsMultiplier =
        static_cast<double>(roundsRemaining) / static_cast<double>(GetMaxRounds());

    return unitsMultiplier * unitsScore + victoryScore;
}
```

### Defender Score Formula

```cpp
auto CombineDefenderScatterScores(
    const UnitsScoreComponents &components) const -> ScoreValue {

    // Use actual total army value as reference
    const double totalArmyValue = components.attackerUnitsValue + components.defenderUnitsValue;
    const double reference = std::max(totalArmyValue, MIN_REFERENCE_VALUE);

    // For scatter strategy, just maximize proportional defender advantage
    const double unitsDiff = components.defenderUnitsValue - components.attackerUnitsValue;
    return (unitsDiff / reference) * UNITS_SCORE_SCALE;
}

auto CombineDefenderHoldCastlesScores(
    const UnitsScoreComponents &components,
    double victoryConditionScore,
    int roundsRemaining) const -> ScoreValue {

    // Use actual total army value as reference
    const double totalArmyValue = components.attackerUnitsValue + components.defenderUnitsValue;
    const double reference = std::max(totalArmyValue, MIN_REFERENCE_VALUE);

    // Similar to attacker, but from defender's perspective
    const double unitsDiff = components.defenderUnitsValue - components.attackerUnitsValue;
    const double unitsScore = (unitsDiff / reference) * UNITS_SCORE_SCALE;
    const double victoryScore = (victoryConditionScore / reference) * VICTORY_SCORE_SCALE;

    const double unitsMultiplier =
        static_cast<double>(roundsRemaining) / static_cast<double>(GetMaxRounds());

    return unitsMultiplier * unitsScore + victoryScore;
}
```

### Terminal States

```cpp
auto InterpretAttackerOutcome(GameOutcome outcome) const -> ScoreValue {
    switch (outcome) {
        case GameOutcome::ATTACKER_VICTORY: return 1000.0;  // Large but bounded
        case GameOutcome::DEFENDER_VICTORY: return -1000.0;
        case GameOutcome::DRAW: return 0.0;
        case GameOutcome::FLEE_OUTCOME: return 0.0;
    }
}
```

Note: Using bounded values (±1000) instead of INT_MAX/MIN ensures numerical stability in MCTS and clearer signal that these are terminal states.

## Example Score Traces

### Large Battle Scenarios (10v10, ~40000 total army)

#### Scenario 1: Even armies, attacker needs to capture 3 castles
- Units: attacker 20000, defender 20000 (total: 40000)
- Victory: -2850 (3 castles * 950 each, medium distance)
- Rounds: 15/30 remaining

Score:
- reference = 40000
- unitsDiff = 0
- unitsScore = 0
- victoryScore = (-2850 / 40000) * 400.0 = -28.5
- unitsMultiplier = 0.5
- **total = 0.5 * 0 + (-28.5) = -28.5**

#### Scenario 2: Slight attacker advantage (10%)
- Units: attacker 22000, defender 18000 (diff: +4000, total: 40000)
- Victory: -2850
- Rounds: 15/30

Score:
- unitsScore = (4000 / 40000) * 80.0 = 8.0
- victoryScore = -28.5
- unitsMultiplier = 0.5
- **total = 0.5 * 8.0 + (-28.5) = -24.5**
- **Difference from Scenario 1: 4.0** ✓

#### Scenario 3: Large attacker advantage (30%)
- Units: attacker 26000, defender 14000 (diff: +12000, total: 40000)
- Victory: -2850
- Rounds: 15/30

Score:
- unitsScore = (12000 / 40000) * 80.0 = 24.0
- victoryScore = -28.5
- unitsMultiplier = 0.5
- **total = 0.5 * 24.0 + (-28.5) = -16.5**
- **Difference from Scenario 2: 8.0** ✓

### Small Battle Scenarios (2v2, ~4000 total army)

#### Scenario 4: Even small armies, 1 castle
- Units: attacker 2000, defender 2000 (total: 4000)
- Victory: -475 (1 castle * 500 * 0.95 distance)
- Rounds: 15/30

Score:
- reference = 4000
- unitsScore = 0
- victoryScore = (-475 / 4000) * 400.0 = -47.5
- **total = 0.5 * 0 + (-47.5) = -47.5**

#### Scenario 5: Slight advantage in small battle (10%)
- Units: attacker 2200, defender 1800 (diff: +400, total: 4000)
- Victory: -475
- Rounds: 15/30

Score:
- unitsScore = (400 / 4000) * 80.0 = 8.0
- victoryScore = -47.5
- **total = 0.5 * 8.0 + (-47.5) = -43.5**
- **Difference from Scenario 4: 4.0** ✓

### Early Game Scenario: Single unit movement

#### Scenario 6: Early game, single unit advances toward castle
- Units: attacker 20000, defender 20000 (total: 40000)
- Victory before: -2850 (distance debuf = 0.95)
- Victory after: -2829 (distance debuf = 0.943, one unit moved closer)
- Change in victory score: +21
- Rounds: 28/30 (early game)

Score change:
- victoryScoreChange = (21 / 40000) * 400.0 = 0.21
- Additionally, the moving unit (value 2000) gets better distance multiplier:
  - Before: 2000 * 0.25 = 500
  - After: 2000 * 0.279 = 558
  - Diff = 58, normalized: (58 / 40000) * 80.0 = 0.116
- unitsMultiplier = 28/30 = 0.933
- **Total improvement: 0.21 + 0.933 * 0.116 = 0.32** ✓

With exploration term ~0.42, this gives exploitation/exploration ratio of **0.76** - still below 1.0 but much better than before (was 0.05). MCTS will slightly prefer better moves while still exploring alternatives.

### Scale Consistency Verification

Comparing **10% advantage** in both battle sizes:
- Large battle (Scenario 2): diff = **4.0**
- Small battle (Scenario 5): diff = **4.0**

**Perfect scaling!** Same proportional advantage → same score difference, regardless of battle size.

Early game tactical moves now produce meaningful signals (0.3-0.5 range) that guide MCTS while still allowing healthy exploration.

## MCTS Behavior Verification

After 100 visits with C=1.41, exploration term ~0.42:

**Early game (single unit tactical moves):**
- Good positioning move: **0.32** (ratio 0.76x exploration)
- MCTS explores broadly but slightly favors better moves

**Mid game (unit advantages matter):**
- 10% army advantage: **4.0** (ratio 9.5x exploration)
- 30% army advantage: **8.0** (ratio 19x exploration)
- MCTS strongly commits to maintaining/increasing army advantage

**Late game (large differences):**
- Major strategic advantages: **10-40** (ratio 24-95x exploration)
- MCTS decisively exploits winning positions

This progression is ideal:
- **Early game**: Healthy exploration (ratio < 1.0) when moves are genuinely similar
- **Mid game**: Strong exploitation (ratio 9-19x) when clear advantages exist
- **Late game**: Decisive exploitation (ratio > 20x) to close out wins

This avoids both pathologies:
- Not over-exploiting (like Standard scorer which overcommitted to tiny early differences)
- Not over-exploring like the retired bounded-ratio scorer, which explored equally even with large advantages

## Why MCTS Needs Stronger Signal Than Minimax

**Iterative Deepening (minimax)** works fine with tiny score differences (0.01-0.1) because:
- It explores all moves to the same depth
- It simply picks `argmax(scores)`
- Even a 0.01 difference causes it to prefer the better move

**MCTS** needs much larger differences (0.3-4.0) because:
- It uses UCB formula: `score/visits + C*sqrt(ln(parent_visits)/visits)`
- The exploration term (~0.4) can dominate small exploitation differences
- With differences < 0.1, MCTS explores all moves almost equally (over-exploration)
- With differences > 10.0, MCTS commits too early (over-exploitation)

**Solution**: Use 10x larger scale constants than initially designed, specifically tuned so that:
- Early game tactical moves (positioning, distance) produce 0.3-0.5 differences
- Mid game advantages (10-30% army strength) produce 4.0-8.0 differences
- Late game crushing advantages produce 10-40 differences

This gives MCTS the right balance: explore when moves are similar, exploit when advantages are clear.

## Implementation Notes

1. **Use same calculation structure**: Inherit from AbstractAIScoreCalculator like Standard
2. **Reuse unit scoring**: Use existing CalculateUnitsScoreComponents and victory condition calculators
3. **Only change combination**: Override CombineAttackerScores, CombineDefenderScores, etc.
4. **Bounded terminals**: Use ±1000 instead of INT_MAX/MIN for numerical stability
5. **No transformation**: Do not apply power transformation - linear scaling is sufficient
6. **Scale constants tuned for MCTS**: 10x larger than naive normalization to provide appropriate signal strength

## Testing with Integration Tests

Before integrating with MCTS, test the new scorer with **IterativeDeepeningAI** using the AI integration test infrastructure.

### Integration Test Infrastructure

The codebase now has comprehensive AI integration tests in `src/test/cpp/net/eagle0/shardok/ai/AIIntegrationTest.cpp` that use:

1. **AIPerformanceTestHelpers** (`src/test/cpp/net/eagle0/shardok/library/AIPerformanceTestHelpers.{cpp,hpp}`):
   - `CreatePerfTestGameState(settings, defenderToggle)` creates a 6v6 scenario on the Alah map
   - Properly initializes units with correct battalion sizes (800 for longbowmen, capacity-based for others)
   - Handles both attacker and defender perspectives
   - Returns GameStateW in SETUP phase with 6 units per player in reserve

2. **ShardokAIClient** integration:
   - Tests use the full AI client interface, not just the search algorithm
   - Time budgets set to 3s for reasonable test execution time
   - Handles both setup phase placement and first turn movement

3. **Acceptable Position Sets** for handling AI non-determinism:
   - AI decisions may vary due to internal tie-breaking and search order
   - Tests define sets of acceptable positions for each unit
   - Example from AttackerAI_Setup_PlacesUnitsCorrectly:
     ```cpp
     std::set<net::eagle0::shardok::storage::fb::Coords> acceptablePositions{
         net::eagle0::shardok::storage::fb::Coords(0, 11),
         net::eagle0::shardok::storage::fb::Coords(1, 10),
         // ... more acceptable positions
     };
     ```

### Adding Tests for New Scorers

To test MCTSOptimizedAIScoreCalculator (or any new scorer) with IterativeDeepeningAI:

1. **Add test cases following the existing pattern** in `AIIntegrationTest.cpp`:
   ```cpp
   TEST(MCTSOptimizedScorerTest, AttackerAI_Setup_PlacesUnitsCorrectly) {
       auto settings = GetDefaultGameSettingsForTest();
       auto gameStateW = CreatePerfTestGameState(settings, /*defenderToggle=*/false);
       auto hexMap = gameStateW.GetHexMap().ToProto();

       // Use MCTSOptimizedAIScoreCalculator instead of StandardAIScoreCalculator
       auto scoreCalculator = std::make_shared<MCTSOptimizedAIScoreCalculator>(
           /*playerId=*/0, /*isDefender=*/false, hexMap, settings->GetGetter());

       ShardokAIClient client(
           /*playerId=*/0, /*isDefender=*/false, hexMap, settings,
           scoreCalculator, std::chrono::milliseconds(3000));

       // ... rest of test follows existing pattern
   }
   ```

2. **Update BUILD.bazel** to add the new scorer as a dependency:
   ```bazel
   deps = [
       # ... existing deps ...
       "//src/main/cpp/net/eagle0/shardok/ai/score:mcts_optimized_ai_score_calculator",
   ]
   ```

3. **Test patterns to implement**:
   - **Setup Phase Tests**: Verify AI places units in reasonable starting positions
     - `AttackerAI_Setup_PlacesUnitsCorrectly`: Attacker should place at start zone (0,11)-(1,13)
     - `DefenderAI_Setup_OccupiesCastles`: Defender should occupy castle tiles
   - **First Turn Tests**: Verify AI makes sensible initial moves
     - `AttackerAI_FirstTurn_MovesUnitsCorrectly`: Attacker should advance toward objectives
     - Use acceptable position sets to handle non-determinism
   - **Score Range Verification**: Add assertions to verify scores are in expected ranges
     ```cpp
     // Example: verify scores are bounded as expected
     auto searchResult = client.GetBestCommand(gameStateW);
     EXPECT_GE(searchResult.score, -50.0);  // Reasonable lower bound
     EXPECT_LE(searchResult.score, 50.0);   // Reasonable upper bound
     ```

4. **Performance Regression Testing**:
   - Run `./scripts/ai_perf_test.sh` to verify the new scorer doesn't cause performance degradation
   - Compare commands evaluated at each depth vs. StandardAIScoreCalculator
   - See CLAUDE.md "Performance Testing" section for detailed instructions

### Why Test with IterativeDeepeningAI First

The new scoring algorithm should work with **both** IterativeDeepeningAI and MCTS:
- If it fails with IterativeDeepeningAI, the scoring logic itself is broken
- If it passes with IterativeDeepeningAI but fails with MCTS, the issue is MCTS-specific
- This allows incremental testing and debugging

Once the scorer passes integration tests with IterativeDeepeningAI, then integrate with MCTS and compare behavior.

## Alternative Names

- `BoundedLinearAIScoreCalculator`
- `MCTSOptimizedAIScoreCalculator`

Recommend: **`MCTSOptimizedAIScoreCalculator`** to clearly indicate purpose.
