Isn't it kind of a given that poker is only partially about the strength of the cards and mostly about the player? That's not the case with the Generals game. Or at least not relevantly so. Therefore, poker should never really have been brought into the discussion. It is really a distraction from solving the problem at hand.

Quote: Original post by InnocuousFox
Isn't it kind of a given that poker is only partially about the strength of the cards and mostly about the player? That's not the case with the Generals game. Or at least not relevantly so. Therefore, poker should never really have been brought into the discussion. It is really a distraction from solving the problem at hand.

I agree that it should be a given about any game like this this.

I missed the past-behaviour modeling part of your longer post; from what your wrote Dave it seemed very clear that you were talking about determining piece odds from exchanges. Did you edit it out by mistake? Alvaro did find a great example of Bayes and Poker BTW. :)

I think your conclusion about Poker and this thread is based on an underlying igorance of the Game of Generals. Therefore it would appear to be to your benefit (in better understanding the topic of the thread (the Game of Generals)) that I brought Poker in to the discussion. It's the great thing about discussion forums like this, isn't it, when people who are confused or do not understand something can learn!

I highly recommend the forums over at http://salpakanna.com/. There are a few active discussions on strategy. Should anyone take the time to learn about the topic of the thread (the Game of Generals) they will quickly learn that the game employs a very strong bluffing and 'psyche' component. There is a short, but decent, piece there on 'assumptive analysis' as well. You can also study some opening positions if you care. There is a nice little piece on one of the games masters (they use an ELO rating IIRC) and how his memory of players past games helps him win so much.

Quote: Original post by willh
I highly recommend the forums over at http://salpakanna.com/. There are a few active discussions on strategy. Should anyone take the time to learn about the topic of the thread (the Game of Generals) they will quickly learn that the game employs a very strong bluffing and 'psyche' component.

My recent post was necessarily simplistic specifically for addressing how you claimed that you didn't think that Bayesian techniques were helpful. (You were wrong... likely based on your ignorance of Bayesian techniques.) The scope of THAT post was specifically limited to addressing that issue. However, in my post towards the end of page 1 I wrote:

Quote: 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.

So yes, I covered how you can adjust the assumptions of a piece's value based on non-contact information. Because you have a few "priors" on completely mis-reading, mis-interpreting, or simply not reading people's posts, my suggestion to you is that you pay a little more attention to the threads that you post in.

Back to the topic...

All of this assumption can lead to bluffing, etc. After all, bluffing is specifically doing something that either plays into or against the other person's mental model of what you have and/or are doing.

In the above example, I could "run away" with either a very poor piece to make you think it was valuable when, in fact, it is a high level piece. On the other side, I could "run away" with a high level piece making you think it was a lower level one that I didn't want to lose. However, none of that is possible unless I have a mental model of not only what you have, but a model of what you might think I have. On top of that, it is simply a playbook of strategies.

My question to you is... how do you model chains of behavior if you have no way of modeling assumptions of individual pieces? I know you really get all tingly about using player modeling, but all of that is a layer on top of the basic game mechanics. In the end, the beliefs about player tendencies as tweaking knobs. Those knobs are the beliefs of the individual pieces.

This is very much like how reinforcement learning is impossible without the raw numbers representing individual weights in the first place. All the learning does is adjust those numbers.

So, the solution in a situation like this is to model the base layer first and only then add other techniques to modify -- even slightly -- the knowledge represented in the model.

Quote: Original post by InnocuousFox
My question to you is... how do you model chains of behavior if you have no way of modeling assumptions of individual pieces? I know you really get all tingly about using player modeling, but all of that is a layer on top of the basic game mechanics. In the end, the beliefs about player tendencies as tweaking knobs. Those knobs are the beliefs of the individual pieces.

This is very much like how reinforcement learning is impossible without the raw numbers representing individual weights in the first place. All the learning does is adjust those numbers.

So, the solution in a situation like this is to model the base layer first and only then add other techniques to modify -- even slightly -- the knowledge represented in the model.

Good questions Dave. Answer is in the last paragraph.

If you've read any of my previous posts on object detection and pattern classification you may recall that I've used Bayes, successfully, before. You're entitled to make accusations though.

