OT: Game Theory/Statistics
 

I came accross a description of a game some months ago and I'm trying to recall it now. It was a simple game that I believe was used in the discussion of game theory in a programming class, or it might have been during a statistics class. In the game you have two players with some number of tokens, I believe it was 100 each, and some number of boxes, I believe it was 10. Each player could distribute their tokens among the boxes in any proportion they wanted without knowing how many the other player had placed in each box, and you won a box if you put more tokens then the other player in it. The winner of the game was the person who won the most boxes.

Does this sound familier to anyone?

Re: OT: Game Theory/Statistics
 

I think I may have heard of it, but that's a bit simplistic to be an interesting game.

One of two things would happen: you would put ten in each box and break even every game, or put 20 in five boxes each and break even in every game.

Re: OT: Game Theory/Statistics
 

It's simple rules, but the strategy comes in trying to anticipate your opponents moves. If you think he's the type to put ten in each box, then you can put 11 in 9 boxes and 1 in 1 box and win 9 out of 10. But there is no perfect strategy because a style that will beat one type of player might lose to another.

The discussion I read was more from a theoretical game science point of view than an "This is fun, let's play" perspective anyway. The game had a particular name and was used in discussing classifying other games. As in "This game is a "blank-type" game."

Re: OT: Game Theory/Statistics
 

Ah, k. I never worry too much about the names of the games, just the statistics and whatever.

But, yeah...the problem comes from the fact that anybody that knows probability and game theory is going to, eventually, play the guaranteed draw instead of the possible win. Either that or a jerk that nobody will want to play with any more.

I understand the theory behind the game but, without randomness or a sense of what your opponent is doing, "safe" is better than "uncertain."

Of course, I'm probably over analyzing things, as I am often caught doing.

Re: OT: Game Theory/Statistics
 

I think you aren't thinking it completely through actually. You can't really play to a draw in the way that you suggest. Putting ten in each box would only be a draw if your opponent also put ten in each box. And as I suggested before if you think your opponent likely to do that you could easily defeat them.

Re: OT: Game Theory/Statistics
 

People who know probability are a small minority, and game theorists are even rarer.

I'm not convinced that there is a guaranteed draw, but then I managed to fail three different probstat courses in college. http://forum.shrapnelgames.com/image...ies/tongue.gif

Re: OT: Game Theory/Statistics
 

Geoschmo - interesting little game. I don't know the name. Also, I don't think there is a guaranteed draw. Two really good players might get to the point where they are winning half the game and losing half the games.

Re: OT: Game Theory/Statistics
 

It's a simple enough game I'm sure there's a reasonably easy (for a game theorist) to prove optimal strategy, but it's probably one of those situations where the optimum is to randomly pick which of some number of strategies to follow each game. Any given fixed distribution of tokens can be beaten, but if you came up with a pair of distributions A and B such that any way to beat A loses to B and any way to beat B loses to A, flipping a coin to decide which of A and B to use each time would guarantee you a 50% win rate.

Re: OT: Game Theory/Statistics
 

A mixed strategy example: A pair of bombers are attacking, and only one of them carries the nuke. Who does the SAM site target first?

If the SAM site is guaranteed to target the lead bomber, the nuke goes in the trailing bomber. If the nuke goes in the trailing bomber, the SAM site should target the trailing bomber...

For both players, the optimal strategy is 50% chance of the bomb in either plane, so flip a coin.

Re: OT: Game Theory/Statistics
 

There is quite a simple way to show that there is no guaranteed draw.

Put all your tokens down, and pretend I get lucky.

If your biggest pile of tokens is less than 9, I could have put 10 in every box and win 10 to zero.
If your biggest pile of tokens is 9 or more, I could have used the same distribution of tokens as you, except for zero against your biggest box, and +1 against all the other boxes. Meaning I win 9 to 1.

Therefore, no matter how many tokens your largest pile has, there is a possibility of me winning.

Re: OT: Game Theory/Statistics
 

While I agree with your conclusion there are some problems with how you got there. First of all, each player has an 100 tokens and there are ten boxes. Simple division should show you the lowest possible number you can have for your biggest pile is 10, not 9. And that's if yo udivide them evenly. If any pile has less then ten then at least one other pile must have more than ten.

Secondly, each player has an equal numebr of tokens, so it's also impossible to outscore an opponent 10 to zip. The highest possible winning score would be 9 boxes to 1.

Geoschmo

Re: OT: Game Theory/Statistics
 

It is true that you couldn't have a maximum stack smaller than 10 unless you did not use all your tokens.

However, that is irrelevant to the proof.
The point being that if your maximum stack is any natural number at all, a random opponent will sometimes beat you no matter what you do.

In fact, if you allow a negative number of tokens in a box, it still works.

Re: OT: Game Theory/Statistics
 

What happens when both players put the same number of tokens into the same box?

Re: OT: Game Theory/Statistics
 

Then it would be a tie, naturally. Whether both score 1, half or zero points for the box, dosen't affect who wins the game.

PS:
Sorry, hit edit instead of reply

Re: OT: Game Theory/Statistics
 

Basically, it's a guessing game.

