Stratego AI

Of course, one of the main issues with Stratego when compared to chess is that you don't know what the pieces are for quite some time. You have to work with some uncertainty based largely on behavior. Scouts moving more than one square are an obvious example.

Additionaly, some of the "solving" of this uncertainty is based on looking for patterns in play. e.g. If there is a large block of unmoving pieces later in the game, we may assume that it is a flag surrounded by bombs. How do we go about recognizing patterns like this?

Even something as simple as "this unknown piece is being agressive - therefore it is likely to be a high-power piece" can be addressed. This is something that can be done with simple reinforcement, though... categorize what an "agressive move" is and slowly bump up the "perceived power" of the unit. Of course, this is a very acceptable decoy move that we all use... and it would fool the computer as well. However, you can't expect to go to that well more than a time or two before it gets old and people see through it... easy enough: each time that move gets proven FALSE, decrease the reinforcement value for subsequent analyses. That is, if I believe that agressive piece is high-powered and THEN find out it is not, make it less important to weigh agressive moves as high-powered pieces in the future. In essence, you are rating and modifying your own pre-concieved algorithms throughout the game.

Of course, the reverse can also be true... if a piece is RUNNING from us, it could be a low powered piece. You can also estimate the value of the piece based on which pieces it KNOWS and runs from. e.g. it runs from a medium piece but doesn't run from a low piece... therefore it is medium-low.

As for doing the moves, a chess tree search would certainly work but would be enormously difficult to do when you are dealing with unknown outcomes of attempted captures. That makes it very hazy to go beyond that particular move in the tree unless you have developed a reasonable certainty of what it SHOULD be based on the above. In Stratego, due to this very nature, we don't generally plan that far ahead anyway... leastways not as far as one might in Chess. It may not be that big of a deal.

Here's a tidbit that should help...

Consider that all the peices on the board have a strength. Given no observations of the strength of a given piece, we can initially assume a probability distribution over the possible strengths of any given piece as being based on the frequency of piece strengths at the start of the game. So, there's only one general in the side, but N pieces, so the (prior) probability that any given pecee is a general (without any other knowledge) is 1/N. Do this for each strength of piece to get a distribution over strengths. Now, given one of your pieces, you can work out the probability of surviving a given combat as being the sum of all of the probabilities corresponding to enemy pieces being less powerful than your current piece. So, if your current piece has strength 4, then the probability of it winning a battle against an unknown strength opponent is p(OpponentStr=1)+p(OpponentStr=2)+p(OpponentStr=3). For special pieces, like scouts, you can add any probability that they win because the opponent is another special piece (e.g. a General) to arrive at the final probability of winning against an unknown opponent. Given the outcome of a combat, you can adjust the probability distribution over piece strengths for each player that lost a piece (since their piece frequency has changed).

Now, here's the other bit that works with this. Once you observe a battle between an enemy piece and one of your own, you automatically know 1) the strength of the enemy piece; and 2) the probability distribution of pieces remaining on the board (assuming a two player game... its more difficult when you don't know which pieces a player has lost in other battles). If the enemy piece survives, then you know its strength, so the probability distribution for piece strength for that piece is a delta function (=1 at piece strength, 0 for every other value). This makes future computation of expected outcome of the battle trivial.

As you move and combat your opponent, the amount of uncertainty you have about the game state decreases.

Now, the bigger problem that you face is choosing a move given what you know about your pieces and what you do or do not know about your enemies pieces. Essentially you want to model future game states with a stochastic state machine. There's plenty of literature on planning in such domains... in particular, look up probabilistic planning. Given the size of the state space, the branching factor and the level of initial uncertainty, you will probably find that you need to perform your planning over a finite horizon.