Going back, my original post was about using Bayesian logic with a game tree, and not not about Bayesian logic. The math you didn't understand shows how the reliability of estimates degrade the search progresses deeper in to the tree. That number I wrote was 1/21, in decimal form. I.E the odds that 1 piece is the sergeant. I should have been more explicit about it.. Dave, rather than argue with you about my ability to multiply numbers: Assuming a piece exchange at each ply, what are the odds that the game trees model of the board at ply 5 is 100% correct. Or, how confident can the AI be in the game trees model? When you work it out and see how staggeringly low the number is, I hope you will see my point. Or you'll prove me wrong and I'll have learned something new. :)

You are accusing me of not reading, or misunderstanding, the posts but I think you're making that mistake yourself Dave. The point I missed was with Alvaros and how it related to the Poker paper he linked to, and I noticed it before I even posted my comment Dave-- it does not change my original argument about probabilities and the game tree. If you read Poker paper, even they do not explore it out past 2 ply (ply being applied loosely in this case)!

To answer your question: In my original post I suggested recording the minimum and maximum known piece strength for each piece. These can be deduced logically as play progresses. These values are known factual limits: not assumptions. With this you can determine absolute outcomes and know which are uncertain outcomes. Each player should always play to win.

I will say it again, Dave. I do not think a game tree using probability distributions will be that effective in this game. I have given my reasons. I have tried to frame the discussion in terms I thought you would understand (Poker, a common game, because you obviously didn't understand this game), and I've even gone so far as to actively implement what I am saying. Have you? I'm willing to discuss it further but not with someone who is acting so rude.

[Edited by - willh on November 4, 2010 5:48:59 PM]

Quote: Original post by willhTo answer your question: In my original post I suggested recording the minimum and maximum known piece strength for each piece. These can be deduced logically as play progresses. These values are known factual limits: not assumptions. With this you can determine absolute outcomes and know which are uncertain outcomes. Each player should always play to win.

But it isn't just the minimum and maximum that is important. It is also how many pieces remain in that range. If I have a mid-level piece that I want to pit against something that could be the highest or could be the lowest, I want to know about the distribution of what else it could be in the middle. If all of the other pieces above me are gone, then it is more likely that the piece in question is below me. That's why modeling the percent chances of each type of piece it could be is important... not just the range.

Quote: Original post by InnocuousFox
But it isn't just the minimum and maximum that is important. It is also how many pieces remain in that range. If I have a mid-level piece that I want to pit against something that could be the highest or could be the lowest, I want to know about the distribution of what else it could be in the middle. If all of the other pieces above me are gone, then it is more likely that the piece in question is below me. That's why modeling the percent chances of each type of piece it could be is important... not just the range.

Indeed, when you destroy a piece, even though you do not learn what that piece is, you do learn that it was some piece with a value less than yours. E.g., suppose you had a Sergeant, and he challenged 5 pieces and won all of his battles. If you had kept careful track of this, you would now know, even though the pieces had never been revealed to you, that only one private remains on the board. This fact would inform later decisions. E.g., say you have a 2nd Lieutenant somewhere else on the board, and you're considering attacking an unchallenged piece. If this had happened at the beginning of the game, your 2nd Lieutenant would have had a 38% chance of winning (assuming a uniform prior). Whereas now, even though the unknown piece still COULD be anything -- the min and max values are the same -- your chance of winning is now only 14%, because you know there are many fewer privates now.

The complete gamestate, I think, is
1.) The positions of your 21 pieces. That's the set ({1..9}x{1..8})^21. Piece identities ca be implicit (through the index in the vector).
2.) A position for each of the 21 enemy pieces. That's the set ({1..9}x{1..8})^21.
3.) for each enemy piece, a probability distribution over the 15 piece types. That's Delta(15)^21, where Delta(n) denotes the probability simplex in n dimensions (fancy-speak for n real numbers between zero and 1 that add up to 1).

Hence your total gamestate is

({1..9}x{1..8})^21 x ({1..9}x{1..8})^21 x Delta(15)^21

which you would most straightforwardly represent with 42 bytes for the positions and 315 floats for all the probability distributions.

This is small enough that it seems manageable to do a straightforward Bayes update here without being clever with Bayes nets or anything.

Right?

[EDIT: Actually the gamestate is larger than this. See later posts.]

[Edited by - Emergent on November 6, 2010 12:27:28 PM]

Quote: Original post by alvaro

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.

When I did this - matching behaviour to hands - I went for a clustering approach based on matrix factorization. i think i'll go ahead and try a bayesian approach see which is better. I suspect the bayesian method will need alot more data to become perfomant.

