Let's talk

Game AI

My Game of the Generals bot learned to run.

I let a Game of the Generals bot tune its own judgment by playing itself. Its score against my greedy bot went from 68.7% to 91.1%, mostly by walking its Flag home.

Lance EndayaFull-stack software engineer
4 min read
GOTG AIGAME OF THE GENERALSScore against the greedy bot68.7%→91.1%after 6,400 games against itselfLTCPVTSPY1LTMAJCOLPVT4★FLGCPT
Blue is my autopilot, walking its Flag to the far row against my greedy bot. Red's pieces are shaded by how likely the autopilot thinks each one is to be red's Flag.

I've been building a bot for Game of the Generals, the Filipino board game also known as Salpakan. It runs entirely in your browser.

This post is about the autopilot, the first of my bots that reasons about what its opponent might be hiding, and what happened when I let it tune its own judgment by playing thousands of games against itself. It got a lot better, mostly by learning to march its Flag across the board.

Tuned autopilot vs greedy
91.1%
95% CI 89.2–92.8% · 1,000 games
Whole interval above 50%
Untuned vs greedy
68.7%
95% CI 65.7–71.4%
Tuned vs untuned
72.5%
642–165–193 W–D–L
Tuned vs random
99.9%
998–2–0 W–D–L
Median move time
2.3 ms
95th percentile 7.1 ms
Play against the autopilotIt's the Hard bot on gotg-ai.vercel.app, with heatmaps, attack odds and move advice if you want help.

The game in a minute

Each player has 21 pieces on a 9×8 board. You can see where every enemy piece is, but not what it is. When two pieces meet, a neutral arbiter removes the lower-ranked one without telling either player what the pieces were.

GOTG AI · The pieces

21 pieces in 15 ranks, and the higher rank removes the lower

StrongestWeakest
  1. 5-Star General
  2. 4-Star General
  3. 3-Star General
  4. 2-Star General
  5. 1-Star General
  6. Colonel
  7. Lieutenant Colonel
  8. Major
  9. Captain
  10. 1st Lieutenant
  11. 2nd Lieutenant
  12. Sergeant
  13. Private ×6
  • Spy ×2Removes every officer and the Sergeant, generals included. A Private removes it.
  • FlagAny piece can take it, and losing it loses the game.
Each side's pieces, as the app draws them. When two pieces of the same rank meet, both are removed.

You win by capturing the enemy Flag, or by walking your own Flag to the far side of the board. So it plays like chess with poker's hidden cards: every challenge is a bet on what the other piece probably is.

What the bot knows

Every ruling is evidence. If my Captain challenges a piece and loses, that piece is a Major or higher, or a Spy. A piece that never leaves its back row is more likely to be the Flag. An earlier milestone built a belief engine that tracks this: for each of the 21 enemy pieces, the odds of each of the 15 ranks, kept consistent with each other and re-solved after every move.

Here's a real game from the autopilot's side. Each red piece is colored by the odds the autopilot gives it of being the Flag.

GOTG AI · Replay of one game

Its top Flag suspect was red's real Flag on every move of the game

LTCPVTSPY1LTMAJCOLPVT4★FLGCPT21%0%0%28%4%48%
Move 133 / 133

Blue's Flag moves A7 → A8. It's on the far row: blue wins.

Odds a red piece is the Flag

<1%9%25%49%81%+
Ruled outBlue's Flag
Odds on red's real Flag
48%
Red pieces left
6
A blind guess
17%
Odds on red's real FlagA blind guess: 1 ÷ red pieces left
The tuned autopilot (blue) against greedy (red), one of its arena games. Each red piece is colored by the odds the autopilot gives it of being the Flag, re-solved after every move. Press play, drag the slider, or drag along the chart.

Its top suspect was the real Flag from the first move to the last, climbing from 9% to 48%. But the autopilot never took that Flag. Watch the gold ring instead: from move 97 on, it walks its own Flag up the left edge and wins on the far row. That habit is most of what tuning taught it.