Just a side thought... you might find some useful information in some of Ariel Budd's publications... he did some work on automated strategic advisors for chess in situations where you didn't know the exact board state (because you didn't necessarily know what a particular piece was and only had observations on the way it moved to make assessments). This is essentially the same problem that you face, except that you have both movement and combat outcomes to reduce uncertainty.


Cheers,

Timkin

Is protecting the identity of your pieces important? For instance, tracking the probability that the enemy knows what your peices are, and selecting moves which minimize this knowledge? Or would that be included in the already suggested resources?

Quote:

Original post by BrianL Is protecting the identity of your pieces important? For instance, tracking the probability that the enemy knows what your peices are, and selecting moves which minimize this knowledge? Or would that be included in the already suggested resources?

Other than scouts, the only way of protecting the identity of your pieces is to not attack or be attacked. That is not going to get the job done in the game. The only piece you are REALLY going to want to be cagey about protecting is the spy. That is one whose position is so vulnerable that you don't want people to know where it is. First, almost anyone can kill it and second, the General will run from it.

Something can be said for keeping your miner secret until they difuse a bomb since they can be stomped by a good portion of the forces and they are a limited asset.

I like Timkin's idea of the probability distribution. In a way, you can almost work with a sort of influence map in this case as well. Use known values whenever possible and use the current aggregate on the unknown values. That way, you can feel comfortable sending high value pieces on those dreaded sweep runs through lower powered areas of the enemy's units.

Quote:

Original post by InnocuousFox I like Timkin's idea of the probability distribution. In a way, you can almost work with a sort of influence map in this case as well.

Hehe... when I wrote my first draft of my reply I had a really big paragraph on an idea to use the probabilities to build a influence map. I suspect you've struck on the same idea, so please Dave, share it with us.

My thought was to roll-out a stochastic state machine, expanding the state space using movement as actions. Since moving into an enemy-held square represents a battle, we could use the probability of winning a battle to determine the probability of the state of the board after the movement. Each battle movement would cause a split in the state space with a probability of each branch occuring; one represents winning the battle and the other losing the battle.

For any given node in this probabilistic search tree an influence map can be created which represents the squares on the board that can be controlled by your army at that turn. Therefore, any given level of the search tree represents the possible set of influence maps after the move that achieved that level in the tree. Since each move has a probability of occuring (based on the probability of winning/losing battles) then each branch of the tree (from the root node to leaf node) has a probability based on winning/losing successive battles. Thus, we can combine all of the influence maps at a given level by summing them and using the probability of the node that the map belongs to as a weight in the summation. This gives us the expected influence map at a given level in the tree. We can then use this influence map to choose an action, given a strategy; for example, control part of the board, find and kill a given enemy piece, break an enemies control of the board.

A slightly more advanced idea might be to build influence maps for each node based on a limited horizon subtree below that node. For example, expand the search tree to depth 12. Then, at depth 9, each node has a subtree of 3 levels below it. These represent all possible states of the board 3 moves after the state at depth 9. Thus, we could build an influence map at depth 9 that represents all of the squares that can be influenced/controlled within 3 or less moves. We can then average this set of maps based on the probabilities of each branch at depth 9.

This map gives a slightly different view of the future board than the simple average map, since it represents an average '3-move' map. One could extend this idea to deeper horizons and deeper averaging trees making the analysis more complete and presumably the AI tougher to outwit!


I'm sure this idea can be improved and I'd be happy to hear how!

Cheers,

Timkin

Wow. Some really interesting ideas here. I did realize that knowledge aquistition (learning the identity of pieces) would play an important role in any Stratego AI, for the exact reason that Timkin mentioned (you can get a more accurate prediction of the average strength of all remaining unrevealed pieces).

I'ven't heard of stocastic state machines before - I assume the idea is you do a minimax search where the evaluation of a position at each node is multiplied by the chance that it makes the correct assumptions of who wins each battle, and by how much? And of course, deeper nodes quickly become less certain. Is this the basic idea or am I completely missing it? Come to think of it, I think I'll probably Google for the answer and educate myself...

Two things I would like to point out:

1. The problem of writing a Stratego AI is really interesting because it seems like brute-force search, while useful for resolving local conflicts, is useless for making long-term plans.

2. I think some long planning is required in Stratego (by "long term" I mean anything outside the minimax search horizon). Stratego isn't just about winning material. Often the board is so clogged up with pieces and the pieces move so slowly that you can win with a decisive thrust towards the flag, regardless of material considerations. Right now I'm thinking a major component of my Stratego AI will be a chunk of code that tries to guess where the opponent's flag is, given his overall piece movements. I don't know exactly how to code it yet, but the basic heuristic is that any piece in the middle of a chunk of immobile peices (lots of people like to surround their flag with bombs and 7s - to kill incoming miners) is a good candidate for being the flag. Later, once I have a database of played-out games from my online Statego server, I might be able to add some pattern-matching algorithm to lay on top of that. Then when trying to choose between moves, any move that puts a peice closer to the supposed location of the enemy flag will get bonus evaluation points. I think perhaps it would be fruitful to use a similar technique to guess the positions of the spy and bombs.

The influence map discussion got me excited because it seems to partially address the problem of long-term planning. I think a multi-tier approach (local conflict vs. global strategy) is required for playing Stratego well.

Unless someone disagrees? I'd love to read more discussion on this!

Sorry to be such a slowbie, but I googled for "stochastic state machine" and came up emtpy, and it's not mentioned in my CS algorithms or automata textbooks. Is there a better term to google for?

I believe you want to search for Markov Decision Process (MDP).

For Stratego, it'd be Partially Observable MDP (POMDP) .

TangentZ already pointed you in the right direction, but if you peek at the definition of stochastic, the connection may make more sense:

From m-w.com:

stochastic:

1 : RANDOM; specifically : involving a random variable
2 : involving chance or probability : PROBABILISTIC

I couldn't find a good definition of 'stochastic state machine' online either. I am sure this was covered here in a thread in the past, but google doesn't seem to be finding it, so here is my attempt:

A stochastic state machine is a state machine where probability is applied to determine the transition out of a state. For instance, on receiving an event, a stochastic finite state machine may select between two or more transitions. The selection of the transition is based on a probabilistic process.

I would recommend that you stay away from MDP and POMDP literature for the moment. They are the end goal that you might try and implement, after you get a basic system going. Essentially, your problem is a complex POMDP. Such problems are, in general, computationally intractable, without simplifying assumptions or approximations. Probabilistic planning is solving a POMDP, although algorithms for solving POMDPs typically attempt to learn an optimal policy (conditional plan) which relates provides a mapping between states and optimal actions. Computing an optimal policy for Stratego would, IMHO, be intractable.

Essentially, a stochastic state machine is a finite state machine where the transitions are probabilistic, rather than deterministic. They are generally known by their various flavours: stochastic maps, Markov processes, dyanamic Bayesian networks,.... (EDIT: Brian got in while I was writing the following!)

Here's a quick tutorial...

Consider the system X that has 3 stats - X₁, X₂ and X₃. Let's assume that the system can, from any state, transition to any other state. Thus, for each state, we need to assign a set of probabilities corresponding to the probability of the transition to the given end state. This would be a matrix looking something like this:

            |  |X<sub>1</sub> |X<sub>2</sub> |X<sub>3</sub> |            |X<sub>1</sub>|p<sub>11</sub>|p<sub>12</sub>|p<sub>13</sub>|P(X<sub>j</sub>|X<sub>i</sub>) =  |X<sub>2</sub>|p<sub>21</sub>|p<sub>22</sub>|p<sub>23</sub>|            |X<sub>3</sub>|p<sub>31</sub>|p<sub>32</sub>|p<sub>33</sub>|

where each element corresponds to the probability of going from the state on the left to the state on the top. Thus, each row must sum to 1, so that the p's are probabilities. Thus, we can write the constraint that

Σ_jp_ij = 1

Now, given a prior probability distribution over states, P(X_i), such that

          |q<sub>1</sub>|P(X(0)) = |q<sub>2</sub>|,          |q<sub>3</sub>|

then we can work out the posterior distribution over states by considering all possible transitions and their probabilities. This is performed by a simple matrix multiplication:

P(X(1)) = a*P(X_i|X_j)*P(X(0))

where 'a' is a normalising constant.

It turns out that because we are dealing with a Markov process here, we can find P(X(k)) trivially from

P(X(k)) = a*(P(X_i|X_j))^k*P(X(0))

This, of course, supplies us with a probability distribution over states. Since our state space is extremely huge (all possible assignments of pieces to squares on the board) we couldn't hope to compute this easily, even with a prior distribution that had a 1 for a given starting state and zeros for all other states (representing the starting state of a game)).

In terms of your game you could build a search tree that encodes specific paths through the stochastic state machine by taking a starting state, adding a successor node for every possible action that can be taken from that state and assigning a probability to the end state. For any end state that doesn't include a battle, all of the end states are equally likely (because all actions are equally likely), so the probability of each is just 1/N, where N is the number of actions.

Let's have an example... assume we have only two pieces which are sitting on a 1D board (a line of squares). Each piece can move either left or right. Thus, at the start of the game, we have 4 branches coming from our root node. These correspond to moving either piece 1 or piece 2 and for each piece, moving it left or moving it right. Thus, each possible outcome state (after implementing an action) has a 1/4 probability.

Now, if an end state has a battle, then we must replace its node with two nodes. The first represents the move and a battle win, the second represents the move and a battle loss. Each has a probability based on the expected outcome given your piece strength (as I described above). Now, the probability of this battle occuring (from the start state) was 1/4. If the probability of winning the battle is q, then the probability for the node representing the win is q*1/4 and the probability for the node representing the loss is (1-q)*1/4. Note how all of the probabilities at this level still sum to 1. This means that one of the states at this level must occur! You can continue to expand your search tree based on selecting a piece and moving it. However, there is another player, so you need to consider all possible moves that they can make. In this way, yes, your search tree is very similar to the sort of tree created in a minimax search. However, the difference is that typical implementations of minimax rely on known outcomes of actions. Here we have probabilistic outcomes, which affect our tree.

You can see that your search tree is going to be very wide for your game (lots of pieces early on) and the probability of any particular path is going to be very small for a moderately deep tree. That's okay...

One way to perform probabilistic planning is to consider the states in the leaf nodes of this tree (For a given depth) and their probabilities and then assign a value (utility) to the outcome state. You multiply the value of that state by the probability of it occuring and select the leaf node with the highest result. This corresponds to the maximum expected utility and the set of actions that lead to that leaf node state is the plan that on average, should give the most reward. Minimax relies on maximising this value while minimising your opponents value. So yes, you could apply minimax to your tree on the expected values (probability * value).

However, I think that given the branching factor and the difficulty with evaluating the value of a state, this approach is going to be problematic. My suggestion of the influence map essentially aggregates, at a given level in the tree, the areas of the board that you have influence over, or can influence within a finite number of moves. Essentially, the first option in my previous post could be computed by considering all nodes at a given depth and for each node: place in each board grid square occupied by one of your pieces the probability of that node occuring. Sum these for all nodes so that for each grid square you get a sum of probabilities of nodes that occupy that square. Each square now holds the expectation value of occupancy by one of your pieces. You should notice that the numbers decrease away from the locations of the pieces in the state at the root of the tree, meaning that from that state, the futher in the future we consider, the less influence we have away from our pieces. You're particularly interested in where your opponents influences are. You can obtain this by considering all of the positions of opponents pieces at any given depth of the tree and computing the same number as above. Thus, you get two maps... places you can control and places your opponent can control. You can now choose actions using this influence map as a basis of tactical analysis.

Do you choose a plan that thwarts your opponent, or one that takes advantage of their weakness in a given area? Do you test the likelihood of being able to get a piece to a given place on the board (likely if you have high influence on that square, unlikely if your opponent has higher influence). These are the tactical issues that must be considered if you go with an influence map analysis of the game board.

One thought that comes to mind with regards to choosing plans is to consider strategies like 'capture the flag' and work out three maps at each depth of the tree: (1) Your influence map, (2) opponents influence map, (3) probability distribution over board states for location of the flag. Then, to capture the flag, you choose actions that maximise your influence in areas of highest probability of the flag location... and perhaps try and diminish your opponents influence in this area.

Cheers,

Timkin

[Edited by - Timkin on June 22, 2004 1:24:06 AM]

Can I add an extra challenge to this? Having learnt what a piece is, if it mixes itself up with a bunch of others I have a tendency to forget which one it was...

There would be an interesting AI vs AI game. Stratego, with a limited number of variables for storing state information. And from the length of some of those replies, we might even get a couple of games going? anyone? ;)

