9 ms·

Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning

131 points by aklein 4y ago

warrenm 4y ago
I haven't played Stratego in decades! Loved it as a kid, though
spywaregorilla 4y ago
Stratego is an odd choice I feel. Evaluating it must be really hard. A significant chunk of the game is just trying to remember which unit is which of the things you've seen so far. Which humans generally can't do very well but machines can do easily. Beating hand crafted bots is good. Can expert humans beat the hand crafted bots? I'm guessing no. Also, what's stratego like without the hidden units? Is that... hard?
- Buttons840 4y ago
  I think the best human players can beat the best computer players in Stratego. Thus, Stratego is an excellent choice.
- janosett 4y ago
  You might consider reading the linked abstract: “… Stratego has been a grand challenge for the field of AI for decades, and existing AI methods barely reach an amateur level of play.”
  - spywaregorilla 4y ago
    Sounds like bullshit to me. I'm not convinced. Here's a paper from 2021 that suggests as much. It's hard, sure, but it's also not really seriously explored. > Compared to other games like Chess and Go, not much work has been done on creating an AI agent for Stratego. As such, the available literature is far and few between, and mostly consists of bachelor’s and master’s theses. In fact, most agents created for Stratego are largely undocumented or closed-source, making it difficult to effectively ascertain exactly which particular methods and techniques have been applied and how effective they were. edit: the claim about bots not beating humans appears to hold, but I'm not convinced its just shoddy bot quality.
    - JoshCole 4y ago
      Just to give a sense of hardness, Stratego's game tree is infinitely larger than Go's game tree, because in imperfect information you select a continuous strategy vector over action space whereas in Go you select a discrete action. Meanwhile Stratego is also infinitely more complex than Go because in Go there are less moves with every move, but in Stratego moves don't monotonically decrease the remaining game length. Beyond those two infinities of greater complexity, Stratego is imperfect information, so it is played relative to the infostate, not the state. In Stratego there are thirty three pieces with unknown information on the first move. We can definitely get a lower upper bound by applying abstraction via domain knowledge, but just so I don't have to deal with the complexity I'll state that there are at most 8683317618811886495518194401280000000 different states associated with the infostate of your first move. Meanwhile, on your first move in Go, you are in at most 1 state. In practice though the average length of a game of Go is ~200ish, the average length of Stratego ~400ish. Much like chess, I would expect optionality to be an important strategic consideration in Stratego. So branching factors are likely selected for such that they get higher by good agents. In contrast to something like Go, the branching factor would tend to diminish over time. Mostly sharing this because I think most people are bad at reasoning about complexity - our mind is really good at making complex things seem simple and simple things seem complex because we can actually deal with the complexity of simple things in their full complexity but dealing with the full complexity of the complicated is intractable. I imagine a lot of people's mind latch onto the things like "we get information so playing well means memorization" and don't pay as much focus to the dizzying complexity; but playing well isn't memorizing. Playing well is playing perfectly according to your uncertainty and it just so happens that as part of doing that you sometimes reduce your uncertainty by scouting.
      - spywaregorilla 4y ago
        This is all technically true, but it's also misleading I feel. Chess and Go have a lot of states, and you need all of them. The entropy of the games are enormous. Move that bishop and the significance of every piece on the board could change. Stratego has verrrryy low entropy. You can only move one piece one space at a time aside from scouts. You can also enter scenarios where the game just simplifies on some dimensions immensely to which some fairly dumb algorithms can win the game. If the enemy loses their top dude and their spy, your top guy is invincible against anything that has ever moved, which isn't victory assured but its probably relatively easy to write an ai to win from that point on. Maybe this is just me but when I thought about stratego I'm pretty sure I only thought about a few units at a time. Moving all of them is a bad idea because of bombs anyway. Your mental model of the game does not consider the state of units in the back row of either side. It probably doesn't even consider all of the units in the front. I also suspect a lot of optimal play is just doing dumb shit back and forth to force your opponent into making the more aggressive move in a lot of cases without technically forfeiting which most humans likely wouldn't do but ai would like to do if not constrained otherwise. But I agree a simple tree search on possible moves is unlikely to work very well until the end game.