How it picks a move

The autopilot only looks one move ahead. For every legal move, it asks how likely it is to win from the position afterwards. A challenge is a gamble, so it scores every way the fight could go and weighs them by their odds.

GOTG AI · One challenge

A challenge is scored as a blend of every way it could go

My Major challenges a piece it can't see

  • 50% it's a Private, so my Major wins

  • 30% it's a Major, so both are removed

  • 20% it's a Colonel, so I lose my Major

WIN 50%

score = 0.5 × score(win) + 0.3 × score(trade) + 0.2 × score(loss)

The autopilot scores the position after each outcome, including what that ruling would teach it about the red piece. Then it weighs the three scores by their odds. The bar is how the app shows a challenge's odds under the target piece.

A position's score comes from 15 features of the board, like material, enemy pieces next to my Flag, and how far my Flag has advanced. Each feature has a weight, and the weighted sum goes through a logistic curve to become a win probability.

Letting it tune itself

I set those 15 weights by hand, and with my guesses the autopilot scored 68.7% against my greedy bot, counting a draw as half a win. Greedy also looks one move ahead, but ignores what the rulings reveal. Hand-set weights are guesses, though, and the features interact in ways that are hard to reason about. I'd rather the bot found out for itself.

The tuner uses SPSA, which is simpler than its name. Each step nudges all 15 weights at once, randomly up or down, plays the "+" version against its mirror-image "−" version for 64 games, and moves the weights toward whichever won. I ran 100 steps, 6,400 games, on 10 CPU cores in 26 minutes.

What it learned

The biggest moves were Flag weights: flagAdvance up, flagAttackers and flagRun down

How far tuning moved each weight from my hand-set guess, in scale units: roughly the smallest change that shows in play, set for each weight. Hover a bar or open the table for the actual values.

RaisedLowered
100 SPSA steps of 64 self-play games each.

The biggest moves were all about Flags:

  • flagAdvance went up the most. Each step its Flag takes toward the far side is now worth over three times what I gave it.
  • flagAttackers went down. Enemy pieces next to its own Flag count as much worse.
  • flagRun went down, which surprised me. It measures whether the Flag could walk home uncaught right now. My read is that once flagAdvance rewards every step forward, flagRun no longer needs to shout, and a loud one may have made the bot bolt too early.
  • material went down. When you can win by reaching the far side, being ahead in pieces only helps if it gets your Flag there.

Did it work?

The real test is the arena: 1,000 games per pairing, with colors alternating, from starting positions the tuner never played.

Tuned, the autopilot scores 91.1% against greedy, up from 68.7%

Score is wins plus half of draws, over 1,000 games per pairing. Whiskers show the 95% confidence interval, and the dashed line at 50% is an even match. To pass, the whole interval had to clear it.

Arena games on starting positions the tuner never played.

The tuned autopilot scores 91.1% against greedy, up from 68.7%, and 72.5% against my hand-set version. It also changed how it wins:

Wins by walking the Flag home rose from 224 to 443, and losses fell from 307 to 87

How each of 1,000 games against greedy ended, before and after tuning.

Won: took the FlagWon: Flag got homeDrawLost
The same arena games as the ladder.

Wins by capturing the enemy Flag barely moved. Nearly all the gain came from walking its own Flag home, and losses fell by more than two thirds. The bot learned to run. The cost is that its Flag gambles more: a Flag only beats the other Flag, and losses where its own Flag challenged a piece and lost went from 4 to 13.

What's next

The next bot, the Expert on the site, takes the autopilot's six favorite moves and plays each one 16 moves into the future against sampled guesses of the enemy's hidden ranks. It scores 91.5% against this autopilot. That's the next post.

Try to beat itPlay the autopilot on gotg-ai.vercel.app, or move up to the Expert if you win.
Written byLance Endaya

Keep reading

Next storyHi, I'm Lance