Quote:

Original post by Squirm Can I add an extra challenge to this? Having learnt what a piece is, if it mixes itself up with a bunch of others I have a tendency to forget which one it was...

That would be something that is interesting to simulate - especially to simulate lower ability players. You can give a decay rate that is determined by the number of moves and the proximity to other pieces. If a piece is out in the open and stays there, you would be likely to remember it. If it is sitting in a logjam and there is stuff swarming all around, the decay rate would be faster. On each turn, you can reduce the likelyhood that you will "remember" what sort of piece it is. However, rather than completely forgetting what it is, you could also have it just "drift" somewhat - although I'm not sure how that would help.

Also, the more "unique" a piece is, the slower the decay (if at all). You are going to tend to remember things such as 1s and 2s far more than you will remember 6s and 7s.

Quote:

Original post by InnocuousFox You can give a decay rate that is determined by the number of moves and the proximity to other pieces.

Such a delay would be trivial to implement using the stochastic model above using diffusion of the posterior probability.

Let's say you have, for a given piece, the probability distribution P(X(t)) = [p₁, p₂,...,p_m], where there are m piece types. You can apply a diffusion kernel to this distribution... and interestingly enough the kernel is itself a conditional probability distribution. For example, we might specify the kernel Q(Y'|Y) = [ 0.1 0.8 0.1 ] (note the elements sum to 1, which preserves the mass of the distribution that is being diffused)... this kernel means that if we apply diffusion, each probability p_i will keep 80% of its mass and shift 10% to each of its neighbours (which will be shifting some of their mass to p_i). This is, in essence, a weighted local averaging of the original probability distribution. The actual implementation equation is a discrete convolution given by:

