11 ms·

Mastering Stratego

290 points by beefman 4y ago

jstummbillig 4y ago
Can anyone shed light on in what way this is more challenging than the starcraft or dota agents, which also had to work with imperfect information?
- machina_ex_deus 4y ago
  Dota is a pretty local game. 70% tactics, 20% strategy. Maybe 10% information. Yes you have warding game but for an AI with no cost of looking at heroes inventories (humans need to waste attention and move their map) AI already has huge advantage over humans in the imperfect information part. Usually fighting into the imperfect information is the bad choice. Stratego is 40% information, 40% strategy, maybe 10% tactics. If you know where is the flag it's trivial to win in almost all situations. Fighting into imperfect information is literally all the game.
  - ghostbrainalpha 4y ago
    Is Tactics the same thing as execution? Like is it just the speed of your clicking? Or is it more than that, like the most basic kinds of strategic decisons?
    - keithnz 4y ago
      in dota the tactics is to do with the execution of abilities, often times in coordination with other agents in execution of their abilities to get combo effects while adapting to the situation as it unravels.
      - dtdynasty 4y ago
        As an avid dota player I wouldn't agree with your characterization that 70% of dota 2 is your definition of tactics. What I've noticed differentiates player MMR the most is the strategy applied to each context. It's rarely the execution that's the problem as you can gain such overwhelming advantages through strategy.
        machina_ex_deus 4y ago
        There's barely any long term strategy in Dota, only meaningful strategic decisions are items and heroes. Even ultimate usage has like 2 minute window of importance. Wards too. And maybe the decision to push high ground because of how many times games are lost because of it, but it's the tactical errors usually making most of the difference there. What's your MMR, out of curiosity?
        nlsvb 4y ago
        I'm immortal (6k MMR) and agree with the parent. I used to think similarly as you, because my mechanics were very good, but as I started to play with friends who are much lower ranked, I noticed that they can often execute things (e.g. ability usage) pretty well, but their overall play and strategy is desperately lacking. Things like playing the wrong areas of the map, spending their time inefficiently, never capitalizing on their strategic opportunities (e.g. not playing where they have vision, not playing in areas of the map that are near their objectives, not taking calculated risks based on available information). I do think OpenAI five derived some of their advantage from seamless ability usage, and inhuman coordination in lane, but it also did some novel things strategically, that challenged some of the established tenets of high level play (e.g. they had a lot of mobility on the map, back when that was considered very inefficient).
        dtdynasty 4y ago
        The highest I've been relative to the top was probably 4.8k in 2013. Nowadays I'm a party queue casual that's still around the same MMR haha.
    - machina_ex_deus 4y ago
      It's from things like properly last hitting creeps, good reaction timing, good reaction decisions, coordinating real time actions with teammates in milliseconds resolution. It's obviously not about clicking fast, but it is about timing, sometimes 100 milliseconds reaction time make huge difference in outcome. It is usually making decisions on very small time scales. Do you retreat or continue? Use ability or hold it? Can you overextend? The only meaningful strategic decisions in dota (which you have long time frame of deciding and effect the game for a long duration) are draft (which AI doesn't really master, they reduced the heroes pool to simplify) and item purchases, and there are only a handful of them (~6) in an entire game. Other decisions don't really have a long "memory" time, a minute or two at the most. After two minutes every other decision is just reduced to the relative advantage between the teams. There used to be one hero in Dota which made it a strategy game instead (techies). But it was like playing a different game and everyone hated it and it was effectively removed. Techies was like playing stratego against chess players, they obviously get pissed off by not playing what they wanted.
      - dtdynasty 4y ago
        There are larger strategic decisions that are significant in dota. Which area of the map to play, which objectives are important and when, what type of fights will we win (fast and bursty) and when will we take them. Often times these are thought of at the beginning of the game and effect gameplay throughout.
        machina_ex_deus 4y ago
        That's pretty tactical decisions, usually made in a time window of like 20-30 seconds top. Takes like 40 second to reach more than half the map from the base. Fighting decisions usually also get tactical. I would say that 90% of the game deciding decisions have a time window of less than 30 seconds to make. 70% are in a time window of seconds. You don't make a strategic decision to fight ever, you make tactical decision when the map looks fitting. If you take strategic fights because of long term strategy (instead of deciding tactically) in Dota you will lose.
  - rosmax_1337 4y ago
    Dota at the mid-casual and high-casual brackets (which is where you find most players) is also a social game. Establishing efficient leadership, communication and cooperation in a game gives you a huge advantage. And the low-casual and the pro levels you find it becomes more a game of skill and strategy funnily enough. (The old joke is that Dota is a 1 v 9 game, not a 5 v 5)
    - mst 4y ago
      I periodically still drop in to Subspace/Continuum Trench Wars and in a multi hour play session will generally spend the first hour dogfighting and then get annoyed with the performance of my assigned team and switch to a command ship and spend a lot more time typing encouraging other pilots to do the sensible thing than I do actually fighting. Both modes of play are fun, mind, but the parallels struck me as worth noting.
- Tenoke 4y ago
  Starcraft and Dota benefit a lot from having good micro. Stratego seems to be only macro. Micro is easyish for AI and requires less long-term thinking to get benefits from.
  - adgjlsfhk1 4y ago
    Starcraft especially only resembles a strategy game in GM (and maybe high masters). Below that, the strategy is mostly macro better so you have more units.
- fnbr 4y ago
  I don’t think it is more challenging than StarCraft or Dota. Does the blog post claim that anywhere? Stratego is way more challenging than Poker, though. StarCraft/Dota/Stratego have the property that you can’t represent their imperfect information as a vector in memory, whereas you can easily do that in Texas hold’em poker (there’s only 52C2 = 1024 possible hands). So for those games, you have to use an approximate distribution rather than the exact one. I’m an author on this paper (although my contributions were relatively minimal) and on the Player of Games paper (which did Poker, Chess, and Go).
  - jstummbillig 4y ago
    > I don’t think it is more challenging than StarCraft or Dota. Does the blog post claim that anywhere? My very naive question question being: Why tackle this after SC and Dota have already been done? What is the scientific interest? Stratego seems strictly simpler than both of these games. In what way is this an advancement over how SC/Dota AI were solved?
- michalsustr 4y ago
  Great question! I would say the main reason why this work is significant is that StarCraft agent was bootstrapped from human replays, and Dota agent did not have game-theoretic guarantees on minimizing exploitability (i.e. how far the strategy is from Nash equilibrium). The R-NaD algorithm with neural nets (behind Stratego) starts from scratch, and has game-theoretic guarantees. In principle, the AlphaStar's league approach (from StarCraft) could be done also in Stratego, and it would be very interesting to compare the two approaches. Note that AlphaStar is more expensive: it required to train N competing agents with pair-wise evaluation costing N^2, while Stratego's NeuRD trains a single agent.
deleted 4y ago
[deleted]
waprin 4y ago
Great article. I played Stratego a lot as a kid and it always felt simpler than chess, go , or poker so it’s surprising it’s a much bigger game tree unless you stop and think. I’m curious about the comparisons to poker. I know the hot algorithm in poker solvers is counter factual regret minimization. The article indicates that the feedback cycle is too long for those algorithms to work but I’d be curious to learn more about the relationship from CFR to what’s tried here, if any.
- _HMCB_ 4y ago
  I played it too. My goodness what a blast from the past. To be honest, none of my friends liked to play. I mostly played by myself it seems. LOL.
  - TecoAndJix 4y ago
    I had star wars stratego that i played where they reversed the number values. It was characters from the OG trilogy and episode 1. takes me back! $80 on amazon for that version :(
- gcanyon 4y ago
  The "complexity" of a game is not very well measured by game-tree size alone. Wikipedia lists multiple factors on the game complexity page: https://en.wikipedia.org/wiki/Game_complexity#Measures_of_game_complexity https://en.wikipedia.org/wiki/Game_complexity#Measures_of_ga...
- fnbr 4y ago
  It’s very hard to use CFR in Stratego because you can’t represent the hidden information in memory. In poker, the hidden information is a 52C2 vector, so you can easily pass it around. Not so in Stratego, so you have to do something else. RNAD has similar theoretical foundations though.
beefman 4y ago
There's an extra space in the link to their code (at the end of the article). The correct URL is: https://github.com/deepmind/open_spiel/tree/master/open_spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_spie...
- ArtWomb 4y ago
  Wow! Thanks to DeepMind for OpenSpiel! Am looking forward to ai experimenting with Stratego, Battleships & Hanabi ;)
beefman 4y ago
The paper is sadly paywalled. I believe this is the preprint: https://arxiv.org/abs/2206.15378 https://arxiv.org/abs/2206.15378
clolege 4y ago
It's interesting to watch the videos they link of deepmind playing against the top-level Stratego masters [0]. I usually find Stratego to be a bit of a dull game (less elegant and more drawn out than Go and chess), but I'm a sucker for watching top-level AIs play. Its skills for bluffing are both fascinating and a bit scary. [0] https://www.youtube.com/watch?v=HaUdWoSMjSY https://www.youtube.com/watch?v=HaUdWoSMjSY https://www.youtube.com/watch?v=L-9ZXmyNKgs https://www.youtube.com/watch?v=L-9ZXmyNKgs https://www.youtube.com/watch?v=EOalLpAfDSs https://www.youtube.com/watch?v=EOalLpAfDSs https://www.youtube.com/watch?v=MhNoYl_g8mo https://www.youtube.com/watch?v=MhNoYl_g8mo
- ep103 4y ago
  Are these games against stratego masters? I'm watching the first one, but it doesn't say who they're playing against
  - clolege 4y ago
    yep, top anonymized players
  - sdwr 4y ago
    Dont think the player pool is very deep, doubt there are many masters around..
    - topaz0 4y ago
      What makes you think that? The article says that one of the coauthors used to be a world champion, which suggests to me that there is some kind of competitive organized league.
      - hgsgm 4y ago
        How many people study Stratego as much as an International Master studies chess?
        4y ago
sdwr 4y ago
I remember seeing a version of the paper earlier in the year (it talked a lot about getting the bot to be aggressive to avoid stalemates). Feels like the secret sauce has to be probability distributions guessing what all the pieces are. Bluffing in stratego seems like it requires long-term planning (if you move a 2 like a 10, you have to keep treating it like that for the bluff to work).
dr_faustus 4y ago
Call me a cynic but the fact that after almost 10 years of AI hype we are still working our way down the list of popular board games is a bit of a downer for me. I mean, having AIs to play Stratego, Risk, Go, Diplomacy and what have you against sure is nice. But there are literally billions of dollars spent on these projects and I really come to the point where I just don't believe anymore that the current AI approaches will ever generalize to the real world, even in relatively limited scopes, without the need for significant human intervention and/or monitoring. What am I missing?
- rg111 4y ago
  > after almost 10 years of AI hype we are still working our way down the list of popular board games That's what one lab is doing. You cannot be blind to many many applications that are finding their ways to consumers and earning people money.
- VHRanger 4y ago
  AI remains better than humans at anything that has well defined rewards and small time gap between action and feedback mechanism (either naturally, like poker, or by value function engineering, like Go or Chess) The problem here is that it's missing the "glue" to more real world applications. This is where more humdrum software engineering comes in. Diplomacy in this is much more interesting than Stratego or beating the next video game - it mixes cooperative game theory with NLP and reinforcement learning.
  - dasil003 4y ago
    > The problem here is that it's missing the "glue" to more real world applications. This is where more humdrum software engineering comes in. This is a bold statement. The world does not function based on "well-defined rewards". The concept of "common sense", which some consider table stakes for a human operating competently in our world, is mostly made up of things which are neither well-defined, nor allow a tremendous amount of training data. Current ML approaches require both.
    - 4y ago
Waterluvian 4y ago
One of my favourite things about watching AIs learn and play games I’ve played is seeing if they come across the same weird strategies I did. I remember my brother and I as kids playing Stratego and discovering the “impenetrable bunker of bombs” to put your flag in. Which evolved to “put a scout in as a ruse” and later “don’t actually enclose it because now brother just assumes it’s enclosed.”
sodapopcan 4y ago
Did anyone else call the dude with the tall hat "Hat Guy" despite them all having hats?
- IggleSniggle 4y ago
  Of course, yes!
  - sodapopcan 4y ago
    Ha, amazing! I always thought it was a thing but then occurred to me that it was maybe just my friends and me who said this. I'm glad to know it's a thing. Thinking back it may have been the sergeant who was the primary Hat Guy as I remember there was "Hat Guy" and later "Other Hat Guy".
midoridensha 4y ago
I'd rather learn how to play Strategema.
turtledragonfly 4y ago
Tangentially taking this opportunity to mention the far-superior "Lying and Cheating" version of Stratego, that (as far as I know) my father invented. It makes the game so much more interesting, IMO. Played it a lot as a child. Here are the basic rules, when a piece is attacked: * The attacker says what their piece is, without showing it (they can lie) * The defender says whether they believe that * The defender says what their piece is, without showing it (they can lie) * The attacker says whether they believe that * ONLY IF someone calls a bluff is that piece revealed. Otherwise, it is treated as the piece it was claimed to be, and kept hidden. * If someone calls a bluff, and they were right, then the other player loses a piece (reach over and remove any piece you like) ** If you pick their flag, then you win — game over. * Likewise, if someone calls a bluff but is wrong, then *they* lose a piece. * After all of that is resolved, do combat as normal, with pieces having either their revealed or not-revealed claimed value, as appropriate. Once you resolve all this, there is no "memory" - you can claim it is a different piece in the future. Some minutiae: * You can move any piece as though it were a Scout (9), but when you do the move, the other player can call your bluff since you're essentially claiming it is a Scout at that moment. Resolve that bluff/call before completing the move. * You could even call a bluff on *any* move someone makes, if you believe that piece is a bomb or flag (and thus cannot move). * You can attack with a bomb! It's a two-step process: first you move (and they could call your bluff, if they know it is a bomb - see above). Then, when the attack happens, you say it *is* a bomb. Of course, your opponent may say their piece is a Miner, and if you haven't seen it, it's a dangerous proposition (since bombs are rare). ** You can also do a variant where bombs can't attack (by attacking, you are claiming it is *not* a bomb). I prefer the above version. Overall, I find this version of the game is a lot less boring. Since you'll probably get several pieces zapped over the course of the game, it affects your flag placement. Plus, you can move flags and bombs, making it more dynamic. Also, the "remember where things were" aspect is even more poignant, since once a piece has been revealed, it loses all the power of being whatever-is-needed-right-now (assuming the other player has a good memory). So, for instance, you can do something crazy like move your bomb as though it were a Scout, all the way across the board, onto an opponent's piece, but then claim it's a "5" instead for the attack. Then if it survives, just let it sit there, continuing to be a bomb in the future (causing havoc).
- 4y ago
waynecochran 4y ago
I 404'ed when I tried to access the source code? https://github.com/deepmind/open_spiel/tree/master/open_%20spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_%20s... Someone needs to create a web front end for this -- I would love to play it.
- gus_massa 4y ago
  As beefman noted in another comment, the problem is that the link has a space "%20". The correct link is https://github.com/deepmind/open_spiel/tree/master/open_spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_spie...
beebeepka 4y ago
What happened to mastering StarCraft? Why did these guys give up after a mid tier pro player defeated the bot handily on live stream? They were super enthusiastic up until that point.
- bni 4y ago
  Have a link to that? Very interesting question btw. I'm also interested in the StarCraft AI state of the art 2022. If it exists. Or was focused changed to some other game?
  - beebeepka 4y ago
    Just look for deepmind StarCraft in YouTube. It won the first event but people came on top during the second event which turned out to be the last one if memory serves
JimWestergren 4y ago
On a related note and surely interesting to the HN crowd I invented Clesto which is similar to Stratego but a bit more like chess, based on an old chinese game: https://clesto.com/ https://clesto.com/ - it is more quick to play and has open information.
7373737373 4y ago
I'd love to see them tackle Chess https://en.wikipedia.org/wiki/Proof_game https://en.wikipedia.org/wiki/Proof_game

290 points by beefman 4y ago

Can anyone shed light on in what way this is more challenging than the starcraft or dota agents, which also had to work with imperfect information?

machina_ex_deus 4y ago
Dota is a pretty local game. 70% tactics, 20% strategy. Maybe 10% information. Yes you have warding game but for an AI with no cost of looking at heroes inventories (humans need to waste attention and move their map) AI already has huge advantage over humans in the imperfect information part. Usually fighting into the imperfect information is the bad choice. Stratego is 40% information, 40% strategy, maybe 10% tactics. If you know where is the flag it's trivial to win in almost all situations. Fighting into imperfect information is literally all the game.
- ghostbrainalpha 4y ago
  Is Tactics the same thing as execution? Like is it just the speed of your clicking? Or is it more than that, like the most basic kinds of strategic decisons?
  - keithnz 4y ago
    in dota the tactics is to do with the execution of abilities, often times in coordination with other agents in execution of their abilities to get combo effects while adapting to the situation as it unravels.
    - dtdynasty 4y ago
      As an avid dota player I wouldn't agree with your characterization that 70% of dota 2 is your definition of tactics. What I've noticed differentiates player MMR the most is the strategy applied to each context. It's rarely the execution that's the problem as you can gain such overwhelming advantages through strategy.
      - machina_ex_deus 4y ago
        There's barely any long term strategy in Dota, only meaningful strategic decisions are items and heroes. Even ultimate usage has like 2 minute window of importance. Wards too. And maybe the decision to push high ground because of how many times games are lost because of it, but it's the tactical errors usually making most of the difference there. What's your MMR, out of curiosity?
        nlsvb 4y ago
        I'm immortal (6k MMR) and agree with the parent. I used to think similarly as you, because my mechanics were very good, but as I started to play with friends who are much lower ranked, I noticed that they can often execute things (e.g. ability usage) pretty well, but their overall play and strategy is desperately lacking. Things like playing the wrong areas of the map, spending their time inefficiently, never capitalizing on their strategic opportunities (e.g. not playing where they have vision, not playing in areas of the map that are near their objectives, not taking calculated risks based on available information). I do think OpenAI five derived some of their advantage from seamless ability usage, and inhuman coordination in lane, but it also did some novel things strategically, that challenged some of the established tenets of high level play (e.g. they had a lot of mobility on the map, back when that was considered very inefficient).
        dtdynasty 4y ago
        The highest I've been relative to the top was probably 4.8k in 2013. Nowadays I'm a party queue casual that's still around the same MMR haha.
  - machina_ex_deus 4y ago
    It's from things like properly last hitting creeps, good reaction timing, good reaction decisions, coordinating real time actions with teammates in milliseconds resolution. It's obviously not about clicking fast, but it is about timing, sometimes 100 milliseconds reaction time make huge difference in outcome. It is usually making decisions on very small time scales. Do you retreat or continue? Use ability or hold it? Can you overextend? The only meaningful strategic decisions in dota (which you have long time frame of deciding and effect the game for a long duration) are draft (which AI doesn't really master, they reduced the heroes pool to simplify) and item purchases, and there are only a handful of them (~6) in an entire game. Other decisions don't really have a long "memory" time, a minute or two at the most. After two minutes every other decision is just reduced to the relative advantage between the teams. There used to be one hero in Dota which made it a strategy game instead (techies). But it was like playing a different game and everyone hated it and it was effectively removed. Techies was like playing stratego against chess players, they obviously get pissed off by not playing what they wanted.
    - dtdynasty 4y ago
      There are larger strategic decisions that are significant in dota. Which area of the map to play, which objectives are important and when, what type of fights will we win (fast and bursty) and when will we take them. Often times these are thought of at the beginning of the game and effect gameplay throughout.
      - machina_ex_deus 4y ago
        That's pretty tactical decisions, usually made in a time window of like 20-30 seconds top. Takes like 40 second to reach more than half the map from the base. Fighting decisions usually also get tactical. I would say that 90% of the game deciding decisions have a time window of less than 30 seconds to make. 70% are in a time window of seconds. You don't make a strategic decision to fight ever, you make tactical decision when the map looks fitting. If you take strategic fights because of long term strategy (instead of deciding tactically) in Dota you will lose.
- rosmax_1337 4y ago
  Dota at the mid-casual and high-casual brackets (which is where you find most players) is also a social game. Establishing efficient leadership, communication and cooperation in a game gives you a huge advantage. And the low-casual and the pro levels you find it becomes more a game of skill and strategy funnily enough. (The old joke is that Dota is a 1 v 9 game, not a 5 v 5)
  - mst 4y ago
    I periodically still drop in to Subspace/Continuum Trench Wars and in a multi hour play session will generally spend the first hour dogfighting and then get annoyed with the performance of my assigned team and switch to a command ship and spend a lot more time typing encouraging other pilots to do the sensible thing than I do actually fighting. Both modes of play are fun, mind, but the parallels struck me as worth noting.
Tenoke 4y ago
Starcraft and Dota benefit a lot from having good micro. Stratego seems to be only macro. Micro is easyish for AI and requires less long-term thinking to get benefits from.
- adgjlsfhk1 4y ago
  Starcraft especially only resembles a strategy game in GM (and maybe high masters). Below that, the strategy is mostly macro better so you have more units.
fnbr 4y ago
I don’t think it is more challenging than StarCraft or Dota. Does the blog post claim that anywhere? Stratego is way more challenging than Poker, though. StarCraft/Dota/Stratego have the property that you can’t represent their imperfect information as a vector in memory, whereas you can easily do that in Texas hold’em poker (there’s only 52C2 = 1024 possible hands). So for those games, you have to use an approximate distribution rather than the exact one. I’m an author on this paper (although my contributions were relatively minimal) and on the Player of Games paper (which did Poker, Chess, and Go).
- jstummbillig 4y ago
  > I don’t think it is more challenging than StarCraft or Dota. Does the blog post claim that anywhere? My very naive question question being: Why tackle this after SC and Dota have already been done? What is the scientific interest? Stratego seems strictly simpler than both of these games. In what way is this an advancement over how SC/Dota AI were solved?
michalsustr 4y ago
Great question! I would say the main reason why this work is significant is that StarCraft agent was bootstrapped from human replays, and Dota agent did not have game-theoretic guarantees on minimizing exploitability (i.e. how far the strategy is from Nash equilibrium). The R-NaD algorithm with neural nets (behind Stratego) starts from scratch, and has game-theoretic guarantees. In principle, the AlphaStar's league approach (from StarCraft) could be done also in Stratego, and it would be very interesting to compare the two approaches. Note that AlphaStar is more expensive: it required to train N competing agents with pair-wise evaluation costing N^2, while Stratego's NeuRD trains a single agent.

deleted 4y ago

[deleted]

waprin 4y ago

Great article. I played Stratego a lot as a kid and it always felt simpler than chess, go , or poker so it’s surprising it’s a much bigger game tree unless you stop and think. I’m curious about the comparisons to poker. I know the hot algorithm in poker solvers is counter factual regret minimization. The article indicates that the feedback cycle is too long for those algorithms to work but I’d be curious to learn more about the relationship from CFR to what’s tried here, if any.

_HMCB_ 4y ago
I played it too. My goodness what a blast from the past. To be honest, none of my friends liked to play. I mostly played by myself it seems. LOL.
- TecoAndJix 4y ago
  I had star wars stratego that i played where they reversed the number values. It was characters from the OG trilogy and episode 1. takes me back! $80 on amazon for that version :(
gcanyon 4y ago
The "complexity" of a game is not very well measured by game-tree size alone. Wikipedia lists multiple factors on the game complexity page: https://en.wikipedia.org/wiki/Game_complexity#Measures_of_game_complexity https://en.wikipedia.org/wiki/Game_complexity#Measures_of_ga...
fnbr 4y ago
It’s very hard to use CFR in Stratego because you can’t represent the hidden information in memory. In poker, the hidden information is a 52C2 vector, so you can easily pass it around. Not so in Stratego, so you have to do something else. RNAD has similar theoretical foundations though.

beefman 4y ago

There's an extra space in the link to their code (at the end of the article). The correct URL is: https://github.com/deepmind/open_spiel/tree/master/open_spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_spie...

ArtWomb 4y ago
Wow! Thanks to DeepMind for OpenSpiel! Am looking forward to ai experimenting with Stratego, Battleships & Hanabi ;)

beefman 4y ago

The paper is sadly paywalled. I believe this is the preprint: https://arxiv.org/abs/2206.15378 https://arxiv.org/abs/2206.15378

clolege 4y ago

It's interesting to watch the videos they link of deepmind playing against the top-level Stratego masters [0]. I usually find Stratego to be a bit of a dull game (less elegant and more drawn out than Go and chess), but I'm a sucker for watching top-level AIs play. Its skills for bluffing are both fascinating and a bit scary. [0] https://www.youtube.com/watch?v=HaUdWoSMjSY https://www.youtube.com/watch?v=HaUdWoSMjSY https://www.youtube.com/watch?v=L-9ZXmyNKgs https://www.youtube.com/watch?v=L-9ZXmyNKgs https://www.youtube.com/watch?v=EOalLpAfDSs https://www.youtube.com/watch?v=EOalLpAfDSs https://www.youtube.com/watch?v=MhNoYl_g8mo https://www.youtube.com/watch?v=MhNoYl_g8mo

ep103 4y ago
Are these games against stratego masters? I'm watching the first one, but it doesn't say who they're playing against
- clolege 4y ago
  yep, top anonymized players
- sdwr 4y ago
  Dont think the player pool is very deep, doubt there are many masters around..
  - topaz0 4y ago
    What makes you think that? The article says that one of the coauthors used to be a world champion, which suggests to me that there is some kind of competitive organized league.
    - hgsgm 4y ago
      How many people study Stratego as much as an International Master studies chess?
      - 4y ago

sdwr 4y ago

I remember seeing a version of the paper earlier in the year (it talked a lot about getting the bot to be aggressive to avoid stalemates). Feels like the secret sauce has to be probability distributions guessing what all the pieces are. Bluffing in stratego seems like it requires long-term planning (if you move a 2 like a 10, you have to keep treating it like that for the bluff to work).

dr_faustus 4y ago

Call me a cynic but the fact that after almost 10 years of AI hype we are still working our way down the list of popular board games is a bit of a downer for me. I mean, having AIs to play Stratego, Risk, Go, Diplomacy and what have you against sure is nice. But there are literally billions of dollars spent on these projects and I really come to the point where I just don't believe anymore that the current AI approaches will ever generalize to the real world, even in relatively limited scopes, without the need for significant human intervention and/or monitoring. What am I missing?

rg111 4y ago
> after almost 10 years of AI hype we are still working our way down the list of popular board games That's what one lab is doing. You cannot be blind to many many applications that are finding their ways to consumers and earning people money.
VHRanger 4y ago
AI remains better than humans at anything that has well defined rewards and small time gap between action and feedback mechanism (either naturally, like poker, or by value function engineering, like Go or Chess) The problem here is that it's missing the "glue" to more real world applications. This is where more humdrum software engineering comes in. Diplomacy in this is much more interesting than Stratego or beating the next video game - it mixes cooperative game theory with NLP and reinforcement learning.
- dasil003 4y ago
  > The problem here is that it's missing the "glue" to more real world applications. This is where more humdrum software engineering comes in. This is a bold statement. The world does not function based on "well-defined rewards". The concept of "common sense", which some consider table stakes for a human operating competently in our world, is mostly made up of things which are neither well-defined, nor allow a tremendous amount of training data. Current ML approaches require both.
  - 4y ago

Waterluvian 4y ago

One of my favourite things about watching AIs learn and play games I’ve played is seeing if they come across the same weird strategies I did. I remember my brother and I as kids playing Stratego and discovering the “impenetrable bunker of bombs” to put your flag in. Which evolved to “put a scout in as a ruse” and later “don’t actually enclose it because now brother just assumes it’s enclosed.”

sodapopcan 4y ago

Did anyone else call the dude with the tall hat "Hat Guy" despite them all having hats?

IggleSniggle 4y ago
Of course, yes!
- sodapopcan 4y ago
  Ha, amazing! I always thought it was a thing but then occurred to me that it was maybe just my friends and me who said this. I'm glad to know it's a thing. Thinking back it may have been the sergeant who was the primary Hat Guy as I remember there was "Hat Guy" and later "Other Hat Guy".

midoridensha 4y ago

I'd rather learn how to play Strategema.

turtledragonfly 4y ago

Tangentially taking this opportunity to mention the far-superior "Lying and Cheating" version of Stratego, that (as far as I know) my father invented. It makes the game so much more interesting, IMO. Played it a lot as a child. Here are the basic rules, when a piece is attacked: * The attacker says what their piece is, without showing it (they can lie) * The defender says whether they believe that * The defender says what their piece is, without showing it (they can lie) * The attacker says whether they believe that * ONLY IF someone calls a bluff is that piece revealed. Otherwise, it is treated as the piece it was claimed to be, and kept hidden. * If someone calls a bluff, and they were right, then the other player loses a piece (reach over and remove any piece you like) ** If you pick their flag, then you win — game over. * Likewise, if someone calls a bluff but is wrong, then *they* lose a piece. * After all of that is resolved, do combat as normal, with pieces having either their revealed or not-revealed claimed value, as appropriate. Once you resolve all this, there is no "memory" - you can claim it is a different piece in the future. Some minutiae: * You can move any piece as though it were a Scout (9), but when you do the move, the other player can call your bluff since you're essentially claiming it is a Scout at that moment. Resolve that bluff/call before completing the move. * You could even call a bluff on *any* move someone makes, if you believe that piece is a bomb or flag (and thus cannot move). * You can attack with a bomb! It's a two-step process: first you move (and they could call your bluff, if they know it is a bomb - see above). Then, when the attack happens, you say it *is* a bomb. Of course, your opponent may say their piece is a Miner, and if you haven't seen it, it's a dangerous proposition (since bombs are rare). ** You can also do a variant where bombs can't attack (by attacking, you are claiming it is *not* a bomb). I prefer the above version. Overall, I find this version of the game is a lot less boring. Since you'll probably get several pieces zapped over the course of the game, it affects your flag placement. Plus, you can move flags and bombs, making it more dynamic. Also, the "remember where things were" aspect is even more poignant, since once a piece has been revealed, it loses all the power of being whatever-is-needed-right-now (assuming the other player has a good memory). So, for instance, you can do something crazy like move your bomb as though it were a Scout, all the way across the board, onto an opponent's piece, but then claim it's a "5" instead for the attack. Then if it survives, just let it sit there, continuing to be a bomb in the future (causing havoc).

4y ago

waynecochran 4y ago

I 404'ed when I tried to access the source code? https://github.com/deepmind/open_spiel/tree/master/open_%20spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_%20s... Someone needs to create a web front end for this -- I would love to play it.

gus_massa 4y ago
As beefman noted in another comment, the problem is that the link has a space "%20". The correct link is https://github.com/deepmind/open_spiel/tree/master/open_spiel/python/algorithms/rnad https://github.com/deepmind/open_spiel/tree/master/open_spie...

beebeepka 4y ago

What happened to mastering StarCraft? Why did these guys give up after a mid tier pro player defeated the bot handily on live stream? They were super enthusiastic up until that point.

bni 4y ago
Have a link to that? Very interesting question btw. I'm also interested in the StarCraft AI state of the art 2022. If it exists. Or was focused changed to some other game?
- beebeepka 4y ago
  Just look for deepmind StarCraft in YouTube. It won the first event but people came on top during the second event which turned out to be the last one if memory serves

JimWestergren 4y ago

On a related note and surely interesting to the HN crowd I invented Clesto which is similar to Stratego but a bit more like chess, based on an old chinese game: https://clesto.com/ https://clesto.com/ - it is more quick to play and has open information.

7373737373 4y ago

I'd love to see them tackle Chess https://en.wikipedia.org/wiki/Proof_game https://en.wikipedia.org/wiki/Proof_game