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. 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.