Quote: Original post by Emergent
This is small enough that it seems manageable to do a straightforward Bayes update here without being clever with Bayes nets or anything.

Right?

Yes... the math of what pieces are out there is very simple to recalculate once a transaction occurs (or another event that may change your idea of what something is as mentioned before).

Once you have this information, you can actually do something along the lines of a tree search with the final outcome of a node (regardless of depth) being a combination of the probabilities on the path through the tree to that point. Rather than a binary outcome at each layer (e.g. tic-tac-toe), you are rolling up percentages of survival.

Obviously, searching to the bottom of the tree is not only computationally next to impossible like in chess, but isn't really necessary. It also becomes statistically less significant the farther in that you go. Thankfully, you can actually do fairly well by only doing a few plys per move.

There is a meta game on top of the moves, however, that would merit its own decision engine. For example, you might be interested in a war of attrition for the most part, but leaving a high-value piece back to defend your flag. You might want to play it cagey and let the other player come to you. Those are simply two examples.

These strategies can be pre-defined in a playbook of sorts and even conditionally changed mid-game. In fact, it would be advisable to change strategies based on the comparative aggregate makeup of the two forces. e.g. "If my war of attrition is not going well and he really outnumbers me, pull back to a defensive mode."

Regardless, the base information is your perception of what the other player has -- to the best of your knowledge.

Logical deduction should be the same for both a probabilistic model and a min/max range model.

This is what I've done so far, and it seems to be working.

- Keep a count for each piece type (private=6,spy=2,segeant=1,.....)
- Flag every piece with a min and max value (3=private, 14=5star general)
- Flag every piece with MaybeSpy = true, IsSpy = false
- Flag every piece with MaybeFlag = true, IsFlag = false
- Flag every piece with a BestCapture=-1

You'll notice I do not count the flag or the spies in min and max initially. All pieces are said to be 'privates' or '5-star generals'. The MaybeSpy flag is used to track if it's a spy or not.

Retain this information for every piece, even ones that have been captured.

When the arbiter reports move results we update min,max,maybespy, etc... Ties (splits, as they are called) obviously identify the piece in question. All of the logic mentioned so far (private winning = spy identified, 5-star losing = spy identified, spy losing=private identified, sergeant winning=private ID'd) is handled here. I wrote three separate functions; ProcessTies, ProcessWins, ProcessLosses.

Next phase is deduction. Lots of small rules, but in general:

Deduction() is called recursivley until nothing new is deduced.

A few examples from my Deduction() routines:
- A function called 'CountSharedMax(int pieceType)' returns the number pieces equal to or exceeding the specified piece type. Any time CountSharedMax returns 1, we know the identity of the 'pieceType'. If it returns 0, we know that piece type doesn't exist anymore.

- Same for the min value. CountSharedMin(int pieceType).

- If we know a piece is not a spy, we can readjust its min value based on what its BestCapture was.

- Any time min=max for a piece, all other pieces sharing it's max get demoted, and all other pieces sharing it's min get promoted.

I'm being overly general here, otherwise this would be a novel. With this process it's possible to continually refine and identify pieces (even ones that have never engaged in combat). I think it's the same for both probabilistic and min/max..

Emergent, the example you gave is bang on. The deduction approach I just described would reveal that there is only 1 private left, but since it does not work on odds, it wouldn't say anything other than 'the results of this challenge are uncertain'.

If you treat all uncertain outcomes as a win for the opponent, the game tree will seek to minimize the worst case scenario. I don't know what this actually means in the context of a game with a good player though. :)

I'm adding this as part of my edit:
I think it would be possible to derive the probabilties for what a piece is by checking the range of min to max, and looking at the tally for the piece counts to calculate a distribution (where the sum = 1.0).

[Edited by - willh on November 5, 2010 1:09:41 PM]

Quote: Original post by willh
If you treat all uncertain outcomes as a win for the opponent, the game tree will seek to minimize the worst case scenario. I don't know what this actually means in the context of a game with a good player though. :)

Treating all uncertain outcomes as a win for the opponent will result in a program that is really easy to bluff.

I think your deduction method is the right thing to do, but it could be extended into something that generates random scenarios that are consistent with all we know so far. If you get that and it's fast, then Monte Carlo methods may work really really well.

I am thinking of writing a program myself (if I find the time). Where can I find the exact rules of the game and/or a program that implements the rules so I can test my understanding? EDIT: Actually, I just re-read the description of the game on Wikipedia, and it seems complete: I thought there was something missing.