Can expert humans beat the hand crafted bots? I'm guessing no. Also, what's stratego like without the hidden units? Is that... hard?
How can I use these 200 IQ moves against a bot?
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?
> 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).
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?
> 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.
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.
> Touching one of his own pieces does not oblige a player to move it.
It also says:
> Psychology, bluff and misleading manoeuvres are considered important aspects of Stratego. Bluffing consists of all verbal communication (talking) or non-verbal communication (acting, mimic or feign) which is intended to mislead your opponent. All forms of bluff are allowed at any time during the game, unless prohibited by any other rule. Abuse will be considered unsporting behaviour and can be penalized accordingly.
So I think you won.
1: https://isfstratego.kleier.net/docs/rulreg/isfgamerules.pdf
> 5.2 Moving
> Flag and Bombs are never moved (For the definition of „move‟: see chapter 6).
Chapter 6 shows the sequences of moves, and then Chapter 7 says:
> A move is made when:
> a piece is released on another square than the starting one, or
> a player touches an opponent‟s piece with one of his own pieces or with the hand in which his own piece is held.
So if the piece was picked up and replaced on the starting square, it was not moved, and that's fine.
On the other hand, these rules incorporate some other rules by reference which includes:
> The bombs and the flag may never be moved and therefore remain in the same place throughout the duration of the game
A bomb hasn't exactly remained in the same place if it's been picked up, has it?
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.
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
Of course, dissatisfaction with such outcomes has often resulted in further wars.
See the Deep Mind "Player of Games" paper from last year for an agent that takes a more game theoretic approach, which is probably needed for "simpler" games like Poker, that we can play to higher levels of accuracy: https://arxiv.org/pdf/2112.03178.pdf
What is the SOTA on solving non-adversarial (single player?) POMDPs? Are those considered to be much simpler problems?
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.Whit...
Well, solving a Partially Observed Markov Decision Processes in general isn't just NP-complete but actually undecidable. So I'm not sure how one measures SOTA (state of the art).
POMDP just means "observations are not state" and that you need to use a stateful policy to infer the state somehow, but without further assumptions it's difficult to answer this question
She’s one of the few people who can regularly beat me at war games. The Avalon Hill and GMT types. My favorite example is the time she carefully mislead me into believing that she hadn’t found the other end of a wormhole that opened near my home-world in a game of Space Empires 4x. Spent the whole game exploring and increasing ship speed and weapons just enough, waiting for me to commit my heavily armed, but slow-ish ships. Then, giggled, and sighed for relief, as she paid the overnight rate to send an armada to my doorstep. Oh, and time she slipped a WMD into the US in Labyrinth. Or in Starship Troopers..
She likes everything from Codenames to those Rosenberg games that are so heavy they should come with an OSHA training poster.
In Stratego she had bluffed me into believing her flag was in a corner.. But then she move a piece that I assumed was a bomb and her face gave away everything. But a momentary lapse of Stratego-face wasn’t the issue. Mostly, it was just too slow for her. Her last obsession was Tyrants of the Underdark. Deck building + area control.
But this result feels a bit anticlimactic in a world where AIs can already beat expert humans at go, six-player poker, Starcraft, ...
The "card" game can be viewed as a form of Limit Poker. The bidding in poker is done with secret cards and public bets. In Stratego, you bet with your secret pieces, so it's more like a closed bid auction. But since there are only 10 moveable ranks, the range of bluffs you can pull off is rather limited compared to e.g. No Limit Poker.
Each of the "subgames" in itself are quite tractable for computers. But the numerical product of all public game states times the number of secret information states is humongous. Combine this with the fact that imperfect information game trees don't decompose as nicely as e.g. chess game trees, and computers will also not be able to divide-and-conquer their way out of the numerical complexity with brute force. Whereas humans can come a long way with heuristics.
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.
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.
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.
> 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.
Is there a good online version these days?
Loved it as a kid, though
