# Algorithm for figuring out the enemy flag's location in Stratego

I am currently programming a Stratego game in `JavaScript`, simply because I wanted to learn to use JavaScript while spending some time to keep my programming skills up to par. (My current work assignments involve no programming.) This info is not entirely relevant though. :-)

The thing is, right now my AI works pretty well already. The AI remembers ranks of pieces that have already been revealed, and will capture or flee depending on this. Pieces that have not yet been revealed are also taken into consideration. For instance, a Marshal will not capture a piece if there's an undiscovered piece next to it, since this latter piece could be a spy. If the spy is no longer alive, the Marshal will only be afraid of non-moving pieces, since those could be bombs. If an unknown piece moves up to the General, the latter will flee, as the unknown piece might be a Marshal. Etc, etc.

My problem is that the AI is currently extremely defensive. It will jump onto opportunities to capture pieces, but it never "plans" to move anywhere, and it never takes the Flag, since it thinks that the Flag might as well be a bomb.

The question is: are there any patterns that can be used as the basis of an algorithm to figure out where the enemy's flag might be? When human players play against each other, what are their tactics to find out the flag's location?

(Note: in the current version, pieces are placed randomly on the board for both players. In the future I will allow the player to place his pieces as he wants, though.)

• This is really about Stratego strategies and may get closed as off topic (maybe you could focus the question more on general AI algorithms). That said my strategy for this game was always to take very close count for what pieces are taken. In certain combinations once you are ahead a single captain doing 1:1 exchanges of the higher pieces and your extra captain is the next general (and fears no spy). Also trying bombs with cheaper pieces (scout) or miners was standard. Commented Oct 6, 2014 at 8:57
• In that respect, you could label all questions about realistic AI as off topic. The purpose is to find something that can actually be molded into a feasible algorithm. Commented Oct 6, 2014 at 9:00
• Yes, problem here is that this would not help you, since your question would get closed. Also with the focus on the actual game and less on algorithms this is more like a discussion on possible approaches or a collection of ideas (as issac9A's answer). Also there was this GameDev StackExchange where this may better fit. Also the fact that an off topic reason applies to a large group of questions (like realistic AI) never kept anybody from closing those questions. That's mostly true for all off topic reasons. Commented Oct 6, 2014 at 9:09
• This question might be more appropriate on GameDev stack exchange. Commented Oct 6, 2014 at 9:32
• Just to be clear, this question is really on topic at both sites. They are merely stating you might get a more targeted or specific answer at GameDev where you might get a larger audience to your question here. Algorithms of all kinds are on topic here. Commented Oct 6, 2014 at 12:38

Designate some of the AI pieces as offensive you should assign certain pieces an offensive role. You would then need to decide whether an offensive or defensive move should be taken on a particular turn. Try to use low number pieces, 2,4,5 for scouting and figuring out pieces' ranks (you can also inadvertently run into the flag this way) then send in threes to break up the bombs. Once the board has cleared up, send in the higher ranking pieces. It might be helpful to keep a list of pieces you have designated as attackers, so you can designate new ones when the old ones die. These are just a few thoughts, to get you started. You should try out a bunch of ideas and see what works best. Try sending out waves of attacks, or maybe wait to unleash a massive attack... There are all sorts of strategies the AI can emulate. Maybe even one strategy isn't optimal. Trial and error is your best friend here. Good luck; I love that game!

• Thanks, that doesn't sound bad! Indeed, my scouts and sergeants are already "exploring" pieces, so they'll be quite aggressive and attack unknown pieces on purpose. Perhaps it would be useful to add lieutenants too, so that the AI will discover the player's pieces at a faster rate. Commented Oct 6, 2014 at 8:56
• You might also want to try sending sensitive pieces such as threes in a pair or group with higher ranking pieces to fend off attacks. Commented Oct 6, 2014 at 8:59

I don't remember how to play Stratego, but in general if you want to encourage a certain type of behaviour in your AI (i.e. being offensive) you have to award some value to that kind of behaviour.

Think about evaluating each potential move on its impact to the overall strength of a position. Ask: "what are the chances of my position being better or worse if I make this move?"

By focusing on the likelihood of a positive outcome, your AI will sometimes make moves that are offensive, but which are calculated risks.