Thread

With most information hidden, the game Stratego had stumped AI until now

288 points · 149 comments · PaulHoule

hnedeotes · 1790969271 · focus · HN ↗
I think that what makes these games beatable repeatedly is that they're static. Not saying an algorithm properly trained won't play better than the average player a game like MtG, or my own <a href="https://aethersummon.com" rel="nofollow">https://aethersummon.com (specially now while it has under 90 possible scrolls only) but if you have a regular release cadence (say weekly or bi-weekly) of relevant new "cards", then I think the playing field is much more even for humans.
Those new additions can invalidate the whole training data by a single new "card" that changes completely the dynamics and would be easy for a player to understand and incorporate but not for an algorithm (perhaps with enough compute to re-train it regularly it could) - that along with the decision trees being orders of magnitude deeper, wider and with more conditionalities than go, chess or stratego - even through the same turn with the same cards available and same table state - would probably pose much harder problems for a compute bound algo.
1. qsort · 1790970847 · focus · HN ↗
  There are very few missing pieces for a game like MTG. The main reasons we don't have a Stockfish for MTG is that it's a PITA to implement the rules and that nobody cares (or at least not enough to make it happen.)
  There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
  1. askjdfksdbfhk · 1790986651 · focus · HN ↗
    >There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
    We don't have superhuman play for bridge.
    Poker and bridge are quite different from each other in terms of solving them. Among other things, the hidden information space in poker (at least, in hold'em) is far smaller than in bridge (or Stratego, for that matter, as discussed in the linked paper). This makes hold'em solvable using CFR, an algorithm which essentially optimizes play by considering all the possible holdings than the opponent might have and their best strategy with each one. Even going from two to four hidden cards per player (Omaha) requires a slightly different approach although you can still use CFR as the basis for the search algorithm.
    Bridge has 13 hidden cards per player which makes CFR basically impossible to apply, at least in any obvious way--just way too many states. Similarly you see it's not used at all in this Stratego paper.
    qsort · 1791009690 · focus · HN ↗
    Sure, but you can do Monte Carlo with a double-dummy solver.
    The point is that, especially for games perceived as being lower-status like MTG and other board games, I'm more inclined to believe the answer is closer to "nobody is willing to pour in the resources to seriously try" as opposed to "we definitively cannot with current science and technology."
    vmilner · 1791028186 · focus · HN ↗
    I think computer bridge will take off soon. LLMs have allowed double-dummy solvers to move from ~0.1sec to microseconds (if you allow 99.9% accuracy) and parsing human bidding system descriptions must either be possible or v close.
    askjdfksdbfhk · 1791052941 · focus · HN ↗
    >LLMs have allowed double-dummy solvers to move from ~0.1sec to microseconds (if you allow 99.9% accuracy)
    I don't know what this is referring to. The ubiquitous dds library, which is AFAIK basically the only double dummy solver, has not seen any real improvements. Neither of those numbers look right to me, I think it's more in the range of ~10ms.
    There's a crank who was claiming some magical improvements a little while ago that really just boiled down to AI psychosis (and having absolutely no understanding of what he was claiming). I hope that's not what you're referring to.
    vmilner · 1791055496 · focus · HN ↗
    I'll concede an order of magnitude for dds, I may not have been using it optimally. The claims made by Lorand Dali for his neural net solver were a thousand times faster with a slight drop in accuracy (99.9%+ I think)
    I believe this was used in his 'ben' bridge engine, <a href="https://github.com/lorserker/ben/" rel="nofollow">https://github.com/lorserker/ben/ now maintained by ThorvaldAagaard, though I have to admit it now seems to be heavily dds focussed, so there may have been a rollback along the lines you outlined.
    I'm attempting to recreate the concept myself, so should soon have an idea whether its moonshine or not,
    askjdfksdbfhk · 1791088040 · focus · HN ↗
    I see, it sounds like you might be referring to this project from 2018: <a href="https://github.com/lorserker/bridgent" rel="nofollow">https://github.com/lorserker/bridgent with a talk at <a href="https://www.youtube.com/watch?v=CRBNI8UdHhE" rel="nofollow">https://www.youtube.com/watch?v=CRBNI8UdHhE
    I wasn't aware of this although this project had a substantial error rate. Flipping through the YouTube video it only predicted the correct number of tricks 70% of the time--so I'm not sure if your 99.9% is referring to a different project that I'm unable to find, or if you misremembered. I don't think anything like this was ever used in Ben; looking at the commit history, I think Ben has always used the standard dds library.
    FWIW I'm pretty confident that you could beat the performance of the project I linked with a fairly straightforward transformer architecture.
    vmilner · 1791103464 · focus · HN ↗
    Yes - you are right, 70% for a correct answer is what the talk says. Id misremembered the higher (~99%) numbers because for my purpose (simulating many random deals compatible with known cards to get probability distributions on hidden card positions and trick taking possibilities in each suit/notrumps ) a one trick error is quite acceptable. I agree a more straightforward architecture is a promising approach. Once I have generated weights in a form usable in C, I am also curious as to whether they can direct DDS's tree search as a kind of probabilistic oracle.
    (There was some Ben code to use a neural net double dummy evaluator, because Ive used it, but it was removed. Ill try and find the git point it was removed.)
    vmilner · 1791139681 · focus · HN ↗
    <a href="https://github.com/lorserker/ben/tree/78c3690f34ed945f95f3c192243c56cf6e24852d/src/examples" rel="nofollow">https://github.com/lorserker/ben/tree/78c3690f34ed945f95f3c1... (look at SingleDummyEstimates.ipynb )
    also the keras model ben/models/TF2models/RPDD_2024-07-08-E02.keras is still present in the current repo but not apparently used. It was trained on ten million deals where all double dummy info is known.
    askjdfksdbfhk · 1791052332 · focus · HN ↗
    Monte Carlo with a double-dummy solver is fundamentally insufficient for good single-dummy play because it is incapable of understanding information. It won't take discovery plays (lines aimed at discovering more information about the opponents' hands before choosing a line of play) and will systemically overvalue positions which are good double dummy but require a guess. It doesn't understand falsecarding (because double dummy, it doesn't matter).
    I agree that many games could make progress if people were actually inclined to try.
    I think it will get a bit better in the coming decade thanks to continued hardware improvements & powerful LLM coding agents making it more feasible for amateurs to tackle these things at home. Personally I've been working on a game AI project for the last month at home based around published techniques for a similar game, using my 5090 for training and Opus for implementation and orchestrating tasks and so on. It's going quite well and it looks like I'm on track for a SOTA, superhuman AI at the end. Doing this ten years ago would have been incomparably harder.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.