Форум умных людей

    Двое играют в детерминированную игру с полной информацией. Каждая игра заканчивается победой одного из игроков (для другого игрока это поражение). Возможна ли такая ситуация, что ни у одного из игроков нет выигрышной стратегии?

как ето?:
В русскуЙУ рулетку играЙУт например.

Если игроки могут неограниченно оттягивать свой конец :)

начинаЙУщий имеет приемущество!

  Каждая игра заканчивается! Каждая игра заканчивается победой одного из игроков (для другого игрока это поражение).

  Из википедии.
   Игра с полной информацией — термин теории игр, обозначающий логическую игру, в которой для соперников отсутствует элемент неопределённости.

Не вполне строго, но практически можно считать, что игра является игрой с полной информацией, если:

    * игроки воздействуют на игровую ситуацию дискретными действиями — ходами, порядок ходов определён правилами и не зависит от таких параметров, как скорость реакции игроков (то есть очередной ход делает тот, кто должен его сделать по правилам, а не тот, кто первым догадался или успел его сделать);
    * в любой момент игры все игроки имеют полную информацию о состоянии игры, то есть о позиции и всех возможных ходах любого из игроков.

вариант - Шашки "Задний ход"

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

  :D  :-[

По определению невозможна.

Да уж, конец-то не резиновый.

Ничья есть

А как же условие?

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

они играют в "забрось мяч в корзину"

Если игра детерминирована, то нет. Если нет, то да  :eat:

Вики пишет, что по-любому детерминирована.

В таком случае, Вики не права  :-\

  Уточнение. Игра детерминирована. Но игра может длиться бесконечное (счетное) число шагов. Но каждая игра  заканчивается победой одного из игроков (для другого игрока это поражение).
 Тут есть некоторая тонкость, но все можно корректно определить.

Игра, конечно, может быть настолько сложной, что практически никто не рассчитает выигрышную стратегию. Но в вакуумно-сферическом случае, если она детерминирована, значит ее процесс предрешен  :yesgirl:

машхаты

Ну, там возможна ничья.

Впрочем, шашки уже, по-моему, посчитали - скоро наступит и черед шахмат.

игра в города

Не поверите, но стратегия там тоже всегда есть :)

   Я, к сожалению, пока не нашел авторитетного источника с определением детерминированной игры. Игра, которая не зависит от случая. Но важно, что  игра может длится бесконечное количество шагов для каждой партии.

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

ввв, а в шахматах, к примеру, у кого выигрышная стратегия?
зы: просто интересно..

Ну я и говорю, про бесконечно оттягиваемый конец.

Конечно невозможна, если она конечна и детерминирована - ввиду конечности состояний и дерева возможностей и если ничья не предусмотрена правилами.
Это просто следует из определения.
Мне непонятно, в чём сыр-бор.
Другое дело, что можно придумать достаточно примитивную бесконечную детерминированную игру с полной информацией.

   Для любой мощности существуют игры, которые длятся именно эту мощность ходов. Задача состоит в следующем. Можно ли классический результат для конечных детерминированных игр с полной информацией распространить на случай бесконечных детерминированных игр с полной информацией? Или нельзя, так как он перестает быть верным?

Бесконечные игры не обязательно заканчиваются победой или поражением.

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

Варианты:
1. Победа 1-го
2. Поражение 1-го
3. Бесконечное продолжение.

   Вариантов всего 2: 1)победа 1-го, 2) победа 2-го.

Значит игра не бесконечна.

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

например, игроки по очереди выписывают цифры десятичного числа (после запятой)
первый выигрывает, если число рациональное, второй - если иррациональное
выигрышной стратегии нет ни у одного

  У второго есть выигрышная стратегия.

значит все-таки детерминирована, т.е. стратегия есть)

А когда определять?

Или я тупой или выигрывает всегда первый?

и какая же?

Мне тоже кажется, первый в любой момент игры выигрывает.

  Тут есть тонкость. Но все можно корректно определить. Правда, требуется некоторая конструкция. Чтобы не углубляться дальше в дебри, опишем ситуацию по-другому. Грубо говоря, стратегией i-го игрока  называется функция, которая определена на множестве всевозможных "позиций" (начальных кусочков партии), когда ход принадлежит i-му игроку в множество дальнейших возможных ходов (как i-й игрок может продолжить партию). Т.е. стратегия описывает как i-й игрок будет ходить в каждой конкретной ситуации. Очевидно, что для двух выбранных стратегий 1-го и 2-го игроков игра восстанавливается однозначно. И, естественно, результат партии. Может ли быть так, что ни у одного из игроков нет выигрышной стратегии.

Я спрашивал про то, в какой момент определять, кто победил в игре Дискоеда.