p_i(t') = Σ_{k=-((r/2))+1:(r/2)}(p_i-k(t) * q_k)

where Q() = [ q₁,q₂,...,q_r ].

So, you could perform this convolution once every few frames, or every few seconds - depending on the kernel you design - and this would have the effect of flattening out your probability distribution P(X) toward a uniform distribution, which represents equal likelihood of each piece.

Another idea as to making the AI more dumb would be to purposefully encode mistakes of piece estimation into its AI. You could do this by changing its probability distribution over piece types... so instead of letting it figure out that a particular piece is a general after a combat (because it saw it), actually change the distribution so that it thinks it is a lower ranked piece (or higher ranked if there are pieces of higher rank than the one it saw). This means that all further evaluations are corrupted by the flawed information... which certainly happens in real games because we forget, or didn't look properly when we were shown the piece... or many other reasons.

However, having said all of the above, I would suggest that you first get a basic system working optimally and THEN and ONLY THEN start playing with corrupting the AI to make it perform sub-optimally.

Cheers,

Timkin

Quote:

Original post by Timkin However, having said all of the above, I would suggest that you first get a basic system working optimally and THEN and ONLY THEN start playing with corrupting the AI to make it perform sub-optimally.

Amen, brother Tim!

Wow. That was a lot of helpful information! Thanks guys.

On the subject of getting some AI v. AI games going - I'm designing the GUI client so that different AIs can be plugged in and out of it easily (The exact mechanism will probably be either as DLLs or as standalones that talk via TCP). So once the interface becomes stable, maybe some people will be interested in writing an AI to take on mine - or to play against other human players across the internet. But realistically I probably have about a month's worth of dev time to put in before my project gets to that stage.

Personally I'd go with the TCP/IP communication model... it's more work... but worth the effort for the benefits it gives:

Players/AI don't have to be co-located

You can different computers for different AI in AIvsAI games

It makes online play possible

Cheers,

Timkin