‹ BackHN Continuity

Thread

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

288 points · 149 comments · PaulHoule

  1. SwellJoe · · focus · HN ↗
    I loved Stratego so much as a kid. But, I eventually couldn't find anyone to play with me because I crushed everyone, including my dad who was much better than me at chess. But, I never would have thought it'd be a game that models would have a hard time with. It feels relatively simple. And, inexplicably, I never even thought that there might be serious players...I've kept the board game, one of the very few things I have from young childhood, but it's been twenty years since I played. I guess it's time to find an online Stratego. Surely someone in the whole world can beat me.

    Too bad I never played against an AI before they cracked it.

    1. cainxinth · · focus · HN ↗
      I also enjoyed it. We even used to play live Stratego at camp with index cards in our socks with our ranks.

      What was the secret of your success?

      1. SwellJoe · · focus · HN ↗
        I don't actually know. I had a few strong setups that I rotated through, but even after I started explaining my strategy after every game, and even giving hints during the game, my best childhood friend would still lose so much it wasn't fun for either of us so we stopped playing. He's smart, and was fine at most games, but no match in Stratego. I guess I'm just good enough at the various aspects of the game, memory, bluffing, planning, that it added up to being a pretty strong player even without much in the way of study or practice. I'm sure I'd crumble against an actual serious player, and would have back then, too, it was just that I wasn't around anyone else who liked the game enough to become good at it.
      2. SamBam · · focus · HN ↗
        I'm curious. I could kind of see that being fun, but I could also see 1 person moving with 79 standing still, and two players who get to make all the decisions. Did you guys modify the rules?
        1. cainxinth · · focus · HN ↗
          Very little standing still. Everyone is running around. It's a bit like capture the flag, except when you tag someone you compare index cards to see who is higher rank.
    2. WalterBright · · focus · HN ↗
      I, too, remember figuring out a strategy when I was around 11, and never lost a game after that.

      It's been a loooong time, and I don't recall all the details. But it revolved around doing probing attacks to determine where the ranks were in the enemy formation, and then having "channels" in my side to move up a soldier that outranked by 1 a targeted attack.

      Color me surprised that it would be difficult to write a program to play it.

      1. SwellJoe · · focus · HN ↗
        Most of my setups, though not all, revolved around bombs and strong soldiers held in reserve behind the bombs, sort of a rope-a-dope...sometimes, I'd kill all of their miners before the bombs surrounding the flag could be disarmed which guarantees no quick win for them. There are risks to that, in that the strong pieces can be stuck while the opponent picks off everything else, but even once people knew I regularly did that, I could still win pretty much always, so it's more than a strong opening layout.
        1. WalterBright · · focus · HN ↗
          Sounds good. My "channels" were a way to move the right pieces to where they were needed. I did this repeatedly, and my opponents never learned.

          One thing Stratego did was implement the "fog of war". My Empire game took inspiration from Stratego and Risk.

          1. SwellJoe · · focus · HN ↗
            In hindsight, maybe Stratego in childhood is part of why I love Civ games so much, which, I think, tickles a lot of the same brain parts. The setting up the board part is heavily why I liked Stratego so much, and in Civ games, you get to plan your cities and empire. Or, maybe it's just the kind of game I find satisfying, and Stratego was the first instance of it I played.

            And, I'm also working on a game that kind of pulls on that same kind of upfront planning, where how you place your pieces to start is as important as how you move them; a settling and strategy game that's heavy on clever defense and using terrain and the interplay of pieces.

    3. VladVladikoff · · focus · HN ↗
      Stratego has a special place in my heart. I have fond memories of playing it with an old family friend. Later in life I sought out an old set off eBay so I could play it with my kids. I really love that game!
    4. Cider9986 · · focus · HN ↗
      It has such a strong story despite being so simple.
    5. m463 · · focus · HN ↗
      > But, I eventually couldn't find anyone to play with me because I crushed everyone

      I think this is a problem with many deeper games. I remember going over to other people's houses and they would pull out obscure-board-game-xyz. The rest of the night for me was trying to figure out how to play, while others were 30 steps ahead of me.

      I think you need something like chess club - stratego club - where people have all gotten to the nuance level and you can play with people of appropriate level.

      1. zahlman · · focus · HN ↗
        I feel like the depth of a lot of board games gets undersold simply because of how inconvenient it would be to play a large number of games physically. And/or because it's easy at the start to try something complicated, fail to get it right and end up concluding wrongly that only the simple things actually work.

        At one point in my life I got in literally thousands of games of Dominion, and I was definitely still not as good as some of the people I discussed the game with online, but in person I could barely find anyone to play with, ever. (In fact, of the people I knew who were familiar with it, few even seemed to think it was any good as a game.)

        1. xyzzy_plugh · · focus · HN ↗
          I've played a lot of Dominion with people who have played thousands of games. I've even beat them with some frequency (it's not that hard!).

          I don't think Dominion is a good game. It's good if you maybe think cubing is good. And it can be a lot of fun!

          But as a game? It's not good. If you have no idea what you are doing and are totally unfamiliar, you can even win pretty easily with some luck. But you won't understand why you won, or rather why others lost.

          There are many, many games where everyone can read the rules together and be, more or less, on even footing. Dominion can sometimes be that way, but it can pretty easily be extremely opposite of that.

          1. SubiculumCode · · focus · HN ↗
            Or another way of saying it, when the default no-thinking baseline strategy can win frequently enough by chance that it becomes difficult to learn from a single game. In this case, just 'buy silver, then gold, then provinces) can win too often just by chance.
            1. eszed · · focus · HN ↗
              Yeah, but that's what makes it such a good game, in my opinion. Ten or so years ago I played a lot with / against two friends. With other "deep"(-ish) games someone who's never played before never has even a remote chance against experienced players - we had other games we'd never pull out with a n00b at the table - but with Dominion you can give them that strategy, plus a few tips, like "trashing cards is really helpful", and they know enough to hang. They'll lose, mostly, but they won't be immediately crushed, and they'll want to play again.

              Anyway, the main fun is trying to get an approach working with unfamiliar card combinations - and yes, we owned all the expansions, thank you for asking. :-)

              1. kelseyfrog · · focus · HN ↗
                There's a level of play in Dominion where it feels like there's two turns. One starts before the first card is played where you devise a strategy given the board. The second is just playing it out. Dominion leaves very little room for strategy switching - if you devise a second rate strategy, there's no realistic way to catch up. Very little of a player's choices depend on the actions opponents have taken. Short of a stack running out, curses, and a few others, you're mostly playing solo. That lack of being able to adapt is why I can't, even after hundreds of games, I can't bring myself to play it anymore.
                1. eszed · · focus · HN ↗
                  That's a fair point. Fortunately, most games are short enough that you don't lose a lot of time when that happens. Mostly, though, I see a way I could have tweaked my card mix a bit to have made it work, so I want to play the same board again.

                  But, sure, if you're looking for a game with a lot of player interaction then Dominion isn't for you.

          2. GoatOfAplomb · · focus · HN ↗
            >If you have no idea what you are doing and are totally unfamiliar, you can even win pretty easily with some luck. But you won't understand why you won, or rather why others lost.

            Interesting, this is a _feature_ of poker games like Texas Hold'em. If the losing players didn't go on convincing winning streaks, they'd stop playing. And those winning streaks can convince them they don't need to learn anything else about the game in order to be a winning player.

            1. xyzzy_plugh · · focus · HN ↗
              The key difference is gambling.

              Have you ever gambled over a game of Dominion? I wouldn't.

              Have you ever played Hold'em without gambling? I wouldn't either.

            2. matwood · · focus · HN ↗
              I’ve played a lot of Hold’em and don’t really see that. Sure, any single hand could be won with luck by a clueless player, but even over a short amount of time, the lesser player will lose.
      2. kulahan · · focus · HN ↗
        Board games really get so much better once you get a vaguely-regular group. If nothing else, you can walk in one night and everyone just knows how to play a lot of really great games right off the bat.
      3. ew-dev · · focus · HN ↗
        Digital Board Games solve this imho very elegantly, since the rules are tracked by the engine for the players (and is always impartial). It also can avoid the onboarding friction.

        Just a pity it does not come close to the haptic pleasure of playing with a real cardboard, polished resin figures, and sturdy cards with dice (or whatever accessories are supplied) :-)

        1. distances · · focus · HN ↗
          Indeed. Online games, Board Game Arena especially, are great for the ease of the rules enforcement and getting together with remote friends. But if given an option, I would always choose the in-person physical version. I'm spending enough hours in front of a monitor already.
          1. thaumasiotes · · focus · HN ↗
            > Online games, Board Game Arena especially, are great for the ease of the rules enforcement

            That's true, but it has the odd side effect that the entire play group may be just plain unaware of important rules.

    6. NDlurker · · focus · HN ↗
      I love Stratego. I used to play with my girlfriend and my brothers. We started playing with different rules too to switch it up. Like moving bombs or the flag. Or playing with the pieces reversed. Reversed pieces were interesting because the hidden information was swapped, made for some funny games.
    7. karim79 · · focus · HN ↗
      > including my dad who was much better than me at chess.

      My experience as well unfortunately. No matter how many books on chess I read, no matter how many games I played against Battle Chess to try to get better, he always won.

      1. wafflemaker · · focus · HN ↗
        Makes me wanna play against Swell Joe's Dad \s

        But about having nobody to play because you crush everyone - as long as you want to play to enjoy and not just always go full-on try-hard mode - just stop crushing everyone and you'll have people to play with.

        Let people win every third game. If you're good enough (at it), they won't notice. They'll have a good time and you will. In Tekken it works to have them win some rounds (extra points if you let them have two out of three), but still win the match, tho maybe only if you're not just 2 ppl playing.

        That's a rule established from rat behavior observation study, you can hear about it in every third jbp lecture.

        Ever since implementing it, I never end up with nobody to play with. Just curb your wanting to always win and focus on maximizing the amount everyone enjoys playing in the long run.

        Even a game where there's always a winner and a loser doesn't have to be a zero sum game.

        1. SwellJoe · · focus · HN ↗
          "But about having nobody to play because you crush everyone - as long as you want to play to enjoy and not just always go full-on try-hard mode - just stop crushing everyone and you'll have people to play with."

          Sure, I'll go back and tell my 12 year old self to do that.

          But, actually, I did do that, to some degree. As I mentioned, I would drop hints and talk about my strategies in games, usually after the game, so he could be more competitive and understand how I was thinking about things. That also has a cost on the fun for both parties, though. Smart people can recognize when you're going easy on them. Nobody normal likes being pandered to.

          1. matwood · · focus · HN ↗
            I don’t know stratego, but could you play to put yourself in a tough position and then dig yourself out?

            This is what I do when training jiujitsu with less experienced people.

            1. SwellJoe · · focus · HN ↗
              You could give yourself a terrible setup. A significant portion of the game is how you place the pieces and there are definitely challenging/risky options. Flag in front with no bombs protecting it is bound to lose, but the game won't last very long either.

              And, I did that kind of thing sometimes, though I was a kid and still liked to win, I doubt I used any truly suicidal setups.

        2. opan · · focus · HN ↗
          I'd also heard about that rat experiment (probably on HN) and also tried applying it to fighting games since my friend I usually played with seemed to get really mad most of the times we played. I think it worked somewhat, but then I told him what I did and he didn't take it well. I kinda get why he'd be mad about losing, but then he never plays without me, doesn't spend time in training mode, doesn't watch videos on the games, etc. Not sure what he expects then, I don't think he's gonna improve much jumping right into a real match while rusty and possibly not even understanding all the fundamentals. Not sure there's a solution here since you can't really force people to care about or like things. Ideally we'd both keep striving to improve and competing with each other, but instead I hear "I'll never be better than you anyway". I'm not even god-tier at FGs, I'll lose 90% of the time if I do online matchmaking. I'm just good enough to have trouble getting new people to play with me.

          The rat strat may be worth revisiting but it's not very fun letting people win, and it feels dishonest and disrespectful as well. The closest thing I've found is to play super defensive. If I try to take as few hits as possible and drag out the battle it still serves as practice, and I kinda let them set the pace.

          1. fn-mote · · focus · HN ↗
            I can’t believe I’m giving social advice on HN, but maybe it will help.

            > I told him what I did and he didn't take it well

            This was a mistake. Ask yourself why you did it. If you don’t have a good answer, one possibility is that it was your ego. Another is your very strong adherence to a certain code of behavior that others do not relate to.

            > we'd both keep striving to improve and competing with each other

            I’m not sure competing with someone who is not on your level is a normal approach.

            I also doubt your friend sees the situation the same way as you. They are more of a recreational player. It’s a level below where you are, but for some reason you want them to care more.

            > I'll lose 90% of the time if I do online matchmaking

            And yet playing in person is important to you. It’s fun?

            > it's not very fun letting people win, and it feels dishonest and disrespectful as well

            At work, you want people on your team to pull their weight even though you could do the job better. How do you keep them from being discouraged? A strategy like this works.

      2. SubiculumCode · · focus · HN ↗
        Chess...I'm in the top 1 percent among regular players on chess.com/lichess, yet impossibly far away from Master/GrandMaster level as to be impossible; their minds are completely alien to me.
        1. karim79 · · focus · HN ↗
          Impressive. Keep at it. I hope you'll find a Eureka moment. I also hope they're not just cheating using AI.
          1. SubiculumCode · · focus · HN ↗
            Becoming such is not my goal; I have too many other interests. It was more commentary about how one might be good, but no where even near competitive, and the journey, even if mentally capable, of improving further would take years and year of full time dedication...because chess is that deep, and because "good" is always context dependent.
            1. karim79 · · focus · HN ↗
              I can relate. I'm in the top percentile on stack overflow (now killed by AI). My only goal was to be "good" in the way you described.
              1. jodrellblank · · focus · HN ↗
                I was in the tens of thousands of points on Stack Overflow, over a hundred badges, into the millions of “people reached”, learning things just to be able to answer, things I have found now in search results and been surprised that it was my answer, and yet so far from being a top contributor it may as well be the Moon.

                And haven’t been back there for years. Reinstate Monica. And shame on the licensing grab.

                1. eks391 · · focus · HN ↗
                  Thank you so much. Whatever the motivation, contributions like yours are what helped hobbyists like me decide that whatever ambition I had was in fact a possible outcome, when I otherwise was hitting infinite walls of my own. And I'm sure for those who turned that hobby into their career, you've helped advance countless improvements to everyone's standard of living.

                  Sure some advancements suck, but that's not on you. Answering the questions publicly for all to see enables everyone, and it's up to them to use it for better or worse.

                  1. jodrellblank · · focus · HN ↗
                    Thank you; I hope it’s been mildly useful to some people. It sometimes feels like a volunteering effort that I can do, which is slightly unusual and most people can’t do.

                    Unlike HN and Reddit “discussions” which bring out the snark and ackchually in me far too often, and rarely seem a good way to “discuss” anything, focused questions and answers can potentially add a small value to the world.

            2. jodrellblank · · focus · HN ↗
              See <a href="https:&#x2F;&#x2F;danluu.com&#x2F;p95-skill&#x2F;" rel="nofollow">https:&#x2F;&#x2F;danluu.com&#x2F;p95-skill&#x2F;
          2. jayGlow · · focus · HN ↗
            I believe there is a type of anticheat to help detect ai usage, there are probably ways to circumvent it but id imagine most of the top players are legit.

            <a href="https:&#x2F;&#x2F;www.chess.com&#x2F;cheating" rel="nofollow">https:&#x2F;&#x2F;www.chess.com&#x2F;cheating

        2. OroPla · · focus · HN ↗
          I lost most of the interest I had in chess as a child when I found out that the way to get better at chess boils down to rote memorization of positions. That&#x27;s not fun.
      3. matwood · · focus · HN ↗
        I remember the day I beat my dad the first time at chess and also my grandfather. Those were big days for me after losing so many times.
    8. FiatLuxDave · · focus · HN ↗
      Does anyone else remember playing Electronic Stratego? The version where the identity of each piece was encoded on the bottom with a series of bumps? It was an even more incomplete information game: attacking a piece would only let you know if the piece was higher, lower, or even, instead of revealing the piece&#x27;s identity. I played it so much as a kid that I can&#x27;t even think of Stratego without hearing that electronic bomb sound in my head. I feel it is actually a better game than the original.

      <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Stratego#Electronic_Stratego" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Stratego#Electronic_Stratego

      1. AngryData · · focus · HN ↗
        That is the rules we used for playing stratego. Attacker reveales his piece number and the defender declared who won, or obviously if both died they were even.
        1. dcrazy · · focus · HN ↗
          Electronic Stratego didn’t even reveal the number.
      2. amenghra · · focus · HN ↗
        Would be fun to build this using cryptography (probably some kind of MPC).
    9. karim79 · · focus · HN ↗
      Question: I need to play this again but there are many different versions. It&#x27;s impossible to decide which one to get. Which is the best one to purchase?
    10. [deleted] · · focus · HN ↗

      [deleted]

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.