Quote: Original post by alvaro
There are two things that you might have missed. One is that in this game it seems to be the case that the rank of the enemy piece is not revealed after a challenge, so you generally don't learn that a piece is definitely of rank 6, only who won.

Oops... I was thinking 2-person Stratego like when I was a kid. The only thing you can do after a battle then is say "I know this piece is greater than N." Still pares things down a bit.

Just throwing my $0.02 in.

I'm not so sure Bayes with a gametree would be of much help here, given that the probabilities of knowing a piece are so small; 0.04 * 0.04 = 0.0016. A 0.16% chance of knowing a piece out beyond one move is too low. This would be like trying to play poker based on card distribution, which I think we all know doesn't work. :)

Is it fair to say that all you can know about each opponents pieces is a minimumn value, and a maximum value?

If so, have you considered using a two phased approach?

1. Doing a 1-ply search of the game space
2. A logic routine that trumps decisions from 1.

1. Start the game by assuming every one of the opponents pieces is the most powerful piece (min = MAX_VALUE, max=MAX_VALUE). Then do a shallow 1 ply search, looking at all of your move possibilities to depth 1, and count the total number of wins/losses for each move. The best move is the one that results in the highest ratio of wins / losses. As pieces are lost/won, you will know the maximum (for you winning), or minimum (for you losing) strength of a piece and can adjust your knowledge accordingly.

2. As you begin to know what the min/max values of the pieces are, a logic routine should be able to tell you exactly what moves (if any) will result in a win, which pieces of yours are doomed, etc... Basically your logic routine will be able to make decisions using hard-coded rules.

You could also extend the search to depth 2,3,4,5, etc.. based on how much knowledge you have about the board (and how much knowledge your opponent has about the board-- this would require you to track both players knowledge). So at the beginning you do a depth-1 search, (50% knoweldge). At 60% knowledge, do a depth-3 search. At 70% depth 4, etc..

Throw in an opening book and you're done! Makes me want to try this out now. lol. :)

Quote: Original post by willh
Throw in an opening book and you're done! Makes me want to try this out now. lol. :)

Please, do try it out. :D

I sent you a PM. This is a very interesting game. It's like a mix of Clue, Chess, and Poker.

I'm willing to setup and host a webservice to broker and manage games if anyone else is interested in getting involved. I'll make sure it is simple enough for HTTP POST or GET, so no SOAP libraries neccessary.

The approach I'm taking is similar to what I mentioned earlier. A question about the rules:

Do you know if there is a rule for a forced draw? Towards the end game, if someone is trying to advance their flag, it seems possible that you could run in to a situation where neither player can win as long as one player keeps moving in a certain pattern.

Quote: Original post by willh
I'm not so sure Bayes with a gametree would be of much help here, given that the probabilities of knowing a piece are so small; 0.04 * 0.04 = 0.0016. A 0.16% chance of knowing a piece out beyond one move is too low. This would be like trying to play poker based on card distribution, which I think we all know doesn't work.

However, we don't need to know exactly what the piece is. We need to be able to estimate win/lose/tie. By adding up the percentages above and below your own (known) piece, you can estimate that.

Quote: Original post by InnocuousFox

Quote: Original post by willh
I'm not so sure Bayes with a gametree would be of much help here, given that the probabilities of knowing a piece are so small; 0.04 * 0.04 = 0.0016. A 0.16% chance of knowing a piece out beyond one move is too low. This would be like trying to play poker based on card distribution, which I think we all know doesn't work.

However, we don't need to know exactly what the piece is. We need to be able to estimate win/lose/tie. By adding up the percentages above and below your own (known) piece, you can estimate that.

I think I get what you're saying, but I'm still caught up on how that would relate to a game of Poker. You _could_ play Poker that way, but probably wouldn't. It's the same kind of idea isn't it?

Quote: Original post by willh
I think I get what you're saying, but I'm still caught up on how that would relate to a game of Poker. You _could_ play Poker that way, but probably wouldn't. It's the same kind of idea isn't it?

Actually, using a Bayesian approach to figuring out what the opponents have is very very reasonable in poker. I googled for `poker bayes' and I found this page, which describes exactly how I would go about implementing a poker bot.

The reason that you don't want to play poker with Bayes is that the set of cards actually in play is often small compared to the deck as a whole. Anything that is still in the deck (and stays there) is not only unknown but largely irrelevant. That means the state space is large, but not necessarily in play.

However, in the topic game, you know exactly what is on the board at the time. That is, you know the other player's "whole hand" -- just not what order it is in.

For starters, you know that any given piece has a 1 in 21 chance of being a specific piece. With some of the duplicate pieces (private/spy), you can combine multiples together. That is really not that thin of a chance. I don't know where you were headed with your math earlier. The point being, if you combine these percentages together, you can get to that higher/tie/lower aggregation that helps you make a decision.

For example, if you take a middle rank piece, you could have a 48% chance of winning, a 48% chance of losing, and a 4% chance of a tie on any given random piece. If you lose to Piece X, however, you now know that Piece X is higher than your piece. You don't know what it is, though. You DO know that you can evenly distribute that percentage to all of the remaining pieces higher than yours. To make it concrete:

Piece listing for reference.

If your 2nd lieutenant piece loses, you know that the other player's piece (X) is 1st lieutenant or above. There are 10 pieces that fit that description. Therefore, Piece X now has a 10% chance of being any of those 10 types. If, however, a few of those pieces had already been captured, that percentage for piece X being each type would be higher.

Assume, however, that no other pieces have been captured. If I estimate my odds of winning against piece X, but this time with a 1-star General, we can expect a 50% chance of winning, a 10% chance of a tie, and a 40% chance of losing.

Our proposed plan of action, therefore, would be able to take into account all the knowns (our pieces) combined with the unknowns (the other player's remaining pieces) and predict the potential for winning and losing. By running the math using estimated maximization of utility, we can determine which potential action is preferable at any given time.

Quote: Original post by alvaro
Actually, using a Bayesian approach to figuring out what the opponents have is very very reasonable in poker. I googled for `poker bayes' and I found this page, which describes exactly how I would go about implementing a poker bot.

That's a really good article on poker but you might have missed this part:

Quote: From http://www.cbloom.com/poker/book/103_bayes.html
P(H|A) = P(A|H)

Here "H" is some hole (two cards) and "A" is the set of their actions you have seen

The author describes modeling known observations about his opponents past behavior as they relate to hands. He's added a player model. That is not Poker based on plain card distrubutions! His method would work with someone who bluffs.. straight card distribution will not. :)

I just reread your earlier post Alvaro. Were you implying a player model from the get go? I noticed you included 'flag moving alone unprotected' as a low probability event, which implies you could have been.

Hopefully we can test this discussion out soon enough. I'm almost done an implementation of what I described earlier. It plays well defensively but has no offence. 'The only winning move is not to play' ;)

Quote: Original post by willh
I just reread your earlier post Alvaro. Were you implying a player model from the get go? I noticed you included 'flag moving alone unprotected' as a low probability event, which implies you could have been.

Yes, I was assuming some sort of opponent model from the beginning. I should have been more explicit about it.