Задачка по теории игр.

[Yuri Gendelman]

antoshka1303 писал(а):

Значит так.
У игрока 1 имеется три карты. Он может пометить либо ни одной карты, либо одну карту, либо две карты, либо три карты.(ННН,либо ННМ,либо НММ,либо МММ),где Н-немеченая карта, М-меченая карта.
У игрока 2 имеется три карты. Он может пометить либо ни одной карты, либо одну карту, либо две карты, либо три карты.(ННН,либо ННМ, либо НММ,либо МММ)
...

Вот-вот-вот, пока все правильно... Ну и?

antoshka1303 писал(а):

такий образом, получается 64 комбинации в тасованой колоде.

Э-эх!
Кстати, а сколько всего колод в игре?

Насчет учебника - сейчас никаким не пользуюсь. Впервые я познакомился с теорией игр классе в 8-м по книге Вильямса "Совершенный стратег". Каким пользовался в университете - уже не помню.

Добавлено спустя 31 минуту 22 секунды:

antoshka1303 писал(а):

У меня Петросян,Зенкевич,Семина Теория игр.

Посмотрел сейчас этот учебник. Мне показалось, что он не очень предназначен для первоначального и самостоятельного изучения теории игр. Посмотрите внимательно примеры на страницах 10-13. Особенно пример 1 (стр.10-11).

[antoshka1303]

Yuri Gendelman писал(а):

Вот-вот-вот, пока все правильно... Ну и?

В игре, таким образом, 2 колоды. В сумме 6 карт.

Игроки наугад выбирают из своей колоды карты по очереди,могут выпасть служуюции комбинации карт.
ММ
МН
НМ
НН, где в первой позиции стоит карта игрока 1, а во второй позиции стоит карта игрока 2.

[Macavity]

antoshka1303 писал(а):

Yuri Gendelman писал(а):

Вот-вот-вот, пока все правильно... Ну и?

В игре, таким образом, 2 колоды. В сумме 6 карт.

Игроки наугад выбирают из своей колоды карты по очереди,могут выпасть служуюции комбинации карт.
ММ
МН
НМ
НН, где в первой позиции стоит карта игрока 1, а во второй позиции стоит карта игрока 2.

В принципе, стратегия начинается и заканчивается там, где игроки могут влиять на ситуацию. Вытащить меченую или немеченую карту, это тоже, конечно, стратегия, но стратегия для шулера.

Но, я надеюсь, у Вас честные игроки. И значит, если стратегии нет при вытаскивании карты, значит она была где-то раньше.
Если хорошо подумаете, то поймете, что стратегия в том, сколько карт пометить. Это то, что зависит полностью от игрока. Вот отсюда и надо плясать.

С другой стороны, ситуация в выборе стратегии абсолютно симметричная для обоих игроков. Это означает, что при правильном выборе стратегии - шиш кто-то из них чего то выиграет. То есть стратегия для обоих игроков должна быть одинаковая. Другое дело, является ли эта стратегия чистая или смешанная. Надо ли им использовать датчик случайных чисел при выборе количества карт, которые надо пометить... А вот распределение вероятностей по количеству карт Вам и надо посчитать...

[незваный гость]

Macavity писал(а):

С другой стороны, ситуация в выборе стратегии абсолютно симметричная для обоих игроков. Это означает, что при правильном выборе стратегии - шиш кто-то из них чего то выиграет.

А стратегии разные бывают. Например, максимальный выигрыш, или минимальный проигрыш. Кроме того, играя оптимально, вы получаете нулевой результат только в том случае, если партнер играет оптимально. А иначе можно и наиграть кое-что.

[Yuri Gendelman]

незваный гость писал(а):

А стратегии разные бывают. Например, максимальный выигрыш, или минимальный проигрыш.

С точки зрения теории матричных игр это одно и то же. Проигрыш - это выигрыш со знаком минус.

[незваный гость]

Yuri Gendelman писал(а):

С точки зрения теории матричных игр это одно и то же. Проигрыш - это выигрыш со знаком минус.

Только вот оптимальные стратегии могут оказаться разными.

[Yuri Gendelman]

незваный гость писал(а):

Только вот оптимальные стратегии могут оказаться разными.