- dr_orpheus 4y ago
  > A significant chunk of the game is just trying to remember which unit is which of the things you've seen so far While this does get hard the further you go in the game, a think a more significant portion of the strategy is trying to predict newly moving units based on what is happening in the game. i.e. I just took a 7 unit with my 8. And now my opponent is coming straight towards me with a unit from elsewhere. Is it a 9 or 10, is it a bluff to drive me off, to drive me in to a spot where the actual 9 or 10 is waiting?
  - aidenn0 4y ago
    Did they renumber the pieces? In the set I played as a kid a scout was 9 and a Marshall was 1...
    - wakamoleguy 4y ago
      Yes, around 2000 they swapped the numbers. Most recent versions treat the Spy as 1 and Marshal as 10. Classic versions ranked the Marshal as 1 and Scouts as 9, with the Spy designated as S.
      - andruby 4y ago
        I bought a set to play with my kids and felt like something was off but couldn’t really recall. Thanks!
  - spywaregorilla 4y ago
    Computers are better at such problems.
- Imnimo 4y ago
  From the paper: > Successes in the game have been limited, with artificial agents only able to play at a level comparable to a human amateur, see e.g. (14–20).
  - riku_iki 4y ago
    It could be because no one seriously tried to build competitive AI player.
    - thomasahle 4y ago
      Computer Stratego World Championship has been held since at least 2007.
      - riku_iki 4y ago
        This doesn't bring much information. It could be some students competition. Also, per my brief google search they stopped doing it after 3 competitions in 2009.
- boringg 4y ago
  I don't think you are that familiar with how good Stratego is played. It isn't strictly a memorize where your opponents units are. There's a significant degree of bluffing and posturing.
  - spywaregorilla 4y ago
    It isn't strictly about memorizing where your opponents are, but having a perfect memory would be an enormous advantage, the point of being an entirely different game imo.
    - ghaff 4y ago
      Yes, playing it as a kid I remember one pretty common thing to do was to make movements that made it easy for your opponent to get confused about whether a piece was that known piece or something else. Not the whole strategy but take that piece out and you definitely change the game I would think relative to typical human play. Especially in the context of it normally being more of a kids game.
    - treis 4y ago
      Seems like it would be easy to test. See how the AI does when revealed pieces stay revealed compared to a standard game. Also, given this is online competitive play likely that a significant portion of top human players are cheating and have aides to keep track of pieces.
      - spywaregorilla 4y ago
        > Seems like it would be easy to test. See how the AI does when revealed pieces stay revealed compared to a standard game. It would effectively need to be a different AI to use that information. And what does it play? Humans? Other AI? > Also, given this is online competitive play likely that a significant portion of top human players are cheating and have aides to keep track of pieces. That's a great point. It may even be condoned in some circles.
      - TemplateRex 4y ago
