Про нас Арти Милана Шеана Кайл
Логин 
Пароль  регистрация
забыли пароль?

Обо мне
Обо всем
О Канаде
Иммиграционный процесс
Об играх
Мысли вслух
Творения
Находки

<< ноя >>        << 2009 >>
ВсПнВтСрЧтПтСб
1234567
891011121314
15161718192021
22232425262728
2930     
 
Арти
Об играх: преимущество первого хода и правило "Пирога" 05-Ноя-09, Чтв, 12:17

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

Вначале о преимуществе первого хода. Большинство игр страдают тем, что у первого игрока есть большое преимущество перед вторым игроком. А в некоторых случаях это преимущество становится фатальным для игры - когда для первого игрока находят 100% выигрышную последовательность ходов. В этом случае интерес к игре у серьезных игроков обычно теряется, ибо достаточно заучить эту последовательность, чтобы выигрывать всё время. Ну, или проигрывать - если играешь вторым игроком.

Почему так происходит, что преимущество в игре есть именно у первого игрока? Я попробую объяснить это простым языком, используя доказательство от противного. В качестве примера возьму известную многим игру, которую я упоминал в предыдущей записи, а именно - "Пять в ряд" или "Крестики-нолики на бесконечной доске", которая в оригинале называется Гомоку. Суть игры проста до безобразия: есть клеточное поле, два игрока по-очереди рисуют крестики и нолики в пустых клетках, выигрывает тот, кто ставит "пятёрку" - пять крестиков (или ноликов) в ряд по горизонтали, вертикали или диагонали. Оригинальная Гомоку немного отличается по форме: используются черные и белые камни и ставятся они не в клетки, а на пересечения линий. Сути это не меняет, но я уже привык к оригиналу, поэтому буду говорить не о крестиках-ноликах а о черных и белых камнях. Прежде всего замечу, что чем больше камней своего цвета на доске, тем лучше для игрока. Это, думаю, очевидно: лишние камни своего цвета никак не могут помешать игроку построить "пятёрку", они могут лишь помочь. В этом плане у первого игрока уже есть преимущество: у него на один камень больше, чем у его противника, второму игроку всегда приходится "догонять" первого.

Теперь предположим, что выигрышная последовательность есть именно у второго игрока. Т.е. мы предполагаем, что какой бы ход не сделал первый игрок, второй игрок может ответить определенным ходом, который приведет к его выигрышу. А теперь докажем, что это предположение неверно. Доказывается это очень просто: если такая выигрышная последовательность для второго игрока действительно существует, то первый игрок может её "украсть". Всё, что нужно сделать первому игроку - это сделать какой-то нерелевантный ход где-то на краю доски. Сделать хуже первому игроку такой ход не может, ибо он лишь добавляет камень, а лишний камень помешать не может - о том я уже написал чуть выше. Теперь получается, что первый релевантный ход делает не первый, а второй игрок. Т.е. второй игрок как бы становится первым, а первый - вторым. Если верить нашему предположению, что у второго игрока была выигрышная стратегия, то теперь первый игрок ее "украл". Конечно же, второй игрок может повторить то же самое, т.е. сделать очередной нерелевантный ход и еще раз поменять"очередность". Затем первый игрок опять-таки повторит такой же "манёвр". И так далее: каждый из игроков будет бояться сделать первый релевантный ход, ибо по нашему предположению второй игрок в этом случае воспользуется своей 100% выигрышной стратегией. Так они и будут делать нерелевантные ходы на протяжении всей партии, пока не заполнят всю доску, так и не создав свою "пятёрку", т.е. придут к ничье. Но ведь мы предположили, что у второго игрока есть выигрышная стратегия. А пришли к тому, что первый игрок в этом случае может либо "украсть" эту стратегию и выиграть сам, либо привести партию к ничье. Противоречие! Которое означает, что наше предположение было неверно: у второго игрока не может быть 100%-но выигрышной стратегии. А вот у первого - может. Кроме того, как я уже написал выше, у первого игрока преимущество в том, что у него на один камень больше на доске, чем у второго противника.

Что же происходит с теми играми, в которых у первого игрока есть, если не известная выигрышная стратегия, то неоспоримое преимущество? В некоторые из таких игр продолжают играть на любительском уровне. Например, я знаю, что для упомянутого Гомоку есть 100%-но выигрышная последовательность ходов. Но саму последовательность я совершенно не помню. Так что могу со спокойной совестью продолжать играть . Тем не менее серьёзные игроки в Гомоку не играют, а играют в другие варианты подобных игр - существует целое семейство игр, которое называется N-in-a-row (Эн-в-ряд). О нём я расскажу позже.

