Теория игр : задачи

← →
Nic © (2008-06-03 19:59) [0]

Ни у кого случайно нет интересных задач по теории игр? В частности, кооперативные и позиционные игры.

← →
Nic © (2008-06-03 20:00) [1]

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

← →
tesseract © (2008-06-03 20:18) [2]

Я о такой даже не слышал. Позиционная игра № раз это Netstorm :-)

← →
PEAKTOP © (2008-06-03 22:09) [3]

В педивикии поиск John Nash.
http://ru.wikipedia.org/wiki/%D0%9D%D1%8D%D1%88%2C_%D0%94%D0%B6%D0%BE%D0%BD_%D0%A4%D0%BE%D1%80%D0%B1%D1%81
оттудыва по внешним линкам и искать.

← →
Игорь Шевченко © (2008-06-03 22:31) [4]

> позиционные игры.

преферанс это позиционная игра ?

← →
Nic © (2008-06-03 23:12) [5]

> PEAKTOP © (03.06.08 22:09) [3]

Кажется Джон Нэш - это по теме. Спасибо.

> Игорь Шевченко © (03.06.08 22:31) [4]

Не играл в эту игру - поэтому точно не могу сказать позиционная игра это или нет.

← →
ketmar © (2008-06-03 23:27) [6]

>[4] Игорь Шевченко © (2008-06-03 22:31:00)
не совсем. по идее, в позиционной игре нет элемента случайности.

---
Understanding is not required. Only obedience.

← →
Игорь Шевченко © (2008-06-04 00:04) [7]

ketmar © (03.06.08 23:27) [6]

Так после сдачи какая там случайность ?

А калах - позиционная ?

← →
antonn © (2008-06-04 00:13) [8]

> Так после сдачи какая там случайность ?

игра начинается до сдачи :)
судоку - позиционная, шашки :)

← →
Германн © (2008-06-04 00:55) [9]

> Игорь Шевченко © (03.06.08 22:31) [4]
>
>
> > позиционные игры.
>
>
> преферанс это позиционная игра ?
>

Это интересная игра.
Насчёт позиционности не знаю. Впрочем ketmar © уже ответил.

← →
VMcL © (2008-06-04 10:55) [10]

>>PEAKTOP © (03.06.08 22:09) [3]

Ну тогда не только почитать педивикию, но и посмотреть "Игры разума" :-)

← →
tesseract © (2008-06-04 11:17) [11]

> преферанс это позиционная игра ?

Она карточная. Или там можно взятки на поле выкладывать ? Есть симбиоз карточная/ позиционная. Например CCG WarHammer , берсерк.

← →
TUser © (2008-06-04 11:55) [12]

"Программирование игр и головоломок" - есть такая книжка. Поищи в сети, если не найдешь - проси меня по почте или в асе.

← →
Mystic © (2008-06-04 12:02) [13]

Классический труд по теме: фон Нейман, Моргенштейн. "Теория игр и экономическое поведение". Написана понятным языком.

← →
Mystic © (2008-06-04 12:41) [14]

> "Программирование игр и головоломок"
Арсак? Это, конечно, увлекательно, но к такому разделу математики, как "Теория игр" не имеет отношения :)

Вот ссылка на фон Неймана:
http://mu.webest.net/book/Neumann_Theory_of_games.djvu

← →
Ega23 © (2008-06-04 12:45) [15]

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

← →
Mystic © (2008-06-04 12:57) [16]

> Ega23 © (04.06.08 12:45) [15]

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

Просто в конечных играх используется матрица, и игрок выбирает стратегию из дискретного множества (пусть и большого). Примером может служит камень-ножницы-бумага: каждый игрок выбирает одну из трех стратегий до игры, есть матрица, которая указывает победителя. Бесконечные игры часто играют на квадрате (каждый игрок выбирает число от 0 до 1, есть функция, которая f(x,y) которая определяет сколько каждый игрок выиграл.

Насчет начинает и может свести вничью ничего не понял.

← →
Ega23 © (2008-06-04 13:02) [17]

> Насчет начинает и может свести вничью ничего не понял.

Если на каждой итерации просчитывать все возможные последующие ходы и правильно оценивать их, то тот, кто делает первый ход, как минимум не проиграет.
Я сейчас точно не помню, проходил это дело лет 8-9 назад, да и не занимался им больше. Но вот что-то такое проскакивало...

> Если на каждой итерации просчитывать все возможные последующие
> ходы и правильно оценивать их, то тот, кто делает первый
> ход, как минимум не проиграет.

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

А вот в игре гекс такое доказательство вполне строгое: предположим, что начинающая сторона проигрывает. Значит для противника должна существовать оптимальная стратегия. Сделаем случайный ход и будет пользоваться стратегией противника. Выставленный камень никак не может нам повредить, поэтому мы должны выиграть. Противоречие. Но доказательство неконструктивное, потому что не позволяет ответить на вопрос: а как надо играть, чтобы выиграть :)

> Строгого доказательства этого факта не существует.

Да? Ну может быть, я ТИ не на столько ковырял. Просто в обычные крестики-нолики (3х3) - если ты крестиком играешь и первым ходом занимаешь центр - ты как минимум не проиграл (если тупить не будешь).
И, вроде, также со всеми остальными игрищами с конечным числом комбинаций.

>[7] Игорь Шевченко © (2008-06-04 00:04:00)
>Так после сдачи какая там случайность ?
и до, и после — ты не видишь карт на руках партнёров. следовательно, игра не детерминированная. «позиционная игра» — это, например, шашки. где весь «расклад» на лицо, надо только посчитать. в преферансе тоже можно считать (и считаем %-), но тут уже в дело идут всякие вероятности и ты пы.

---
All Your Base Are Belong to Us

> Просто в обычные крестики-нолики (3х3) - если ты крестиком
> играешь и первым ходом занимаешь центр - ты как минимум
> не проиграл (если тупить не будешь).

Это крестики нолики. Тут легко доказать, что начинающий не проигрывает. Но видоизменим правила. Например, поставивший три крестика или нолика в ряд не выигрывает, а проигрывает. Уже ходить стало невыгодно, хотя ничью удержать можно. Или шашки на доске 4x4. Тут уже из трех первых ходов два проигрывают...

Кстати, выше в тексте спутаны понятия игры с полной информацией и позиционной игры. Позиционная игра это игра в которой принятие решений игроками рассматривается как многошаговый (непрырывный) процесс.
http://www.cultinfo.ru/fulltext/1/001/008/090/549.htm
Поэтому преферанс сюда отнести можно.

А вот есть игры с полной информацией, где для соперников отсутствует элемент неопределенности. Сюда преферанс отнести нельзя: игроку неизвестны карты противника. Поэтому решение преферанса в общем случае нужно искать в области смешанных стратегий.

>[21] Mystic © (2008-06-04 16:03:00)
>Кстати, выше в тексте спутаны понятия игры с полной информацией и позиционной
>игры.
угу. моими стараниями. извиняюсь.

---
Understanding is not required. Only obedience.

Вот нашел случайно задачник, понравилась его сугубо практическая направленность. По крайней мере, с парочкой задач я сталкивался в жизни.
http://www.math.nsc.ru/~mathecon/Kokovin/zadachnk.pdf

Огромное всем спасибо! :) Зачёт таки сдал :)

Теория игр : задачи Найти похожие ветки