- TemplateRex 4y ago
  The best available bot that is also mentioned in the paper, is Probe. Expert humans will score the same as DeepNash against Probe. The best humans have no trouble recalling every piece that moved, and the square it originated from. Top-level play usually has very few moved pieces (since they are vulnerable to your opponent's general once your own marshal gets revealed), so memory is important but typically not the main bottleneck.
  - spywaregorilla 4y ago
    > Top-level play usually has very few moved pieces (since they are vulnerable to your opponent's general once your own marshal gets revealed), so memory is important but typically not the main bottleneck. Interesting. Is top level play... boring? Stratego doesn't have a lot of nuance to positional advantaging aside from moving forward or back, and while I'd imagine there's stalemate rules, there's probably a lot of nothing moves to dance around getting super minor and uninteresting advantages. Is that a correct statement?
    - TemplateRex 4y ago
      It depends on player attitudes. The maneuvering is simpler than in chess or even checkers, although you can have very intricate multi-piece pincers around the lakes. Most top players however tend to be quite aggressive, sacking majors or even colonels to expose the opponent’s top two pieces, while at the same time having their counter attacks ready. Typically there are 3 simultaneous battles for each of the 3 alleys. But, yeah, as in chess, there can be bloodless draws or fortress positions where neither wants or can make headway.
hirundo 4y ago
When I was a kid I "won" a Stratego game with a non-move that my friend claimed was against the rules. So he claimed the win. Could I get an umpire's call here? The issue is that when considering my next move, I picked up the bomb piece, thought for a few moments, put it back down, and moved another piece. My friend then, assuming that I had just given away that it was not a bomb, attempted to capture it, and lost the attacker. He claimed that it was illegal to pick up that piece and put it down again, although he had no objection until he learned that I'd tricked him. We had never previously announced or enforced a touch-it-move-it rule. So did I win that game or did he? That's not a question machine learning could answer.
- Swenrekcah 4y ago
  You won. Deception is obviously a critical part of all warfare.
  - yborg 4y ago
    By that argument, the opponent rightfully won, because negotiation is also a critical part of warfare. He got his opponent to give away a tactical battlefield victory on the basis of mutually agreed ground rules. Of course, dissatisfaction with such outcomes has often resulted in further wars.
- boringg 4y ago
  Hmm that you picked up the piece might have been an infraction. I constantly touch the bomb pieces but I don't lift them off the ground which implies that they can move. Tough call - glad that you are still carrying this from your childhood though. I would wager that you won but through borderline cheating. Still not sure TBH
- milesskorpen 4y ago
  If you're playing seriously, I think if you touch a piece you need to move it.
- HWR_14 4y ago
  You won because "He claimed that it was illegal to pick up that piece and put it down again, although he had no objection until he learned that I'd tricked him." I think "touch-move" is perfectly valid to enforce, but you waive your right to do so once you move after that. If someone touches a piece in chess, then moves another piece, you don't get to go all the way until you're mated and then say there was an error you should have won on. And if you touch an illegal to move piece, I would say there the penalty would probably be revealing the bomb (or that it is immobile), not forfeiture of the game.
voidfunc 4y ago
I haven't played Stratego since I lost my board when I was in third grade and brought it to play during recess... Is there a good online version these days?
evouga 4y ago
I mean. Stratego is a great game; I had a lot of fun playing it at summer camps when I was a young boy. It's cool there's a good AI for it. But this result feels a bit anticlimactic in a world where AIs can already beat expert humans at go, six-player poker, Starcraft, ...
- kzrdude 4y ago
  How far did they get with Starcraft? Stratego should be a stepping stone to get there - it introduces imperfect information.
  - spywaregorilla 4y ago
    It's very difficult to say. There are many cookie cutter strategies for RTS games and it's difficult to handicap the ai to note use its machine precision and quickness of thinking to just win everything on a tactical level. actions per minute handicaps are not nearly nuanced enough to capture this. Generally it seems that the absolute top humans are better than bots strategically but the execution to do so is really, really tough. And then of course there are dumb exploits because you find some dumb weakpoint than any sane human would quickly adjust their behavior for.
  - confuseshrink 4y ago
    Starcraft in the form of Alphastar worked in the sense that it could beat humans, at least in the short term. The problem with the whole technique is that they had to tether it to the human examples they had gathered in the form of a divergence loss. I haven't checked out the linked paper yet but if they managed to do something from first principles that would still be an interesting development.
  - anonymoushn 4y ago
    spywaregorilla left a good reply about Starcraft. In the games I watched, despite the AI being handicapped to use human-like levels of APM and human-like viewport management, it primarily fought using *clearly superhuman* blink stalker micromanagement. Stalkers with barely any health would typically survive engagements and get to re-engage when their shields were fully recovered. On the other hand, a human player managed to confuse the bot by repeatedly airdropping units in its base, picking them up, and dropping them elsewhere. The bot uselessly moved its mass of stalkers back and forth while losing many probes and buildings. Edit: After looking at some games again, the AI also benefits from precise target selection for the phoenix's graviton beam. A human player might take 3 phoenixes and a bunch of stalkers into a fight against an army containing 3 immortals, some sentries, some stalkers, and some zealots, and use graviton beam to pick up some mix of units including units other than immortals. The bot can pick up only the immortals.
miiiiiike 4y ago
Got a copy of Stratego (one of the old-style ones with descending rank, as pleases the gods) so I could show my board game loving girlfriend one of my favorite games from when I was a kid. She hated it.
- jrussino 4y ago
  Did you still enjoy it? I loved playing this game with my Dad when I was a kid and I'm wondering if it still holds up.
  - TedDoesntTalk 4y ago
    Played it recently with a 12 year old boy. He loves it.
  - jasone 4y ago
    It held up for me. I played a lot of Stratego with family and friends as a kid, but there was one friend in particular who routinely wiped the battlefield with my pieces. I couldn't understand how he so consistently beat me, and as an adult I was able to 1) reason more deeply about the game, and 2) quickly learn deeper strategy from the Internet. As a result, the game is even richer now to me than it was in the 1980s.
  - miiiiiike 4y ago
    Loved it. I still think it’s one of the best games out there. The best games tho: Neuroshima Hex! And 51st State from Portal games.
- LionTamer 4y ago
  Seeing the paper title gave me so much nostalgia for playing Stratego as a kid, that was always my favorite Board game. Glad to see I’m not the only one who used to love that game, few of my friends growing up played it.
- kibwen 4y ago
  Stratego was probably my favorite board game as a kid, but, to be fair, when people these days say that they love board games what they probably mean is that they love Eurogames, which Stratego decidedly is not.
hervature 4y ago
I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD. The core contribution here is the Nash equilibrium component to imperfect information games using only self-play. Note, there is no MCTS being done in this paper. This differs from counter factual regret methods (like the most famous Poker AIs) because it does not need to compute for all possible "information sets" which makes it intractable for even sufficiently complicated poker variants. It should also be noted (as they do in the paper) that this is more incremental than methodologically innovative as AlphaGo. This is the AlphaZero step increment to NeuRD. As is my general critique with their previous papers, they generally omit many engineering details that prove to be very important. Here, they admit that fine-tuning is vitally important (one of the 3 core steps) but details are relegated to the supplementary materials. It also opens up the question of if this new "fine-tuned" policy still guarantees the Nash equilibrium which it obviously does not as some mixed strategies are going to have sufficiently small probability. I wish researchers would be more honest with "this is a hack to get things to work on a computer because neural networks have floating point inaccuracies". It doesn't ruin any of the theory and no one is going to hold it against you. But it causes all sorts of confusion when trying to reimplement.
- algo_trader 4y ago
  > I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD What is the SOTA on solving non-adversarial (single player?) POMDPs? Are those considered to be much simpler problems?
  - hervature 4y ago
    POMDPs is exactly how one formalizes imperfect information games. This is where the concept of information sets comes from. To answer your question, any two player algorithm is going to apply to single player games as it is trivial to transform. For games like 2048, the "adversary" is simply the opposite of your outcome. For games where you are trying to maximize your score, this is the standard RL setting and any of the Atari algorithms (including MuZero) can be used. In case you are wondering about cooperative multi-agent games, I would check this group's publications: https://www.cs.ox.ac.uk/people/publications/date/Shimon.Whiteson.html https://www.cs.ox.ac.uk/people/publications/date/Shimon.Whit...
mensetmanusman 4y ago
Would it be interesting if the posted the approximate kWhr energy required to train?
Someone 4y ago
My gut feeling is that optimum play in Stratego is not to play. It feels better to let your opponent try and take your piece because, if they take it, you can make sure there will be at least one neighboring piece that can strike back. If so, every game should end in a draw because of inactivity of both players. My limited experience confirms that. Playing defensively, only offering my scouts to get intel tends to win games for me. But then, I’ve never found any strategy guides, and wouldn’t know how good players play.
- thomasahle 4y ago
  I you read the article you will see a lot of discussion on different strategies the bot has (re)discovered. You can also try playing against others on the internet and see how well your method works.
bezoz 4y ago
So we have gone from DQN to Alpha Go to Alpha Zero to Mu Zero to Deep Nash? Every time I thought I have figured out their naming scheme, they come out with something even more unpredictable.
thomasahle 4y ago
I really like the section on initial piece deployment: > The Flag is almost always put on the back row, and often protected by Bombs. Occasionally, however, DeepNash will not surround the Flag with Bombs. Experts (e.g. Vincent de Boer, 3-fold World Champion) believe that it is indeed good to occasionally not protect the Flag because this unpredictability makes it harder for the opponent in the end-game. Another pattern observed is that the highest pieces, the 10 and 9, are often deployed on different sides of the board. Additionally, the Spy is quite often located not too far away from the 9 (or 8), which protects it against the opponent’s 10. DeepNash does not often deploy Bombs on the front row, which complies with the behavior seen from strong human players. The 3’s (Miner), which can defuse Bombs, are often placed on the back row, which makes sense because their importance typically increases throughout a game as more opponent Bombs and potential Flag positions get revealed. The eight 2’s (Scout) are typically deployed both in the front and more in the back, allowing to scout opponent pieces initially but also in later phases of the game.

131 points by aklein 4y ago

I haven't played Stratego in decades! Loved it as a kid, though

Stratego is an odd choice I feel. Evaluating it must be really hard. A significant chunk of the game is just trying to remember which unit is which of the things you've seen so far. Which humans generally can't do very well but machines can do easily. Beating hand crafted bots is good. Can expert humans beat the hand crafted bots? I'm guessing no. Also, what's stratego like without the hidden units? Is that... hard?

Buttons840 4y ago
I think the best human players can beat the best computer players in Stratego. Thus, Stratego is an excellent choice.
janosett 4y ago
You might consider reading the linked abstract: “… Stratego has been a grand challenge for the field of AI for decades, and existing AI methods barely reach an amateur level of play.”
- spywaregorilla 4y ago
  Sounds like bullshit to me. I'm not convinced. Here's a paper from 2021 that suggests as much. It's hard, sure, but it's also not really seriously explored. > Compared to other games like Chess and Go, not much work has been done on creating an AI agent for Stratego. As such, the available literature is far and few between, and mostly consists of bachelor’s and master’s theses. In fact, most agents created for Stratego are largely undocumented or closed-source, making it difficult to effectively ascertain exactly which particular methods and techniques have been applied and how effective they were. edit: the claim about bots not beating humans appears to hold, but I'm not convinced its just shoddy bot quality.
  - JoshCole 4y ago
    Just to give a sense of hardness, Stratego's game tree is infinitely larger than Go's game tree, because in imperfect information you select a continuous strategy vector over action space whereas in Go you select a discrete action. Meanwhile Stratego is also infinitely more complex than Go because in Go there are less moves with every move, but in Stratego moves don't monotonically decrease the remaining game length. Beyond those two infinities of greater complexity, Stratego is imperfect information, so it is played relative to the infostate, not the state. In Stratego there are thirty three pieces with unknown information on the first move. We can definitely get a lower upper bound by applying abstraction via domain knowledge, but just so I don't have to deal with the complexity I'll state that there are at most 8683317618811886495518194401280000000 different states associated with the infostate of your first move. Meanwhile, on your first move in Go, you are in at most 1 state. In practice though the average length of a game of Go is ~200ish, the average length of Stratego ~400ish. Much like chess, I would expect optionality to be an important strategic consideration in Stratego. So branching factors are likely selected for such that they get higher by good agents. In contrast to something like Go, the branching factor would tend to diminish over time. Mostly sharing this because I think most people are bad at reasoning about complexity - our mind is really good at making complex things seem simple and simple things seem complex because we can actually deal with the complexity of simple things in their full complexity but dealing with the full complexity of the complicated is intractable. I imagine a lot of people's mind latch onto the things like "we get information so playing well means memorization" and don't pay as much focus to the dizzying complexity; but playing well isn't memorizing. Playing well is playing perfectly according to your uncertainty and it just so happens that as part of doing that you sometimes reduce your uncertainty by scouting.
    - spywaregorilla 4y ago
      This is all technically true, but it's also misleading I feel. Chess and Go have a lot of states, and you need all of them. The entropy of the games are enormous. Move that bishop and the significance of every piece on the board could change. Stratego has verrrryy low entropy. You can only move one piece one space at a time aside from scouts. You can also enter scenarios where the game just simplifies on some dimensions immensely to which some fairly dumb algorithms can win the game. If the enemy loses their top dude and their spy, your top guy is invincible against anything that has ever moved, which isn't victory assured but its probably relatively easy to write an ai to win from that point on. Maybe this is just me but when I thought about stratego I'm pretty sure I only thought about a few units at a time. Moving all of them is a bad idea because of bombs anyway. Your mental model of the game does not consider the state of units in the back row of either side. It probably doesn't even consider all of the units in the front. I also suspect a lot of optimal play is just doing dumb shit back and forth to force your opponent into making the more aggressive move in a lot of cases without technically forfeiting which most humans likely wouldn't do but ai would like to do if not constrained otherwise. But I agree a simple tree search on possible moves is unlikely to work very well until the end game.
dr_orpheus 4y ago
> A significant chunk of the game is just trying to remember which unit is which of the things you've seen so far While this does get hard the further you go in the game, a think a more significant portion of the strategy is trying to predict newly moving units based on what is happening in the game. i.e. I just took a 7 unit with my 8. And now my opponent is coming straight towards me with a unit from elsewhere. Is it a 9 or 10, is it a bluff to drive me off, to drive me in to a spot where the actual 9 or 10 is waiting?
- aidenn0 4y ago
  Did they renumber the pieces? In the set I played as a kid a scout was 9 and a Marshall was 1...
  - wakamoleguy 4y ago
    Yes, around 2000 they swapped the numbers. Most recent versions treat the Spy as 1 and Marshal as 10. Classic versions ranked the Marshal as 1 and Scouts as 9, with the Spy designated as S.
    - andruby 4y ago
      I bought a set to play with my kids and felt like something was off but couldn’t really recall. Thanks!
- spywaregorilla 4y ago
  Computers are better at such problems.
Imnimo 4y ago
From the paper: > Successes in the game have been limited, with artificial agents only able to play at a level comparable to a human amateur, see e.g. (14–20).
- riku_iki 4y ago
  It could be because no one seriously tried to build competitive AI player.
  - thomasahle 4y ago
    Computer Stratego World Championship has been held since at least 2007.
    - riku_iki 4y ago
      This doesn't bring much information. It could be some students competition. Also, per my brief google search they stopped doing it after 3 competitions in 2009.
boringg 4y ago
I don't think you are that familiar with how good Stratego is played. It isn't strictly a memorize where your opponents units are. There's a significant degree of bluffing and posturing.
- spywaregorilla 4y ago
  It isn't strictly about memorizing where your opponents are, but having a perfect memory would be an enormous advantage, the point of being an entirely different game imo.
  - ghaff 4y ago
    Yes, playing it as a kid I remember one pretty common thing to do was to make movements that made it easy for your opponent to get confused about whether a piece was that known piece or something else. Not the whole strategy but take that piece out and you definitely change the game I would think relative to typical human play. Especially in the context of it normally being more of a kids game.
  - treis 4y ago
    Seems like it would be easy to test. See how the AI does when revealed pieces stay revealed compared to a standard game. Also, given this is online competitive play likely that a significant portion of top human players are cheating and have aides to keep track of pieces.
    - spywaregorilla 4y ago
      > Seems like it would be easy to test. See how the AI does when revealed pieces stay revealed compared to a standard game. It would effectively need to be a different AI to use that information. And what does it play? Humans? Other AI? > Also, given this is online competitive play likely that a significant portion of top human players are cheating and have aides to keep track of pieces. That's a great point. It may even be condoned in some circles.
    - TemplateRex 4y ago
TemplateRex 4y ago
The best available bot that is also mentioned in the paper, is Probe. Expert humans will score the same as DeepNash against Probe. The best humans have no trouble recalling every piece that moved, and the square it originated from. Top-level play usually has very few moved pieces (since they are vulnerable to your opponent's general once your own marshal gets revealed), so memory is important but typically not the main bottleneck.
- spywaregorilla 4y ago
  > Top-level play usually has very few moved pieces (since they are vulnerable to your opponent's general once your own marshal gets revealed), so memory is important but typically not the main bottleneck. Interesting. Is top level play... boring? Stratego doesn't have a lot of nuance to positional advantaging aside from moving forward or back, and while I'd imagine there's stalemate rules, there's probably a lot of nothing moves to dance around getting super minor and uninteresting advantages. Is that a correct statement?
  - TemplateRex 4y ago
    It depends on player attitudes. The maneuvering is simpler than in chess or even checkers, although you can have very intricate multi-piece pincers around the lakes. Most top players however tend to be quite aggressive, sacking majors or even colonels to expose the opponent’s top two pieces, while at the same time having their counter attacks ready. Typically there are 3 simultaneous battles for each of the 3 alleys. But, yeah, as in chess, there can be bloodless draws or fortress positions where neither wants or can make headway.

hirundo 4y ago

When I was a kid I "won" a Stratego game with a non-move that my friend claimed was against the rules. So he claimed the win. Could I get an umpire's call here? The issue is that when considering my next move, I picked up the bomb piece, thought for a few moments, put it back down, and moved another piece. My friend then, assuming that I had just given away that it was not a bomb, attempted to capture it, and lost the attacker. He claimed that it was illegal to pick up that piece and put it down again, although he had no objection until he learned that I'd tricked him. We had never previously announced or enforced a touch-it-move-it rule. So did I win that game or did he? That's not a question machine learning could answer.

Swenrekcah 4y ago
You won. Deception is obviously a critical part of all warfare.
- yborg 4y ago
  By that argument, the opponent rightfully won, because negotiation is also a critical part of warfare. He got his opponent to give away a tactical battlefield victory on the basis of mutually agreed ground rules. Of course, dissatisfaction with such outcomes has often resulted in further wars.
boringg 4y ago
Hmm that you picked up the piece might have been an infraction. I constantly touch the bomb pieces but I don't lift them off the ground which implies that they can move. Tough call - glad that you are still carrying this from your childhood though. I would wager that you won but through borderline cheating. Still not sure TBH
milesskorpen 4y ago
If you're playing seriously, I think if you touch a piece you need to move it.
HWR_14 4y ago
You won because "He claimed that it was illegal to pick up that piece and put it down again, although he had no objection until he learned that I'd tricked him." I think "touch-move" is perfectly valid to enforce, but you waive your right to do so once you move after that. If someone touches a piece in chess, then moves another piece, you don't get to go all the way until you're mated and then say there was an error you should have won on. And if you touch an illegal to move piece, I would say there the penalty would probably be revealing the bomb (or that it is immobile), not forfeiture of the game.

voidfunc 4y ago

I haven't played Stratego since I lost my board when I was in third grade and brought it to play during recess... Is there a good online version these days?

evouga 4y ago

I mean. Stratego is a great game; I had a lot of fun playing it at summer camps when I was a young boy. It's cool there's a good AI for it. But this result feels a bit anticlimactic in a world where AIs can already beat expert humans at go, six-player poker, Starcraft, ...

kzrdude 4y ago
How far did they get with Starcraft? Stratego should be a stepping stone to get there - it introduces imperfect information.
- spywaregorilla 4y ago
  It's very difficult to say. There are many cookie cutter strategies for RTS games and it's difficult to handicap the ai to note use its machine precision and quickness of thinking to just win everything on a tactical level. actions per minute handicaps are not nearly nuanced enough to capture this. Generally it seems that the absolute top humans are better than bots strategically but the execution to do so is really, really tough. And then of course there are dumb exploits because you find some dumb weakpoint than any sane human would quickly adjust their behavior for.
- confuseshrink 4y ago
  Starcraft in the form of Alphastar worked in the sense that it could beat humans, at least in the short term. The problem with the whole technique is that they had to tether it to the human examples they had gathered in the form of a divergence loss. I haven't checked out the linked paper yet but if they managed to do something from first principles that would still be an interesting development.
- anonymoushn 4y ago
  spywaregorilla left a good reply about Starcraft. In the games I watched, despite the AI being handicapped to use human-like levels of APM and human-like viewport management, it primarily fought using *clearly superhuman* blink stalker micromanagement. Stalkers with barely any health would typically survive engagements and get to re-engage when their shields were fully recovered. On the other hand, a human player managed to confuse the bot by repeatedly airdropping units in its base, picking them up, and dropping them elsewhere. The bot uselessly moved its mass of stalkers back and forth while losing many probes and buildings. Edit: After looking at some games again, the AI also benefits from precise target selection for the phoenix's graviton beam. A human player might take 3 phoenixes and a bunch of stalkers into a fight against an army containing 3 immortals, some sentries, some stalkers, and some zealots, and use graviton beam to pick up some mix of units including units other than immortals. The bot can pick up only the immortals.

miiiiiike 4y ago

Got a copy of Stratego (one of the old-style ones with descending rank, as pleases the gods) so I could show my board game loving girlfriend one of my favorite games from when I was a kid. She hated it.

jrussino 4y ago
Did you still enjoy it? I loved playing this game with my Dad when I was a kid and I'm wondering if it still holds up.
- TedDoesntTalk 4y ago
  Played it recently with a 12 year old boy. He loves it.
- jasone 4y ago
  It held up for me. I played a lot of Stratego with family and friends as a kid, but there was one friend in particular who routinely wiped the battlefield with my pieces. I couldn't understand how he so consistently beat me, and as an adult I was able to 1) reason more deeply about the game, and 2) quickly learn deeper strategy from the Internet. As a result, the game is even richer now to me than it was in the 1980s.
- miiiiiike 4y ago
  Loved it. I still think it’s one of the best games out there. The best games tho: Neuroshima Hex! And 51st State from Portal games.
LionTamer 4y ago
Seeing the paper title gave me so much nostalgia for playing Stratego as a kid, that was always my favorite Board game. Glad to see I’m not the only one who used to love that game, few of my friends growing up played it.
kibwen 4y ago
Stratego was probably my favorite board game as a kid, but, to be fair, when people these days say that they love board games what they probably mean is that they love Eurogames, which Stratego decidedly is not.

hervature 4y ago

I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD. The core contribution here is the Nash equilibrium component to imperfect information games using only self-play. Note, there is no MCTS being done in this paper. This differs from counter factual regret methods (like the most famous Poker AIs) because it does not need to compute for all possible "information sets" which makes it intractable for even sufficiently complicated poker variants. It should also be noted (as they do in the paper) that this is more incremental than methodologically innovative as AlphaGo. This is the AlphaZero step increment to NeuRD. As is my general critique with their previous papers, they generally omit many engineering details that prove to be very important. Here, they admit that fine-tuning is vitally important (one of the 3 core steps) but details are relegated to the supplementary materials. It also opens up the question of if this new "fine-tuned" policy still guarantees the Nash equilibrium which it obviously does not as some mixed strategies are going to have sufficiently small probability. I wish researchers would be more honest with "this is a hack to get things to work on a computer because neural networks have floating point inaccuracies". It doesn't ruin any of the theory and no one is going to hold it against you. But it causes all sorts of confusion when trying to reimplement.

algo_trader 4y ago
> I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD What is the SOTA on solving non-adversarial (single player?) POMDPs? Are those considered to be much simpler problems?
- hervature 4y ago
  POMDPs is exactly how one formalizes imperfect information games. This is where the concept of information sets comes from. To answer your question, any two player algorithm is going to apply to single player games as it is trivial to transform. For games like 2048, the "adversary" is simply the opposite of your outcome. For games where you are trying to maximize your score, this is the standard RL setting and any of the Atari algorithms (including MuZero) can be used. In case you are wondering about cooperative multi-agent games, I would check this group's publications: https://www.cs.ox.ac.uk/people/publications/date/Shimon.Whiteson.html https://www.cs.ox.ac.uk/people/publications/date/Shimon.Whit...

mensetmanusman 4y ago

Would it be interesting if the posted the approximate kWhr energy required to train?

Someone 4y ago

My gut feeling is that optimum play in Stratego is not to play. It feels better to let your opponent try and take your piece because, if they take it, you can make sure there will be at least one neighboring piece that can strike back. If so, every game should end in a draw because of inactivity of both players. My limited experience confirms that. Playing defensively, only offering my scouts to get intel tends to win games for me. But then, I’ve never found any strategy guides, and wouldn’t know how good players play.

thomasahle 4y ago
I you read the article you will see a lot of discussion on different strategies the bot has (re)discovered. You can also try playing against others on the internet and see how well your method works.

bezoz 4y ago

So we have gone from DQN to Alpha Go to Alpha Zero to Mu Zero to Deep Nash? Every time I thought I have figured out their naming scheme, they come out with something even more unpredictable.

thomasahle 4y ago

I really like the section on initial piece deployment: > The Flag is almost always put on the back row, and often protected by Bombs. Occasionally, however, DeepNash will not surround the Flag with Bombs. Experts (e.g. Vincent de Boer, 3-fold World Champion) believe that it is indeed good to occasionally not protect the Flag because this unpredictability makes it harder for the opponent in the end-game. Another pattern observed is that the highest pieces, the 10 and 9, are often deployed on different sides of the board. Additionally, the Spy is quite often located not too far away from the 9 (or 8), which protects it against the opponent’s 10. DeepNash does not often deploy Bombs on the front row, which complies with the behavior seen from strong human players. The 3’s (Miner), which can defuse Bombs, are often placed on the back row, which makes sense because their importance typically increases throughout a game as more opponent Bombs and potential Flag positions get revealed. The eight 2’s (Scout) are typically deployed both in the front and more in the back, allowing to scout opponent pieces initially but also in later phases of the game.