А что такое стратегия я знаю)

  Выигрышная стратегия для 2-го игрока. Он действует независимо от действий первого. Его последовательность ходов: 1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,... . Число будет иррациональным. Предположим противное. У рационального числа, начиная с некоторого места вправо будет повторяться один и тот же набор цифр. У периода есть какая-то длина. Но это противоречит последовательности 2-го игрока.

  После того, как мы получили результативное число.

А подходит такой вариант:
Нужно загадать число 0 или 1.
Если числа у игроков совпали - выигрывает первый. Если нет - второй.
Или это не с полной информацией?

Конечных иррациональных чисел не существует.
Поэтому пока игра продолжается, первый - победитель.

+1

пока игра продолжается, победителя нет.
Как тол'ко игра завершилас' (на любом конечном ходе) - выиграл 1-ый

Ну я это и имел в виду ;)

  Эта игра не завершается на конечном шаге. Если же эта игра по определению длится лишь 10^100 ходов, то любая стратегия первого игрока является выигрышной.

10^100 или 1 ход разницы не вижу.

Т.е. эта игра и ест' решение вашей задачи / вопроса?

Тогда зачем так изощрённо? Пуст' будет так:
Игроки ставят по очереди цыфры от 0 до 9
Если на поле появляется 1 выигрывает первый.

У первого ест' стратегия (повер'те )
Игра может продолжаться бесконечно долго.
(эта игра аналогична предыдущей )

Пардон:
Выигрышная стратегия это как?:
1. Последовательность действий игрока ИЗНАЧАЛЬНО (начиная с 1-ого хода) приводящая к победе с БОЛЬШЕЙ шей вероятностью (чем к проигрышу )

2. Последовательность действий игрока начиная с К-ого хода приводящая к победе с БОЛЬШЕЙ вероятностью (чем к проигрышу )

3. Последовательность' действий игрока ИЗНАЧАЛЬНО (начиная с 1-ого хода) приводящая к 100% ПОБЕДЕ игрока

4. Последовательность' действий игрока начиная с К-ого хода приводящая к приводящая к 100% ПОБЕДЕ игрока

Последовательность действий в ответ на ЛЮБОЕ действие соперника, приводящая к 100% победе игрока.

   Стратегия S называется выигрышной  для i-го игрока, если для любой стратегии T 3-i-игрока i-ый игрок выигрывает, если он руководствуется S, а его соперник ---  T.

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

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

   Это не детерминированная игра.

   Э   Это игра не является  детерминированой игрой с полной информацией.

     Ошибся. Эта игра не является детерминированной игрой с полной информацией.

Не вполне строго, но практически можно считать, что игра является игрой с полной информацией, если:

    * игроки воздействуют на игровую ситуацию дискретными действиями — ходами, порядок ходов определён правилами и не зависит от таких параметров, как скорость реакции игроков (то есть очередной ход делает тот, кто должен его сделать по правилам, а не тот, кто первым догадался или успел его сделать);
    * в любой момент игры все игроки имеют полную информацию о состоянии игры, то есть о позиции и всех возможных ходах любого из игроков.

Разве не подходит?

второй игрок не видит цифру первого игрока
они пишут одновременно, потом показывают

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

А в условии не сказано, что она должна быть детерминированной.

Сказано в дополнении к условию  :eat:

  В момент хода воздействует на игру только один игрок, а не два или больше.

Ребята, вы бы лучше вечным двигателем занялись...

   Это можно трактовать, что такой игры не существует?

если кто-либо выигрывает, значит он или его соперник делает последний ход 100% приводящий к победе первого либо второго.
А следовательно на етом, либо предыдущем ходе (в общем, когда ходит победитель ) выигрышная стратегия существует.

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

Каждый игрок знает все варианты, и знает что противник знает все варианты. А отсюда выходит, что каждый будет знать заранее, как будет ходить другой. И знать результат игры.

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

Другой вопрос, может ли реально существовать игра с такими условиями.

крестики-нолики

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

Походу, такой игры (как в условии) быт' не может.

"осенило"

игра: нажми на кнопку

ходы по очереди, за ход можно нажать на кнопку. Кто первый нажмет на кнопку - выиграл.

1) полная информация
2) детерминирована
3) не может быть ничьи
4) у второго игрока нету выигрышной стратегии

^^

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

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

Например, игра - камень-ножницы-бумага

Не с полной информацией

А бесконечные крестики-нолики катят? (По 5 в ряд)

Однажды с другом изрисовали полторы страницы :)

  Каждая партия должна быть результативной. Даже если она длится бесконечно долго. Правильный ответ  Показать скрытый текст

А я дал неправильный ответ?

   Скоро мы это узнаем.

  Ответ. Показать скрытый текст

Немного запутано...