Complexity Analysis
Okay, let's break down the complexity of Egalicon and compare it to other abstract strategy games.
Defining Egalicon Setups for Analysis
These setups match the implementation used in the interactive game on this site.
- 6x6: 2 starting rows per player (12 pieces each: 4 Diamonds [D], 4 Papers [P], 4 Scissors [S]). Board size 36.
- 9x9: 3 starting rows per player (27 pieces each: 9D, 9P, 9S). Board size 81.
- 12x12: 4 starting rows per player (48 pieces each: 16D, 16P, 16S). Board size 144.
- 18x18: 6 starting rows per player (108 pieces each: 36D, 36P, 36S). Board size 324.
Egalicon Complexity Factors:
- Movement: Single pieces move 1 square in any of 8 directions.
- Stacking: Single pieces can tower onto friendly pieces/towers.
- Capturing: Single pieces or whole towers can capture opponent pieces/towers if the top piece wins according to Rock-Paper-Scissors.
- Tower Ambiguity: When moving a tower to an empty square or capturing, the player chooses whether to move only the top piece or the entire tower. This significantly increases the branching factor compared to just moving single pieces.
Complexity Estimations (Egalicon)
- Initial Moves (a): Calculated deterministically based on available single-piece moves (to empty or tower on own piece) for Red's first turn using the specific setups above.
- 6x6: 68
- 9x9: 173
- 12x12: 326
- 18x18: 776
- Average Moves (b): Estimating the average number of legal moves (often called the 'branching factor' in game AI) throughout a typical game is challenging. The "Tower Ambiguity" rule increases options significantly compared to the initial state, but piece captures reduce options later. The values presented below use a conservative "Piece-Centric" estimation method (see Note ¹ below).
- Positions to Analyze (c): Calculated as (Avg Branching Factor) raised to the power of (Turns * 2). This represents the approximate number of unique game states (leaf nodes) to check in a simple brute-force search for a given number of player moves (ply). This table uses **2 turns (4 ply)** (see Note ² below).
Complexity Data for Other Games (Approximate/Common Figures)
- Chess: Initial: 20. Avg Moves: ~35. State Space Complexity (total possible positions): ~10^43-47. Game Tree Size (estimated decision tree size): ~10^120.
- Abalone: Initial: ~50-60 (depends on specific opening move choice). Avg Moves: ~30-40 (can be higher for multi-marble pushes).
- Checkers (English Draughts): Initial: 9. Avg Moves: ~10 (lower due to forced captures). State Space: ~10^20. Solved (meaning a perfect strategy is known).
- Go: Branching factor is roughly proportional to board size initially/mid-game, decreases slightly later.
- Go 9x9: Avg Moves: ~50-80. State Space: ~10^38. Game Tree: ~10^70.
- Go 13x13: Avg Moves: ~100-150. State Space: ~10^78. Game Tree: ~10^170.
- Go 19x19: Avg Moves: ~200-300. State Space: ~10^170. Game Tree: ~10^360.
Comparison Table (Conservative Estimates)
| Game Variant | a) Initial Moves | b) Overall Avg Moves¹ | c) Positions (2 Turns)² |
|---|---|---|---|
| Egalicon 6x6 | 68 | ~54 | ~8.5 M |
| Egalicon 9x9 | 173 | ~140 | ~384 M |
| Egalicon 12x12 | 326 | ~288 | ~6.9 B |
| Egalicon 18x18 | 776 | ~729 | ~281 B |
| Chess | 20 | ~35 | ~1.5 M |
| Abalone | ~55 | ~35 | ~1.5 M |
| Checkers (Draughts) | 9 | ~10 | ~10 K |
| Go 9x9 | 81 | ~70 | ~24 M |
| Go 13x13 | 169 | ~140 | ~384 M |
| Go 19x19 | 361 | ~250 | ~3.9 B |
Comparative Complexity Scale (2 Turns)
To put the "Positions to Analyze" after 2 turns into perspective, here's a comparison table where Chess's complexity (~1.5 Million positions) is set as a base scale factor of 1.
| Game Variant | Scale Factor (vs Chess 2 Turns) |
|---|---|
| Checkers (Draughts) | ~0.007 |
| Chess | 1 |
| Abalone | ~1 |
| Egalicon 6x6 | ~5.7 |
| Go 9x9 | ~16 |
| Egalicon 9x9 | ~256 |
| Go 13x13 | ~256 |
| Go 19x19 | ~2,600 |
| Egalicon 12x12 | ~4,600 |
| Egalicon 18x18 | ~187,000 |
Notes and Caveats
- ¹ Avg Moves (b): The values presented use a conservative "Piece-Centric" estimation method. This method estimates the average moves based on the likely number of active pieces mid-game (assuming ~75% of initial pieces remain) multiplied by an estimated average number of options per piece (ranging from 6 for 6x6 to 9 for 18x18, accounting for movement, stacking, and tower ambiguity). This approach avoids direct scaling from the potentially misleadingly high initial move count and provides a more cautious, though still approximate, view of the average branching factor. Previous estimation methods yielded significantly higher, potentially inflated, results.
- ² Positions (c): Calculated as
(Overall Avg Moves) ^ 4(i.e., for 2 full turns or 4 ply). This represents the approximate number of leaf nodes in a 4-ply brute-force search tree. Values are approximate (K = Thousands, M = Millions, B = Billions). - Game Complexity: These numbers relate primarily to Game Tree Complexity (difficulty for AI search) more than State Space Complexity (total possible unique positions).
- Go Complexity: Go's branching factor is high initially but doesn't necessarily increase as much mid-game as Egalicon might due to the towering mechanic. Local fights dominate Go strategy.
- Estimation Uncertainty: All estimates for average branching factor are inherently uncertain without extensive game simulations. The actual branching factor fluctuates significantly throughout any given game.
Analysis Summary (Conservative Estimates)
- Egalicon vs. Chess/Checkers/Abalone: Even with conservative estimates, Egalicon exhibits a significantly higher average branching factor than Chess, Checkers, or Abalone, especially on larger boards. This is largely due to the 8-directional movement, towering, and particularly the "move top vs. move whole tower" ambiguity. The 6x6 variant's estimated average branching factor (~54) is already higher than Chess (~35).
- Egalicon vs. Go:
- The estimated average branching factor of Egalicon scales rapidly with board size (e.g., ~54 for 6x6 up to ~729 for 18x18). On larger boards, it significantly exceeds that of Go on comparable dimensions (e.g., Egalicon 18x18 at ~729 vs. Go 19x19 at ~250).
- The nature of the complexity differs. Go's complexity arises from the vast possibilities of local territory formation and influence. Egalicon's complexity stems from the tactical interactions of RPS captures combined with the spatial and combinatorial options offered by towers and the dual-move tower mechanic.
- Scalability: Egalicon's complexity increases very steeply with board size. The number of positions to analyze within a few turns grows astronomically, confirming its status as a highly complex game.
In conclusion, based on these more conservative estimates, Egalicon remains a game of exceptionally high tactical complexity due to its core mechanics. Its average branching factor appears to significantly exceed that of Chess and Abalone, and likely surpasses Go on larger board sizes. The tower ambiguity rule is the primary driver of this complexity, presenting a substantial challenge for deep strategic calculation and AI development.