Quote:Original post by swiftcoder

Quote:Original post by alvaro
How hard have you tried to find out on your own what it is?

It is one of those things that is surprisingly hard to google for - only one relevant entry on the first page [smile]

It gets far better if you search for "UCB1 monte carlo".

Going back to Bayes, I would think that you could profile all the pieces based on a sliding belief of what you think they might be. Obviously, everything is equal at the beginning. Once you know what something is, it not only affects that piece but the others as well since the type of piece that is now know is taken off the potential list of the others. Over time, you will hone down what you think things might be. Additionally, you can nudge things based on the other player's behavior. If he starts moving a piece aggressively toward one of your pieces that HE knows, you can assume that it is a higher-ranking piece and slide your assumptions accordingly.

For strategy, you can then work out a shallow-depth min-max that is optimized using utility theory. That is, what are you going to gain/lose over the next few moves. This can support a higher-level strategy such as attrition, a directed attack at a place where you believe the enemy's flag to be, or defending a high-value area. There are other playbook entries that can be devised such as making a hole for a spy using other higher-ranking pieces, etc.

That said, I don't think Monte Carlo is even necessary.

Remember that the Bayes information is only for the unknown pieces. When you discover a piece, then you decrease the "unknown" pool by 1 and the "piece X" pool by 1.

In your example, if you discover the single rank 6 piece, you now have 20 pieces unknown rather than 21. Therefore, the percentage of anything being a rank 6 is now 0%, but the odds of a given piece being something else increases slightly because the denominator is 20 rather than 21. (e.g. 4.7% to 5.0%)

Now, if you are holding a piece of Rank n, and you want to know the odds of you winning, you simply total up the percentage chances of all the things that it would beat (i.e. rank > n). Obviously, include the flag in this list. The same can be said for calculating the other direction. If you put a piece at risk, what are the odds that the unknown piece next to it could capture it?

The fun comes when you start to bias pieces for other reasons. For example, if the other player knows you have a Rank 3 piece that you are advancing and a particular piece of his is running away from it, it is more likely that this piece is Rank 4+. To get really fancy, it is actually more likely that this piece is rank 5 or 6 than it is 7+. After all, he would be more concerned with saving a 5 or 6 than he would a lesser rank. However, that gets all sorts of subjective at that point.

The point is, you can tweak the percentage chance of something manually and have it cascade to other pieces. The trick is to use a fully normalized range that encompasses every piece. As you increase the likelihood of Piece A being Rank N, it necessarily reduces the odds of the other pieces being Rank N and, therefore, increases the odds the the other pieces are NOT Rank N (i.e. all the others). It's a more subtle version of going from whatever % all the way to 1.0 (i.e. I know what that piece is).

So, once you have all these percentages, you can seed all sorts of things... MinMax, Markov models, Monte Carlo, etc. to determine what the "best move" should be at any given point.

(I miss anything Alvaro?)