6 ms·

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 thing

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.
      - JoshCole 4y ago
        If I'm understanding you correctly, you're saying that the rules of Stratego let you apply an abstraction rule which drastically simplifies the game. I agree you can do this. I think this point is remarkably similar to the technique of blueprint abstraction. Of course, we ought to be focused on the situations which lead to these nice situations - which leads us back to the imperfect information situations which lead to those positions we can reason about. Interestingly, you can invert your point and get a similar rule more generally. The trick is to backward induction on the abstracted category transitions. So your point is actually so valid that is valid even in situations where your examples don't apply. I hope you can see I'm strong manning here. I agree with you that this should be done and is critical to making things tractable. There is an issue though, at least in the generalized case, which is that perfect information is much easier than imperfect information. See, in perfect information games when you do the backward induction step you actually just flat out solve the game. Meanwhile, in imperfect information games, this backward induction step merely makes solving the game more tractable. Chess endgames are the backward induction version of your forward induction from the rules abstraction, but the abstraction rule is so hard to determine we wouldn't usually think of it that way. Notice that chess is hard enough that we don't have endgame tables that go all the way back to the start of the game? Yet the average game length in Stratego is hundreds of moves longer and there are more then double the number of pieces. I still think your point is right and someone who pushes hard enough in this direction would manage to tackle the complexity. So I basically agree with you. But if you take standard approaches like counterfactual regret minimization and throw it at the game without adjusting them for the fact that the problem is "hard" then they just wont terminate.
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.

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.
    - JoshCole 4y ago
      If I'm understanding you correctly, you're saying that the rules of Stratego let you apply an abstraction rule which drastically simplifies the game. I agree you can do this. I think this point is remarkably similar to the technique of blueprint abstraction. Of course, we ought to be focused on the situations which lead to these nice situations - which leads us back to the imperfect information situations which lead to those positions we can reason about. Interestingly, you can invert your point and get a similar rule more generally. The trick is to backward induction on the abstracted category transitions. So your point is actually so valid that is valid even in situations where your examples don't apply. I hope you can see I'm strong manning here. I agree with you that this should be done and is critical to making things tractable. There is an issue though, at least in the generalized case, which is that perfect information is much easier than imperfect information. See, in perfect information games when you do the backward induction step you actually just flat out solve the game. Meanwhile, in imperfect information games, this backward induction step merely makes solving the game more tractable. Chess endgames are the backward induction version of your forward induction from the rules abstraction, but the abstraction rule is so hard to determine we wouldn't usually think of it that way. Notice that chess is hard enough that we don't have endgame tables that go all the way back to the start of the game? Yet the average game length in Stratego is hundreds of moves longer and there are more then double the number of pieces. I still think your point is right and someone who pushes hard enough in this direction would manage to tackle the complexity. So I basically agree with you. But if you take standard approaches like counterfactual regret minimization and throw it at the game without adjusting them for the fact that the problem is "hard" then they just wont terminate.

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.