Quote: Original post by alvaro
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.

If you want I can send you my Piece, Board, and Arbiter classes (along with images so you can draw it all pretty). It's in C#. They're not very complicated but it could save you some leg work.

Quote: Original post by willh
If you want I can send you my Piece, Board, and Arbiter classes (along with images so you can draw it all pretty). It's in C#. They're not very complicated but it could save you some leg work.

Thanks, but I don't work in C# and I am usually pretty quick at the initial part of this type of project.

Quote: Original post by InnocuousFox
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.

Yup, random variables are totally deterministic things, so, a priori, stochastic games are themselves just really large deterministic games; naturally you can search them.

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

This feels dirty. "Are you doing minimax or not?"

I mean, there's a different way you could come at the problem, which is that you could have a collection of different strategies as you said, and then consider the matrix game over those strategies. Throw in uncertainty about the opponent's strategy and it becomes a Bayesian game...

Quote: willh wrote:

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

This seems to be throwing out some information relative to a full Bayes update. Of course, that might be just fine in practice. But with Bayes being as practically feasible as it is for this problem, I'd be really tempted to do it for real. That said, you're the one who's actually getting his hands dirty with an implementation!

Quote: Original post by Emergent
This feels dirty. "Are you doing minimax or not?"

I mean, there's a different way you could come at the problem, which is that you could have a collection of different strategies as you said, and then consider the matrix game over those strategies. Throw in uncertainty about the opponent's strategy and it becomes a Bayesian game...

My thought is that the first-level Bayesian inference can simply be the probabilistic distribution of the pieces. With that "knowledge" (fuzzy though it may be) of the board, you can now delve into certain strategies.

Remember that unlike T-T-T, there isn't just "go here or else". There are actually two goals (get his flag and protect yours) and any given move may or may not support one or both of those goals. When you incorporate different strategies, the difference becomes the thresholds of risk you are willing to endure on certain moves.