В матричной игре элемент матрицы игры $m_{i,j}$ задает выигрыш 1-го игрока и одновременно проигрыш 2-го игрока при выборе соответственно стратегий i и j. Отрицательное значение трактуется как проигрыш 1-го игрока и соответственно выигрыш 2-го игрока. Критерий один - минимакс. Тут просто нет места разным стратегиям.
Я здесь говорю только об антагонистических играх 2х игроков. Других игр наш главный герой пока не знает.

[незваный гость]

Может я чего-то не понимаю, но мне кажется, что стратегия обеспечивающая наименьший проигрыш 1-го игрока может отличаться от стратегии, дающей наибольший выигрыш. Пример, A играет орел-решка и кидает монетку. Если А выбрал орел и угадал, он выиграл 2, если нет — проиграл 1. Если А выбрал решку и угадал, он выиграл 10, не угадал — проиграл 5. Очевидно, что стратегия максимизирующая выигрыш — выбирать решку, а минимизирующая (максимальный) проигрыш — выбирать орла.

Не скажу, чтобы это было несводимо одно к другому. Разумеется, сводимо.

[antoshka1303]

я кажется что-то начинаю понимать:). Пусть i-я стратегия игрока 1 это количество помеченных карт в своей колоде(0<=число помеченных карт <= n), пусть j-я стратегия игрока 2 это количество помеченных карт в своей колоде(0<=число помеченных карт <= n).

Закодируем меченую карту единицей, немеченую карту нулем. На стратегиях игрока хочу постоить функцию, выбора из колоды карты. Функция принимает 2 значения нуль(немеченая карта), единица(меченная карта)... на основании нее строим матрицу игры.

[незваный гость]

Почти правильно. Стратегия в данном случае — это, действительно, пометка определенного количества карт. Отсюда, кстати вывод — введение посредников никак не отражается на стратегии игроков, поскольку посредники появляются только тогда, когда все решения уже приняты.

Дальше наступает игра — чисто стохастическая — с мечеными, но не шулерскими, колодами.

[Yuri Gendelman]

antoshka1303 писал(а):

я кажется что-то начинаю понимать:)

Да Со стратегиями Вы разобрались. У каждого игрока - по (n+1) стратегии.

Теперь надо построить матрицу игры. Выбор карт из колод - процесс случайный. Поэтому для каждой пары стратегий игроков нужно оценить матожидание выигрыша.
Примеры для случая 10 карт:
- 1-й пометил 0, 2-й пометил 10: 2-й всегда выигрывает, цена игры = -2
- 1-й пометил 10, 2-й пометил 10: всегда ничья, цена игры = 0
- 1-й пометил 9, 2-й пометил 10: 1-й выигрывает в 9 случаях из 10, 2-й - в 1 из 10, цена игры =

Добавлено спустя 32 минуты 35 секунд:

незваный гость писал(а):

:evil:
Может я чего-то не понимаю, но мне кажется, что стратегия обеспечивающая наименьший проигрыш 1-го игрока может отличаться от стратегии, дающей наибольший выигрыш. Пример, A играет орел-решка и кидает монетку. Если А выбрал орел и угадал, он выиграл 2, если нет — проиграл 1. Если А выбрал решку и угадал, он выиграл 10, не угадал — проиграл 5. Очевидно, что стратегия максимизирующая выигрыш — выбирать решку, а минимизирующая (максимальный) проигрыш — выбирать орла.

Игра здесь есть, но нет теоретико-игровой задачи. Матожидание выигрыша одинокого игрока A при выборе орла равно +0.5, а при выборе решки соответственно +2.5. То, о чем Вы говорите - это стратегии при одной попытке.
А вот если бы вместо подбрасывания монеты, был бы выбор игрока Б, то получилась бы игра 2х2 без седловой точки. Стратегии соответственно [5/6, 1/6] и [11/18, 7/18], цена игры 5/6.

[незваный гость]

Yuri Gendelman писал(а):

А вот если бы вместо подбрасывания монеты, был бы выбор игрока Б, то получилась бы игра 2х2 без седловой точки. Стратегии соответственно [5/6, 1/6] и [11/18, 7/18], цена игры 5/6.

Хорошо, поясните мне этот случай. Почему А не имеет право минимизировать свой максимальный проигрыш? Он при этом не максимизирует выигрыш, но не все же сразу? Консервативен ли он, жаден, или просто нет денег, а игру навязывают -- не важно. Скажем ну не может он себе позволить проиграть 5. И всегда выбирает невыгодный орел. Если В это знает, то А всегда проиграет. Но даже в этом случае он не проиграет 5.

