For Stratego, I'd start by implementing some of the basic strategies humans use, such as trying to identify the enemy pawns, and most of the time, playing with the known pieces, to hide your own info.

Minimax can be used, in combination with this on the state space you know ( the pieces you discovered). Add general weights to actions such as "attack" (go in with a high level piece and take out those you know), "identify pieces" (send scouts to find out what's what), "defend" (how can I kill the high level piece in my backyard). For pieces movement think about the shuffle puzzles :D

This should give you an ok, player to go up against. If you want a smart AI for stratego, I suggest you keep finetuning this, and incorporate board-setup strategies, mining, protection of pieces, etc... Unlike chess, not every piece can be attributed a certain value, as in stratego pieces have a value depending on the situation of the board. (e.g. miners becomes virtually useless when you have identified all bombs, and they are not in the way...)

You can use a NN to attribute values to the pieces, but I doubt this will get you better results.

Rhun

Stratego has some elements that are more complex than chess. Since you don't know what the enemy pieces are, the path is clear for strategies involving bluffing and deceiving your opponent. Treating all unknown pieces the same probably won't work too well since a human player would try to reason about how the enemy moves and positions their pieces. Considering every possible way the enemy pieces could be placed would make the search space too big, and even if you could consider every possibility, you'd still need to decide how much risk to take. Should you play defensively, trying to avoid losses, or should you play aggressively, trying to gain a better position by taking more chances and possibly losing more pieces?

When people say game tree search, they mean something like minimax or expectiminimax. The game tree is just an abstract description of all of the possible sequences of valid moves. From the start of the game to the end, every choice is a decision to follow one particular branch.

First of all, instead of trying to find the actual values of the pieces that you don't know, you could find an upper and lower limit. (for example - I know that the value is between 4 and 7)
Then after knowing what some of the opponents pieces are you could use some kind of statistical algorithm to determine the other ones. For example, most players wont put the best piece (1 - let's say that 1 is the best, 2 is second best...) next next to the 2. the miners have a better chance of being in the back than a 4, usually people distribute the pieces evenly - so if you found a 3 on the left side of the board there're good chances that the other one is on the other side.
With a list of rules like these you can get a good estimate of the upper and lower bounds of all the pieces even though you're only sure about a few of them.
One example of an algorithm that could do this would work in a similar way to a flooding algorithm - using the values of the pieces that you know get estimates of the peices next to them - then the pieces next to them...

Also, most players learn some setup when they're little and use the same one for the rest of they're lives! So, if the ai saves the moves, after playing one game it ai could reconstruct the players position and remember it for the next time:)

-Daniel

At one point I was thinking a lot about Stratego AI. Here are some random jumbled thoughts:

Stratego oftens turns into a game of perfect information in the end-game. If your goal is to create a killer Stratego AI, you will probably need it to be competitive. You'd have to have a great heuristic to tame the branching factor though.

I would separate the AI into two components. The first component is responsible for watching the enemy's moves and trying to predict the values of unseen pieces. Here are some sample heuristics that might work:

* The opponent is more likely to move high-value pieces than low ones.
* If the opponent is moving a piece towards a known bomb, it may be a miner.
* The flag is likely to be near enemy bombs.
* Any piece approaching your 1 is highly suspect (maybe trigger a scouting priority on this piece)

The first component assigns each unknown piece a probability distribution (i.e a single piece may have a 10% chance of being a 1, a 5% chance of being a 2, and a 85% chance of being the spy). This information is then considered by the second component, which is the module responsible for reasoning out the move to make on a given turn. It would consider the fact, for example, that if a particular piece with an 85% chance of being the spy is approaching your 1, then you had better intercept it or run your 1 away.

I'm not really sure what sort of planning algorithm is suitable for the second component. Minimax would fall apart rather quickly due to branching factor and snowballing uncertainty. What you really want to do is generate several multi-turn plans, and pick the one most likely to improve your position.

It may be that you could pre-define a handful of plans like "scout piece X" or "move miner to X" or "intercept piece X", continually assign them all priorities based on your board assessments, and run with the most popular plan.

Well I did say they were jumbled. Hopefully that was reasonably cogent.

Good luck and let us know if you get anything working.

Curious:

Were you planning on writing an AI to setup the pieces as well? Or were you going to use a "book" of starting configurations? In either case, you might look at how chess engines do "book learning" - a well tuned openning book can increase the strength of a chess engine by more than 200 points in my experience.

Of course you would only save the starting configurations in the book, not the move history like a chess book.