With the attrition strategy, for example, you are willing to take more of a risk and, as a result, lose more pieces. As such, the negative weight of losing a piece is not so significant. With the defensive strategy, you could be more risk averse and make losing a piece weigh more than normal. This effect is such that each individual move is not a 0-sum game. (Of course, it wasn't one already because the pieces were different to begin with.)

To top all of this off, you could really use a planning algorithm as a master strategy for the game. The cost/benefit of the moves/captures would end up being your edge weights for the search. *shrug* The problem with that is that each move isn't really a discrete event but rather a series of them. They are all very much dependent on the other player's moves and this could lead to constant re-planning on a scope that is almost useless.

However, you could use the planner at a higher level to select between the strategies. For example, "let's take a few pieces with a high-level piece and then see which piece of his pursues us in response. We can counter that piece. Additionally, this helps us narrow down what could possibly be the flag and we can send mid-level pieces after it." This sequence doesn't get down to the actual move level but gives a general, context-specific strategy. This is much like the multi-level command structure used in many RTS games.

Quote: This seems to be throwing out some information relative to a full Bayes update. Of course, that might be just fine in practice. But with Bayes being as practically feasible as it is for this problem, I'd be really tempted to do it for real. That said, you're the one who's actually getting his hands dirty with an implementation!

Yeah... it confused me that he seemed to be tiptoeing up to using the Bayes implementation that we are all discussing, but then not finishing it up and using the much more specific data. *shrug*

Quote: Original post by InnocuousFox
There are actually two goals (get his flag and protect yours) and any given move may or may not support one or both of those goals.

There are 4 goals.
- Get his flag,
- protect your own (obviously).

The two other important ones:
- stop his flag from reaching the other side (or you lose)
- get your flag to the other side (so you win)

It's why a game tree is important.. or some other block/obstruct/path planning solution. I think the OP uses a Game Tree (Minimax). I also use a game tree (Minimax).

Quote: Original post by InnocuousFox
To top all of this off, you could really use ...

*shrug*

The problem with that is ..

However, you could use ..

A lot of the things you've brought up (like 'if his flag is over there lets go get it') are exactly the type of problem we want to solve. What you haven't done so far is to provide a real plan on how to facilitate this. You seem to keep changing your mind. Normally I wouldn't comment, but you keep poo-pooing the only other person here actually implementing a concrete plan.

Quote: Original post by InnocuousFox

Quote: This seems to be throwing out some information relative to a full Bayes update. Of course, that might be just fine in practice. But with Bayes being as practically feasible as it is for this problem, I'd be really tempted to do it for real. That said, you're the one who's actually getting his hands dirty with an implementation!

Yeah... it confused me that he seemed to be tiptoeing up to using the Bayes implementation that we are all discussing, but then not finishing it up and using the much more specific data. *shrug*

Try re-reading my first post at 10/30/2010 4:59:27 PM. I've been saying the exact same thing throughout this entire thread. No tiptoeing by me. Why throw thinnly veiled insults?

Dave, from your last post it sounds like you could be changing your a mind a bit about the game tree and instead going for using 'certain strategies' or an RTS top-down-command style approach instead.. or did I misread that? Is the game tree no longer Minimax?

Quote: Original post by InnocuousFox
For strategy, you can then work out a shallow-depth min-max

Have you changed your mind about the importance of a player model? Or is the player model now the overall strategy-come-highlevel-RTS-manager? Even so, from what you had said earlier I was under the impression that you didn't think a model of the player was relevant to the game.

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.

You've got so many ideas that I can't keep track anymore. I'm still a little confused about whether or not you think one should employ Monte Carlo or not:

Quote: Original post by InnocuousFox
That said, I don't think Monte Carlo is even necessary

Quote: Original post by InnocuousFox
So, once you have all these percentages, you can seed all sorts of things... MinMax, Markov models, Monte Carlo, etc.

EDITED

Just a thought, but if someone were to use a Bayesian approach they might be able to work out picking the best 'high level strategy' using something like regret minimization or by measuring forecast skill (good 'ol time series analysis).



[Edited by - willh on November 6, 2010 12:26:17 AM]

Quote: Original post by InnocuousFox
Remember that unlike T-T-T, there isn't just "go here or else". There are actually two goals (get his flag and protect yours) and any given move may or may not support one or both of those goals.

Is this a meaningful distinction? In either case, there are gamestates where you win and gamestates where you lose. That's it. Any other reasoning is "just" heuristic (and useful for guiding a search or something, but theoretically not really an issue).

Quote: When you incorporate different strategies, the difference becomes the thresholds of risk you are willing to endure on certain moves.

The clean way to express this, I would think, would be via the evaluation function you use in your truncated search. You would maximize expected utility; a risk-averse player would have a concave utility function, a risk-seeking player would have a convex utility function, and a risk-neutral player would have a linear one.

Quote: To top all of this off, you could really use a planning algorithm as a master strategy for the game. The cost/benefit of the moves/captures would end up being your edge weights for the search.

So, I'd thought we were talking about minimax (i.e., Markov games). Now it sounds like we're talking about dynamic programming (i.e., Markov decision problems). The latter is easier to solve, but requires that you assume that your opponent will behave in a particular, presumably greedy, way. Do we want to do that?

Quote:
However, you could use the planner at a higher level to select between the strategies. For example, "let's take a few pieces with a high-level piece and then see which piece of his pursues us in response. We can counter that piece. Additionally, this helps us narrow down what could possibly be the flag and we can send mid-level pieces after it." This sequence doesn't get down to the actual move level but gives a general, context-specific strategy. This is much like the multi-level command structure used in many RTS games.

I find this approach interesting, but this isn't really something we've talked about at all, so I'm not sure how it'd apply. I'm also not sure how to understand this in a clean way.

Quote: Original post by willh

Quote: Original post by InnocuousFox
Yeah... it confused me that he seemed to be tiptoeing up to using the Bayes implementation that we are all discussing, but then not finishing it up and using the much more specific data. *shrug*

Try re-reading my first post at 10/30/2010 4:59:27 PM. I've been saying the exact same thing throughout this entire thread. No tiptoeing by me. Why throw insults and acusations around?

Hmm, yeah, things got uncomfortably ad-hominem. Anyway, you're clear on how your approach differs from a full Bayes update, and how Bayes can deal with a little more, right? E.g., consider my previous example, but bump the Sergeant up to 2nd Lieutenant and the 2nd Lieutenant to 1st. After your 2nd Lieutenant has killed 5 pieces, you don't know for sure that there is only 1 private remaining; there might be 2 -- he could have killed 4 privates and a sergeant. This is still relevant -- it means that a number of weaker pieces have been removed from the board, and it will affect your 1st Lieutenant's odds in the next fight -- but just counting pieces can't express it; you don't know how many of each are left; there is only a probability for each possible list of piece counts (not that this is something you'd store as-such).

Maybe we should work out Bayes' Rule for this problem. I keep advocating it, and I've worked out the size of the gamestate, but I haven't actually figured out exactly how you'd do the Bayes update here, and that's key to the whole idea... Anybody want to roll up their sleeves? :-)

[Edited by - Emergent on November 6, 2010 12:53:05 AM]

Quote: Original post by Emergent
Anyway, you're clear on how your approach differs from a full Bayes update, and how Bayes can deal with a little more, right? E.g., consider my previous example, but bump the Sergeant up to 2nd Lieutenant and the 2nd Lieutenant to 1st. After your 2nd Lieutenant has killed 5 pieces, you don't know for sure that there is only 1 private remaining; there might be 2 -- he could have killed 4 privates and a sergeant. This is still relevant -- it means that a number of weaker pieces have been removed from the board, and it will affect your 1st Lieutenant's odds in the next fight -- but just counting pieces can't express it; you don't know how many of each are left; there is only a probability for each possible list of piece counts (not that this is something you'd store as-such).