Тем не менее, даже для таких игр, как Гомоку, существует одна возможность, которая может перевести их в разряд серьёзных. Собственно, один из самых известных вариантов Гомоку (Рэндзю) как раз использует эту самую возможность для того, чтобы сократить преимущество первого хода. Называется эта возможность "правилом Пирога". Почему так? Истоки лежат в довольно известной задаче о справедливом дележе пирога. Задача заключается в нахождении способа дележа пирога между двумя людьми, при котором обе стороны остаются довольны. Кто не знает этой задачи может поискать решение сам . Кому лень искать - отметьте следующий абзац мышкой:

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


Точно такой же подход используется и в тех играх, для которых найдена, если не 100%-но выигрышная последовательность, то как минимум дебюты (последовательность из первых ходов), которые чисто статистически в большинстве случаев приводит к выигрышу первого игрока. Тут я хочу оговориться: если такие "выигрышные" дебюты и существуют, то это не означает, что нет обратного - откровенно слабых дебютов, приводящих первого игрока к проигрышу. Существует и третий вид дебютов - нейтральные или сбаллансированные. Т.е. такие, после которых статистическая вероятность выигрыша для каждого из игроков близится к 50%. Преимущество первого игрока заключается в том, что он может выбирать. И, естественно, опытный игрок выбирает выигрышные дебюты, а не проигрышные, в результате чего игра становится не интересной для того, кто играет вторым. Вот, чтобы этого не происходило и используется "правило пирога", которое разрешает второму игроку на некотором начальном этапе игры (обычно - после самого первого хода) поменяться местами с первым игроком, т.е. взять себе камни / фигуры его цвета и развернуть доску на 180о. В этом случае первому игроку не выгодно делать слишком хороший первый ход. Не выгодно ему делать и откровенно слабый ход. А выгодно - походить настолько сбаллансированно, насколько хорошо он знает игру. Т.е. так, чтобы первому игроку было все равно, согласиться ли второй игрок с его первым ходом или же решит забрать первый ход себе и поменяться местами. Некоторым подобное правило очень не нравится - в основном тем, кто играет в игры на любительском уровне. В среде же серьёзных игроков и игровых дизайнеров бытует мнение, что "правило пирога" можно добавить к любой игре вообще - испортить им игру сложно, а сделать лучше - элементарно.

На этом я, пожалуй, завершу эту запись .

 
 


Комментарии:


Krasnaja Shapka
  05-Ноя-09, Чтв, 16:35

доказательство мутное какое-то... а если после заполнения 50% доски (мы же всетаки на листочке ограниченном играем) у второго не останется "нерелевантных" ходов? и он, бедный, полюбому выиграет?

да... и еще... давно тебя просил нарыть выигрышную стратегию в пять-в-ряд...

 
Профиль
 


Арти
  05-Ноя-09, Чтв, 16:44

Ну, я же предупредил вначале: "Я попробую объяснить это простым языком". Это не было математическим док-вом, а "док-вом на пальцах".

Насчет выигрышной стратегии: погугли "winning sequence gomoku", "forced winning gomoku" и те де  

 
Профиль
 


BlackChaos
  06-Ноя-09, Птн, 06:55

А я никак понять не мог какого рожна они доску крутят... Теперь буду знать - "пирог делят"!

 
Профиль
 


Ярослав
  26-Дек-09, Сбт, 20:26

 Нашёл интересную вещь: в реверси в вариантах с доской меньше 8х8 существует идеальная стратегия в которой всегда выигрывает второй игрок

http://ru.wikipedia.org/wiki/Реверси#.D0.A0.D0.B5.D0.B2.D0.B5.D1.80.D1.81.D0.B8_n_.C3.97_n


[ 27-12-09, Вск, 03:27:01 Отредактировано: Ярослав ]
 
Профиль
 


Арти
  26-Дек-09, Сбт, 22:28

Реверси - одна из редких игр, в которых выигрывает таки второй игрок. Такие игры существуют, но они составляют меньшинство.

Могу привести пример довольно простой игры, в которой выигрывает второй игрок. Первый игрок называет число от 1 до 10. Второй игрок прибавляет к нему число от 1 до 10, затем тоже самое делает первый игрок и так далее. Выигрывает тот, кто получает 99. Довольно легко убедиться, что у второго игрока есть довольно простая 100% выигрышная стратегия.

 
Профиль
 



Комментарии разрешены только зарегистрированным посетителям! Вход на сайт в правом верхнем углу.

Шармик - Хауз © Арти & Милана & Шеана & Кайл

debug info: total 0.098 sec (4 queries in 0.015 sec)