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. Arainach · 1790970570 · focus · HN ↗
  > Those new additions can invalidate the whole training data by a single new "card" that changes completely the dynamics
  This doesn't follow. You're basically proposing that new combo decks be added all the time, and it's far simpler for an agent to scan the new cards for potential interactions with the thousands of other cards in circulation than for a human to remember all of them.
  Your analogy is akin to saying that all you have to do is keep landing new code all the time, and since the agents weren't trained on the code they won't be able to identify and respond to security vulnerabilities in it as fast as humans, which hasn't turned out to be correct
  1. [deleted] · 1790972552 · focus · HN ↗
    [deleted]
  2. hnedeotes · 1790972916 · focus · HN ↗
    No, well, in MtG you could interpret it as meaning such but what I mean is that if in the training set sequence A-B-B-A when state is C-A-X-Y is the play 80% of the time, then you have a new card (that doesn't need to be combo) that by sheer mechanics thwarts that then that strategy won't stick by the addition of that single card to the opposing deck (that you can't know if your opponent is playing or not) and having one or 2 or 3 or 10 different cards renders every calculation very problematic as a play can be the best or the worst depending on such simple things diluting further the best play as the pool grows. Then you need to take into account in MtG shuffling and drawing. I think it's fair to say it's much more difficult to model... And while an agent can learn new combos, you just need to read the card once, the agent needs to be retrained.
    ironSkillet · 1790977257 · focus · HN ↗
    Doesn't this entirely depend on the latent embeddings of strategies and game space in the AI model, which may not be so concrete and explicit as you've described? That's kind of the magic of LLMs with coding, they can generalize because the abstract patterns are encoded in latent space, not the specifics.
    hnedeotes · 1790980066 · focus · HN ↗
    I might be wrong but what I was thinking was that in chess (or even imperfect information games with a much smaller "range" such as Stratego,) a model can calculate all possibilities for all moves and following moves, by itself and opponent up to a depth that the human cannot. So it can see everything that can happen if it does move X-Y, then Y-Z, then A-C and figure out one that is unbeatable no matter what (or at worse leads to a draw).
    But on MtG in particular that never really applies in full due to drawing new cards. You can play perfectly and still lose due to sheer randomness of draws.
    The latent space I'm not sure how it translates to a game playing bot, but I would imagine that it would open it up to fail in the same ways a human fails.
    On the game I'm designing it could do that (calculate all possibilities up to X depth, for all possible scrolls and table states) but it would be extremely expensive to do so (not a very good argument if compute power keeps increasing), but more than that, in contrast to something like chess, there can be many more paths and decision points where a bad decision turns into a loss, so if it assumes that the best play is X at some point, a sequence that it discarded due to not being the most probable can exist and the bot can never be sure, so if it makes a decision that plays into a "trap" he can't undo to a favourable position. While in Chess it's much clearer what is possible from a given state, it's unambiguous and the rules are fairly limited.
    In stratego you have a 10x10 board game, a very clear objective and at most 40 pieces (with repeated pieces and simple mechanics amongst them), while in MtG and similar games a single piece (card) can have probably hundreds of different interactions depending on everything else going (and everything else hidden), at many points of decision. In stratego it also seems that for humans at least, most moves are "inconsequential", as it probably plays more at the psychological/bluff level. Maybe a human player that was given the same budget for training could spend a month training against bots might fare better as the strategies might be then better understood (by the article it's mentioned that the agent recovered from bad positions, so it seems that it was mostly human error, as the human was playing better up to that point).
    While on MtG or Asummon, although there can be inconsequential moves (they don't matter given the context/stage of the game), every move carries with it a possibility of being consequential in unpredictable ways. Anyway, there should be ways of training models with just a rule abiding client for these games, without codifying all rules, that they can just keep playing to figure out the interactions, so if that theory is true then it should be possible to create an unbeatable bot - I'm just not sure it is without infinite time/compute and less so if the "meta" keeps changing rendering possible training inconsequential regularly.
2. 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. hnedeotes · 1790972193 · focus · HN ↗
    MTG is also severely constrained (small hand, mana -> possible moves) although I don't think it's anywhere near the same. In my opinion the rules are effectively what change the whole dynamics. You can't plan as efficiently without knowing what your opponent holds and having to take into account all possibilities (with infinite energy/compute time perhaps)... I don't doubt you can train a model to play well, I just think it should be much more level to the human player. In MtG you also have the randomness which is not easy to model nor account for - the perfect play by an LLM can be the worse once the opponet draws next.
    In my own game you don't have shuffle/draw randomness but the pool of options is statistically tending to infinite (if I would have 500 or 1000 scrolls designed and MtG depending on the format has that depth) when compared to something like chess, or this game. On the other hand in my own game you have to account for much more depth on the possible options your opponent has.
    dragontamer · 1790974010 · focus · HN ↗
    There's only so many card interactions that strong players actually think about.
    Ex: you don't really care if the opponent plays Giant Growth or Chastise. The effect is that the opponent is playing a combat trick, and combat has moved from attackers favor into defenders favor.
    To defeat an instant speed combat trick requires a combat trick of your own, or a generic counter spell of some kind. Some have interactions (ex: Doom Blade beats Giant Growth but not Chastise), but the overall gist is that opponents can do things after combat is declared. You only need to keep track of how many combat tricks you think the opponent has.
    ---------
    Other situations are card advantage (ex: 2 for 1. If the opponent spends 1 cards to defeat only 2 cards of yours). The traditional card for this is Mindrot, but well placed counterspell can turn a combat trick into. 2-for-1 reversal.
    You don't necessarily keep track of how your opponent makes 2-for-1 opportunities. You just have vague gists of them.
    ---------
    Good spells have huge applicability. Doom blade or Murder is high because killing opponent creatures at instant speed handles the vast majority of creature buffed combat tricks, and also serves as a way to stop enemy combos and other such tricks.
    In contrast, chastise is very niche. If the opponent were playing like Swords to Plowshares (powerful white instant speed removal), it's pretty much always better than chastise.
    If the opponent plays chastise instead, you take that as a win because you know they could have had a deck of better cards. But for whatever reason decided to play with weaker cards...
    hnedeotes · 1790976015 · focus · HN ↗
    I agree in a way, but at the same time, and I think it's a bit more applicable to MtG due to the limit of cards you can have as possible plays at any given time (outside of combos), and I believe too that you can train a bot to be good, better than average - I doubt arena doesn't have bots - but I still think that without unbound compute/time it's a game where human players have much better odds to outsmart an AI if they're good players. MtG has for the past 10 or more years been re-hashing the same play patterns, while introducing some new mechanics on most cycles, but pretty much you have staples throughout most editions that are just variations on that - card advantage, denial, combat tricks, removal, curve and then the rarity enabled bombs/combos
    But even then (not saying I'm right) I think the depth of choices, effects and so on, on a format like modern, or legacy, would be very difficult for an AI to top against pros. If you add draft into the mix it gets worse for the AI in my view too.
    Because a good play in most situations can easily be a bad play under others. That doesn't happen in chess for instance, given enough decision depth to the algos to see the future game. In my own game I think those situations can occur much easier due to you always having your full deck available. Also, in MtG it's easy to get into table states that are either ahead/behind and then you kinda just have to protect your position (like with denial decks). Then you have the effects that you might remove a creature threat (graveyard) but then that enabling a combo you weren't expecting that needs a creature on the grave, or enabling delve cards or whatever have you. It's much less clear cut for a probabilistic model to make the optimal play at every single interaction. So the more you train the model on all the variations and possible follow ups, the more you dilute its certainty isn't it? In chess, or this game, or RTS such as starcraft, that doesn't really happen in my view.
    dragontamer · 1790982235 · focus · HN ↗
    I'm also a Poker player and the way Poker AIs solved this problem was by making the best estimate of the Nash Equalibrium and playing around it.
    No human can possibly keep up with all the possibilities or combinations that are accounted for.
    Games of incomplete information have been IMO soft-solved as of.... Maybe 5 years ago? As in, stronger than any human can possibly reach (ie: massive GB-sized matricies accounting for all information iterated over millions of iterations of "he thinks that I think that he thinks that I think that....")
    It's not a true Nash Equalibrium, which remains outside of the realm of even computers to compute. But a computer can always reach a closer / better estimate of any Nash Equalibrium, which covers all games of incomplete information.
    --------
    For Poker, it turns out that a few types of bet sizes (3x pot, 1.5x pot, pot, half pot, quarter pot) covered enough betting patterns to reach superhuman.
    And frankly, MtG is simpler than the bluffing game in Poker. Like MtG has bluffs but it's no where close to Pokers level.
    There's no crazy deep game for Red Deck Wins vs Control. The game basically plays itself out (Red tries to win before Control comes online. Control tries to stall before Red Deck Wins). There are some games with complex board states but they're largely a game of bluffing + card counting (opponent holds 4 cards, two of which were since the start of game and 2 were top decked in the last two turns. He at best has only planned for 2 responses or got lucky with the other two newest cards. Do I have a play that beats two cards yet?)
    syradar · 1791014430 · focus · HN ↗
    The card counting is harder since we can hide which cards were top decked or held since the start by just rearranging/shuffling our hand. We could have 0-4 counters or setups waiting for the gating decision.
    The possible game state is also much larger than poker. Deck construction alone is 60 cards out of about 30,000 unique cards. Sure, not all cards are viable in all decks, but we can have 1-4 copies of a card in our deck.
    So we might not even know if we’re playing against mono-red or multicolored since the decklist is unknown. You can think you’re playing mono-red and then they suddenly play a Plains. Poker at least always has the same 52 cards to reason about.
    I do think AI could be great at coming up with decklists though.
    hnedeotes · 1791028474 · focus · HN ↗
    Yeah I am of the same opinion. And of those unique cards (although formats will limit the total number) they all can play differently in different contexts/states of the game - even a "bear" (2/2 vanilla), can be just a bear, or part of a strategy (if other cards pump those specific cards being played, or enhance them), while poker they're always evaluated in aggregate from 52 cards that are split between players, so you can always remove the ones you're holding, the ones on the table. So 48 cards to calculate possibilities after initial deal + whatever is on the table. The fact that they're shared also means you can exclude immediately what is revealed and what you hold on your hand from those calculations.
    hnedeotes · 1791029575 · focus · HN ↗
    Hm, I don't really agree. I think that bluffing feels more important in poker because of the usual monetary value attached, and is more of a strategic hindrance when playing against bots, while it's very important between humans because (usually) of the money involved - even in this article there's a mentioning that the bots don't care about bluffing and that for humans that is part of the normal gameplay and mastery.
    There's also the decision points, in poker it's way less. You're dealt cards, the table reveals cards, you bet/ante, move to the next, bet/ante. It's a very finite sequence of moves until disclosure. Plus it's 52 cards divided by the table players while on MtG it's 60 per players that you can't know (even lands can interact beyond being a resource and in competitive lists usually they do, specially in older formats) - although with enough/infinite time/memory you can probably generate a table for all possibilities, you still have to contend with the interactions other than the card types. A 9 Diamond is a 9 diamond. A Skull Clamp is a Skull Clamp but the way it interacts, its value/threat is highly dependent on context that can/might be hidden.
    While I think that MtG is indeed "poker" like underneath the keywords, it's many more levels and I think bluffing can be way more "complex" but simply isn't because even at the pro-tour level prize pools are insignificant when compared to serious poker tables. Some MtG players are known to also dabble/play poker regularly.
    I also think that the structure of poker game-play is more prone to be exploited by a competent bot - if you have a "budget" and you assign a bot to a table where the antes are "in-line" with the "budget" it has, it can mathematically (within a very high degree of probability) always turn a profit - ultimately humans fail in part because they enter "bluff" kingdom against a bot as the bots can just rely on mathematical probabilities. Made up numbers but the idea being, you have $200 to play. Choose a table where this allows you to play X games at least, say antes of cents, it should be able to make money most of the time at some point.
    Yes, but as the other reply mentioned, the thing is you don't know if it's red deck wins, or a RDW with a tweak for the metagame and building the "he thinks that I think that he thinks" tables would probably require for practical terms what could amount to infinite storage and any of these chains, if followed through, can land the bot in a losing position hard to come back from. Now, to be honest, most MtG players aren't that good either, they play it more like a hobby/fun game, rather than approach it as poker/probabilities.
  2. wavemode · 1790973410 · focus · HN ↗
    > There is nothing that, in principle, makes MTG different from poker or bridge
    There is - metagame. There is no universal optimal strategy in a trading card game, because what is optimal depends on what decks and strategies other people are playing.
    I'm sure you could train a neural network to play a specific deck within a specific metagame of a specific card game, but you would probably have to keep re-training it when there are new decks/combos/releases/rotations/banlists/metagame shifts.
  3. Marazan · 1790977945 · focus · HN ↗
    > There is nothing that, in principle, makes MTG different from poker or bridge
    Only in the most general form they are games with cards and hidden information with a state space that some form of tree search can theoretically play out.
    The difference is the size of the search space. In MTG the search space is unimaginably huge. It would make Go's search space look like a spec of hydrogen in the middle of the universe.
    It would require completely different techniques to produce a computer good at MtG than one that is good at bridge.
  4. 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.
3. xpct · 1790974932 · focus · HN ↗
  You can definitely try to regularize against ruleset changes by generating a bunch of cards and making the agent play in randomized subsets of those cards.
  I didn't look for prior work on this, but my estimate is that it's probably within 2-3 orders of magnitude of additional training compared to a static game. (Still a lot!)
  1. hnedeotes · 1790976145 · focus · HN ↗
    But wouldn't (couldn't) the model then hallucinate play patterns and get itself into problems when playing against a real opponent?
    xpct · 1790977940 · focus · HN ↗
    Well, if your training includes regularization against ruleset changes, the model should simply handle it. (that would be the expensive option, and require vastly more training)
    When the Dota 2 bot was made, they retrained the bot only partially when new patches came in, so it was definitely cheaper to adapt.
4. empath75 · 1790977024 · focus · HN ↗
  Hearthstone is absolutely swarming with bots that beat humans regularly.
  1. nkrisc · 1790977195 · focus · HN ↗
    Which humans? Many people are simply not that good at Hearthstone. Are the bots regularly achieving high legend ranks?
5. gus_massa · 1791036489 · focus · HN ↗
  Like once a month, a different person submit a variant of chess to HN. I played a lot of chess when I was a kid, so I try most of them.
  IIUC most of them just put a standard chess engine over the new rules. I consider I'm not a bad player, but the engines destroys me, even with the weird rules.
  * <a href="https://chess39.com/" rel="nofollow">https://chess39.com/ I only win if the computer start with a very bad initial position and in the first 2 or 3 moves I get huge advantage, because I slowly lose the advantage. Hopefully the game ends before I lose all the initial wins. Sometimes the computer "gives up" and exchange pieces unnecessary, that is not the optimal strategy when you assume the opponent (in this case me) is a worse player. Perhaps it's necessary to train to AI to pay assuming the opponent may blunder.
  * [Another variant I can't find now. Each piece changes when it moves P->N->B->R-Q->P->...] The changes of the pieces confuses the engine too much and it's easy to win using some tricks. I guess some variants are just too different and need a lot of additional training.
  1. hnedeotes · 1791041612 · focus · HN ↗
    But chess39 is just plain chess with changed initial board states right? That doesn't seem like anything different from the point of view of an algo/bot.
    I used to play a bit of chess when I was young too, but never sticked to it nor got good at it either, but the complexity is pretty low relative to other games - specially when we talk about automated/bot scenarios.
    In the variant you mention now imagine that every piece can have hundreds of different interactions depending on the other pieces on the table plus other pieces outside the table that the bot can't know for sure - I would imagine it would make the bot much weaker overall and specially against a good player independently from training - it just doesn't seem to make mathematical sense that it wouldn't but it's not my area of research so I can be missing some important thing.
    gus_massa · 1791043011 · focus · HN ↗
    Yes, but I'm surprised the chess bots are good even with impossible pieces combinations.
    [spoiler alert]
    My favorite strategy for Ches39 is using 13 bishops in the 4 and 3 ranks. That is outside the training set, or at least any sensible training set. (Protip: Learn how to check mate with only two bishops of different colors.)
    For the reverse I'd like to give the AI 13 knights, that would overwhelm any human player. I never dare to try it.
    And I think the wall of 39 pawns is a good idea for a human, but for some reason the AI beats me anyway.
    hnedeotes · 1791052616 · focus · HN ↗
    I think that comes from the way they can "learn" the game. I don't think more modern models rely on the knowledge of how many pieces there are in the game, probably they model it as given these pieces in this grid table, and rules for each piece and player actions, how do you reduce the state of the table to one where the opposing player has 0 kings (the rules probably can just be the engine replying invalid move don't even need to be stipulated, would be my guess). Then you could generalize it to any sized grid, with how many pieces you wanted, even 2 or more kings per side. At least that's how I imagine it to go or how I would try to do it.
    To be honest haven't played chess for years - I did MtG for a while even as I got older but then it just annoyed me and haven't played in years - it was when I started working on my own take on tcg's
    vikingerik · 1791069686 · focus · HN ↗
    I beat Chess39 on my second try on the hardest setting, using a wall of all pawns (27 pawns and 4 bishops.) Keep advancing your rear pawns whenever there's space so that no pawn is ever unprotected. Eventually the pawns will advance far enough that the opponent has no room and you'll start getting traps and forks.
    The key is to make sure you never leave a defensive opening - you have to watch out for two enemy pieces attacking a pawn that's defended only once. The computer/opponent will sacrifice the first piece to get the second to break through behind the pawn ranks, and it can often demolish all the pawns from there or checkmate your cramped king.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.