That was very helpful Emergent. The number-of-captures wasn't even a term I had considered and I'm glad you pointed it out.

When this discussion started my concern was using Bayes with a game tree (minmax specifically). I still question how well it would work at planning 5 moves ahead, given the uncertainties. Do you think this concern is justified?

Given my fear of compounded uncertainty when making decisions 5 moves in the future, what I've been attempting is to bring the game back to one of perfect knowledge.. or at least back far enough so that it's possible to beat the human player. :) I want to recover as much factual information as possible.

The example you provided illustrates a weakness in what I've built so far. Now that I know it's there I'll address it-- not to generate probabilities, but so that I can know as fact (when the identity of the 1st lieutentant is revealed) that all 6 privates have been gobbled up. :)

Quote: Original post by Emergent
Maybe we should work out Bayes' Rule for this problem. I keep advocating it, and I've worked out the size of the gamestate, but I haven't actually figured out exactly how you'd do the Bayes update here, and that's key to the whole idea... Anybody want to roll up their sleeves? :-)

You sound like the ideal candidate. :D I need sleep now.. ugh.

EDIT: Just noticed I didn't answer your question. :) Yes, I do agree that there is more information present with the Bayes approach you've described. It's not factual though, and I was only concerned with factual data once I got rolling.

Quote: Original post by willh
EDIT: Just noticed I didn't answer your question. :) Yes, I do agree that there is more information present with the Bayes approach you've described. It's not factual though, and I was only concerned with factual data once I got rolling.

*facepalm*

Quote: Original post by InnocuousFox
*facepalm*

Yeah, a little (it does seem like he's uncomfortable with the idea of applying Bayes' rule, but in honesty it's also enough of a pain in the ass that I haven't sat down to figure it out myself either) but... how do you solve an extensive-form Bayesian game with signaling? In general; forget practical "but it'll take 1000 years" arguments. I mean, I don't know how you'd do it; do you?

I think this is something we'd do well to figure out.

See e.g.
Link 1
Link 2
Link 3
...etc.