To make it a strategy game, there has to be some sort of in-game interaction between the playing pieces. Perhaps change it so you can select three boxes and see what your opponent put in them.

Re: OT: Game Theory/Statistics
 

Or, play it repeatedly, observing the outcomes after each trial, then try to predict the other person's reactions.

Re: OT: Game Theory/Statistics
 

That's still a guessing game. You've simply added a meta strategy game over a series of games.

(You know you've hung out over at The Forge for too long when...)

Re: OT: Game Theory/Statistics
 

True, and a great summary of a lot of Game Theory games. they tend to have both players secretly select a move and then reveal the results. Not necessarily a bad thing -- the opening moves in most RTS and 4X games are done without the other player knowing what you're doing.

But it gets so much attention -- is it because it's easy to do on a chalk board? How would you quantify building a scout to shorten the time until you know something about your opponant's build order?

Secrecy does have merit in war. I once saw an interesting definition of a secret: Any info that, if others found out, would damage your score. Something like that.

Another problem is framing games of perfect knowledge like chess, where you see all and take turns. They are usually drawn as a tree of possibilities, that quickly grows enormous. Too much, really. Maybe that's the problem that needs to be worked on: How to represent a game where the players take turns, and see the pieces, but doesn't draw out to an exploding tree.

Like maybe some sort of greedy current situation heuristic, that only remembers a short list of successful things tried when in the current/similar position. And maybe also a short list of tragic things to definitely not try when in that situation. Isn't that sort of how people do it?

Re: OT: Game Theory/Statistics
 

I dunno, a game that doesn't develop into an exploding tree sounds kind of dull to me.

Lots of things are like that: the interesting stuff is rarely easy to analyze.

Re: OT: Game Theory/Statistics
 

Oh no, I didn't mean that the game would be different. Take chess for example. You can still model the game as an exploding tree if you like, but it's not possible to draw the whole thing out. It's too big.

Now think of another way to model the game of chess (no changes to the game of chess allowed).

Re: OT: Game Theory/Statistics
 

The type of game geo is talking about is called a "blotto" game. Here's a site that talks a bit about it and lists out the results of a game played with a bunch of people...

Colonel Blotto

Space Empires can feel a bit like a blotto game when you are defending multiple wormholes against multiple aggressors.

Re: OT: Game Theory/Statistics
 

does that mean i can do blotto emergency build and get 150 tokens instead of 100? http://forum.shrapnelgames.com/images/smilies/laugh.gif

Re: OT: Game Theory/Statistics
 

Only if you're willing to accept 25 tokens in the rematch. http://forum.shrapnelgames.com/image...ies/tongue.gif

Re: OT: Game Theory/Statistics
 

That's the one Spoon. Thank you. http://forum.shrapnelgames.com/images/smilies/happy.gif

Re: OT: Game Theory/Statistics
 

After reading this, I did a Mathematica notebook on the game. A set of strategies S={ {...}, {...} ...} where each is a list of ten integers, describing a player's troop allotment across ten territories. For a score function, I counted the number of territories that a player has more troops in than the other guy. Comparing each strategy against the set (107 in my set), the result looks like this:

http://home.comcast.net/~anglewyrm/blotto.png

Number of times a player won each amount of territories with their strategy. Some strategies won more territory than others. The total number of territories won, by strategy index number:

http://home.comcast.net/~anglewyrm/blotto2.png

Re: OT: Game Theory/Statistics
 

Edit: Much longer analysis notebook

Re: OT: Game Theory/Statistics
 

So, uh, best strategy?

Re: OT: Game Theory/Statistics
 

erm...uh...hehe...uhh...Fire!Fire!...hehe...

There are two levels of victory to this game, the battles and the war. It looks a lot like elections...

If we count the number of games won, Then then the top four strategies won 50, 49, 47 and 46 games out of 107. The next winners were farther behind, with scores of 42 and below.

Winner(50 games won): {7, 18, 18, 2, 9, 3, 18, 5, 2, 18}
Won 35 games by taking 6 territories, 14 by taking 7, and 1 by taking 8.
Some strong pieces, some secondary, and some weak. Nice unit mix.

2nd place(49 games won): {17, 3, 17, 3, 17, 3, 17, 3, 17, 3}
Won 31 games with a 6-territory lead, 17 with 7, and 1 with 8.
Two piece battler, strong units with escourt.

3rd place(47 games won): {2, 10, 1, 18, 19, 3, 20, 2, 8, 17}
Won 39 games by a score of 6 to 4, and 8 games 7 to 3.
Similar to winner, but also invested in a couple expensive super units.

Honorable mention(46 games won): {17, 0, 17, 0, 17, 0, 16, 0, 17, 16}
Won 46 games 6 to 4.
Tank spammer; got what he wanted, but lack of unit mix cost a few games.

Also, some people chose numbers > 20;
Here is the distribution of numbers chosen (unit strengths):

http://home.comcast.net/~anglewyrm/blotto3.png

This distribution suggests that unit strengths of 19, 9 and 4 would make a good unit mix against that group of opponants. [EDIT]Yep: {19,19,19,19,4,4,4,4,4,4} did very well. Four battlecruisers with heavy fighters as escourt. It pays to know thy enemy.