Размещение ресурсов (оптимальная стратегия)

Я знаю, что это не совсем то место, чтобы задавать этот вопрос, но, возможно, кто-то умный парень найдет решение.

Я пытаюсь написать компьютерную игру, и мне нужен алгоритм для решения этого вопроса:

Игра ведется между двумя игроками. У каждой стороны по 1.000 долларов. Есть три «ящика», и каждый игрок записывает в них сумму денег, которую он собирается положить. Затем эти суммы сравниваются. Тот, кто положил больше денег в коробку, получает 1 очко (если каждый тянет по пол-очка). Тот, кто наберет больше очков, выигрывает у своего оппонента 1.000 долларов. Пример игры:

Игрок A: [500, 500, 0] Игрок B: [333, 333, 334]

Игрок A выигрывает, потому что он выиграл бокс A и бокс B (но проиграл бокс C).

Вопрос: Какова оптимальная стратегия размещения денег?

I есть еще вопросы (связанные с алгоритмом, а не с математикой), но сначала мне нужно знать ответ на этот.

Обновление (1): После дополнительных исследований я узнал, что проблемы такого типа / игры называются Colonel Blotto Games . Я приложил все усилия и нашел несколько (очень технических) документов по этому вопросу. Короче говоря, моя проблема (описанная выше) называется простой игрой в блотто (всего три поля битвы с симметричными ресурсами). Сложные - это, скажем, 10+ полей сражений с несимметричными ресурсами. Все документы, которые я читал, говорят, что простую игру Blotto легко решить. Дело в том, никто из них на самом деле не говорит, что это за "простое" решение.

Обновление (2): Я написал небольшой файл ActionScript, чтобы продемонстрировать стратегию в статье, упомянутой Томом Сиргедасом. Вы можете протестировать его на megaswf . Инструкции: Щелкните точку внутри треугольника. Красная область представляет выигрышные случаи. Синяя область соответствует проигрышным случаям, крошечные беловатые линии - ничьей.

7
задан blackened 16 March 2011 в 18:04
поделиться