Sixty-seven days of engines here opened with the same line of state: whose turn is it. Minimax alternates on it, alpha-beta prunes against it, a tablebase indexes by it. Bidding tic-tac-toe — the Richman game — deletes it. Before every mark both players seal a bid, the higher bid buys the right to place, and the winner pays that bid to the loser. Nothing is ever spent; only the split moves.
Delete the turn variable and minimax has nothing to alternate against. What is left is not a search.
Board, prices and auction log: https://dev48.infy.uk/game/day68-bidding-tic-tac-toe.html
The engine is a price, and it is one line
R(b) = ( min over MY placements R + max over THEIR placements R ) / 2
bid = ( max over THEIR placements R - min over MY placements R ) / 2
R is the share of the pot you must hold to force your line. It sits exactly halfway between the best and the worst thing that can happen next, because the auction is a coin you are allowed to pay to bias, and you bid half the gap — a quote, never a reaction to what the other side bid.
Make the pot 512 and every price is a whole number of coins: a game is at most nine auctions and nine halvings is 512, so the /2 never rounds. Alternation is gone too, so money can buy several moves in a row and eight-nil is a legal board. Reachable positions: 18,753, not tic-tac-toe's 5,478.
The famous draw is a 20-coin band
Price an X line and an O line separately; from the empty board both come out at 266 of 512. Two prices summing past the pot is a draw band: 266 + 266 − 512 = 20 coins. Hold 247 to 266 and it is the drawn game everybody knows. Hold 267 and you buy the line; hold 246 and the bot does. The classic result is true on 20 of the 513 bankrolls — 3.9% — and false on the other 96.1%. Not asserted, played: 513 stakes, two perfect players, 513 agreements, 0 disagreements.
The auction is worth more than the board
A Richman strategy is two things, a bid and a square, and the theory does not say which carries the game. Against one fixed opponent, 600 games each:
| challenger | wins |
|---|---|
| the price, and the table's square | 100.0% |
| the price, and a random square | 80.2% |
| bidding half your purse, table's square | 66.7% |
| a random bid, and the table's square | 56.0% |
| a flat 16 coins, table's square | 2.0% |
Throw the board away and keep the bid: 80.2%. Keep the board and throw the bid away: 56.0%. And the sensible-looking constant — a flat sixteen coins — wins 2.0%, worse than bidding at random, because a constant bidder is trivially outbid at the only moments that matter.
What the sweep contradicted
85 checks and 5,748,757 assertions against three independent solvers, and two of them landed on me.
The exhaustive sweep of all 513 stakes caught a real engine bug. I had written both offence tests as strict >:
return s.me === 2 ? (mine >= own.R[s.code]) : (mine > own.R[s.code]);
O wins tied auctions, so O only needs to match its price while X has to beat its own. With both strict, the perfect player defends a position it could have been buying and hands back a forced win as a draw — at exactly one stake in 513, the boundary one. Self-play never surfaces that.
And my assertion that random-square play must miss the price by more than 0.02 failed. The coin-flip sampler lands on 0.5195 as it should; random squares land on 0.5304. That is a genuine 9.7-sigma separation and only 1.1 points wide. The hand-picked tolerance is gone, replaced by sampling-error bounds — sigma = sqrt(1/4n) — because a number I chose by eye was sitting on a real result.
Part of a from-scratch series — one game a day, vanilla JS, one file, and an engine with no dependencies: https://dev48.infy.uk/gamefromzero.php
Top comments (0)