Resource placement (optimal strategy)

Posted by blackened on Stack Overflow See other posts from Stack Overflow or by blackened
Published on 2011-02-28T23:17:24Z Indexed on 2011/03/01 23:24 UTC
Read the original article Hit count: 205

I know that this is not exactly the right place to ask this question, but maybe a wise guy comes across and has the solution.

I'm trying to write a computer game and I need an algorithm to solve this question:

The game is played between 2 players. Each side has 1.000 dollars. There are three "boxes" and each player writes down the amount of money he is going to place into those boxes. Then these amounts are compared. Whoever placed more money in a box scores 1 point (if draw half point each). Whoever scores more points wins his opponents 1.000 dollars. Example game:

Player A: [500, 500, 0] Player B: [333, 333, 334]

Player A wins because he won Box A and Box B (but lost Box C).

Question: What is the optimal strategy to place the money?

I have more questions to ask (algorithm related, not math related) but I need to know the answer to this one first.

Update (1): After some more research I've learned that these type of problems/games are called Colonel Blotto Games. I did my best and found few (highly technical) documents on the subject. Cutting it short, the problem I have (as described above) is called simple Blotto Game (only three battlefields with symmetric resources). The difficult ones are the ones with, say, 10+ battle fields with non-symmetric resources. All the documents I've read say that the simple Blotto game is easy to solve. The thing is, none of them actually say what that "easy" solution is.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about math