I had assumed that things generalized from games of perfect information to games of imperfect information in the same way that MDPs generalize to POMDPs -- especially since solving Markov Games is almost the same as solving MDPs. That's where I'd been going with my "this is the gamestate" post. But now I'm really not so sure that's enough.

I've studied a little game theory, but not enough to help me answer this question.

We should figure this out.

----------------

Unrelated to above, but useful. This is a Chebyshev (not Bayes) estimator for the number of remaining pieces of each type.

Suppose that there were 4 kinds of pieces (it's easy to generalize to the full game, but I only feel like writing 4), with initial counts N1,...,N4.

Now suppose you know that
- pieces of rank 1 have made k1 kills (including equal-value annihilations)
- ...
- pieces of rank 4 have made k4 kills ("")

and you want to estimate the values
- 'n1,' the number of pieces of rank 1 remaining
- ...
- 'n4,' the number of pieces of rank 4 remaining

Well, we know the following:

[These inequalities have been edited.]

1.) The numbers of remaining pieces are within bounds:

0 <= n1 <= N10 <= n2 <= N20 <= n3 <= N30 <= n4 <= N4

2.) At least as many of your enemy's low-rank units have been killed as your low-rank units have gotten kills.

k1 + k2 + k3 + k4 <= (N1 + N2 + N3 + N4) - (n1 + n2 + n3 + n4)k1 + k2 + k3      <= (N1 + N2 + N3     ) - (n1 + n2 + n3     )k1 + k2           <= (N1 + N2          ) - (n1 + n2          )k1                <= (N1               ) - (n1               )

3.) Your high-rank units are responsible for at least the high-rank kills:

k1 + k2 + k3 + k4 >= (N1 + N2 + N3 + N4) - (n1 + n2 + n3 + n4)     k2 + k3 + k4 >= (     N2 + N3 + N4) - (     n2 + n3 + n4)          k3 + k4 >= (          N3 + N4) - (          n3 + n4)               k4 >= (               N4) - (               n4)

This system of inequalities defines a bounded, convex set in R^4. One estimate for how many pieces remain is the "center" of this set; this is called the Chebyshev center. It can be found in the following way.

Letting n=(n1,n2,n3,n4), write the above inequalities and equations as

A n - B <= 0
Aeq n - Beq = 0

for appropriate matrix A and vector B. Then the Chebyshev center is found by adjoining one more scalar variable, 'z', to the system of inequalities and solving

     min zs.t. z >= A n - B     Aeq n - Beq = 0

with the minimization taking place over (z,n).

If the optimal point is (zbar, nbar), then the Chebyshev center is nbar; this gives you an estimate for your opponent's troop numbers.

This minimization problem is a linear program, and can be solved by standard LP solvers.

This is suboptimal compared to Bayes' Rule, but still useful, I think.

[Edited by - Emergent on November 6, 2010 2:29:46 PM]

Oh my. I should have been more clear. It was 4 in the AM when I responded...

I was going to respond fully, but just deleted what I wrote after reconsidering. I'm not comfortable with the way the forum moderator (Dave Mark) is handling this discussion, so I'm going offline with this.

I'm going to keep trucking ahead with what I'm doing. I think we all (minus DM) can agree that I have a resonably solid plan that, despite possibly not being theoretically optimal, can be (and is being) implemented.

You've got a pretty good idea cooking Emergent, and I think you've identified some practical unknowns that need to be worked out. I hope you keep rolling with it. This type of problem isn't really that uncommon in the grand scheme of things. :)

Alvaro, thanks for the Monte Carlo suggestion. If I can stay motivated and find the time I will try that out. Emergent, thank you for contributing so much to this discussion. It's been very informative and I've enjoyed it very much.

If any of you ever do get something running and would like to compare notes, evaluate positions, or have the programs compete, please give me a shout.

Thanks OP for introducing us to this game.

Ciao!

Ohh, and Emergent, don't forget that Spies eat everything except Privates!!! :D And you can win by moving your flag across the board! :D