Мне кажется, такие вопросы тоже изучаются теорией игр.

[Yuri Gendelman]

незваный гость писал(а):

Хорошо, поясните мне этот случай. Почему А не имеет право минимизировать свой максимальный проигрыш? Он при этом не максимизирует выигрыш, но не все же сразу? Консервативен ли он, жаден, или просто нет денег, а игру навязывают -- не важно. Скажем ну не может он себе позволить проиграть 5. И всегда выбирает невыгодный орел. Если В это знает, то А всегда проиграет. Но даже в этом случае он не проиграет 5.
Мне кажется, такие вопросы тоже изучаются теорией игр.

Я никогда не утверждал, что задача в Вашей постановке не имеет смысла. Я только говорил, что это не задача матричной теории антагонистических игр, хотя и выглядит похоже, даже матрицу можно составить.
Не всякая игра имеет отношение к теории игр, не всякая задача, решаемая теорией игр использует игры в качестве модели. Например, теория дифференциальных игр используется для описания алгоритмов целеуказания.
Помните простейшую игру в кости, которую я предложил Антошке в качестве провокационного вопроса? Тоже ведь игра. Вспомните игры, анализируя которые Паскаль создал теорию, но не игр, а вероятностей.

[Macavity]

незваный гость писал(а):

:evil:

Macavity писал(а):

С другой стороны, ситуация в выборе стратегии абсолютно симметричная для обоих игроков. Это означает, что при правильном выборе стратегии - шиш кто-то из них чего то выиграет.

А стратегии разные бывают. Например, максимальный выигрыш, или минимальный проигрыш. Кроме того, играя оптимально, вы получаете нулевой результат только в том случае, если партнер играет оптимально. А иначе можно и наиграть кое-что.

Ну речь ведь не идет о том, что мы идем в казино или после трудного рабочего дня играем по маленькой в покер. Если бы такое было вряд ли бы дело закончилось боевой ничьей.

Это теория игр и в ней именно и рассматривается (в первую очередь), какие у игроков оптимальные стратегии и мат. ожидание выигрыша каждого при их применении. Так вот ввиду симметричности игры (получится симметричная матрица) стратегии игроков должны быть одинаковы и мат. ожидание выигрыша для каждого равно 0 (если они закладывают по рублю в каждой игре, что похоже и следует из условия) или равны одинаковому числу если ничего не закладывают.

Другое дело, что стратегия может быть чистая, например, каждый игрок метит только одну карту. Или смешанная, кажый игрок не метит карт с вероятностью 0.5, метит одну карту с вероятностью 0.2 и т.д. и .п. (в сумме 1.0)...

Добавлено спустя 13 минут 11 секунд:

незваный гость писал(а):

:evil:
Может я чего-то не понимаю, но мне кажется, что стратегия обеспечивающая наименьший проигрыш 1-го игрока может отличаться от стратегии, дающей наибольший выигрыш. Пример, A играет орел-решка и кидает монетку. Если А выбрал орел и угадал, он выиграл 2, если нет — проиграл 1. Если А выбрал решку и угадал, он выиграл 10, не угадал — проиграл 5. Очевидно, что стратегия максимизирующая выигрыш — выбирать решку, а минимизирующая (максимальный) проигрыш — выбирать орла.

Не скажу, чтобы это было несводимо одно к другому. Разумеется, сводимо.

К сожалению несводимо. В Вашем случае есть разница между А и Б.
Но если Вы точно такие условия дадите для Б (что имеет место в нашей задаче), то сводимо.
Заметьте, что в нашей задаче условия для обоих игроков одинаковы.

[незваный гость]

Macavity писал(а):

В Вашем случае есть разница между А и Б.

А что, теория игр изучает только симметричные игры? Под сводимостью я имел в виду не столько переход к данной задаче, сколько переход от проигрыша к выигрышу.

~~~

По-моему, дуэль на троих является одной из классичесих задач теории игр: A стреляет в B, B стреляет в C, С стреляет в A. Вероятность успешного выстрела A меньше вероятности B, которая, в свою очередь, меньше C. Правильная стратегия для A — стрелять в воздух.

Еще один пример: шахматы (игры с полной информацией). Тоже же изучаются.