2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 О "ниме в поддавки" и его обобщениях
Сообщение20.12.2018, 11:14 


20/12/18
8
Прошу объяснить/дать ссылки на такой момент теории позиционных игр.

Во многих местах, включая страницу "Функция Шпрага — Гранди" википедии ( https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 0%B4%D0%B8 ) говорится, что "Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход".

По адресу http://e-maxx.ru/algo/sprague_grundy#25 (страница "Теория Шпрага-Гранди. Ним", пункт "Ним в поддавки") утверждается: "... существует также "ним в поддавки" ("misère nim") — когда игрок, совершивший последний ход, проигрывает (а не выигрывает) ... Решение такого нима удивительно просто: будем действовать так же, как и в обычном ниме (т.е. посчитаем XOR-сумму всех размеров кучек, и если она равна нулю, то мы проиграем при любой стратегии, а иначе — выиграем, найдя переход в позицию с нулевым значением Шпрага-Гранди). Но есть одно исключение: если размеры всех кучек равны единице, то выигрышность/проигрышность меняются местами по сравнению с обычным нимом."

Есть ли какие-то известные правила, определяющие, когда именно это приём обобщается на другие игры, в которых используется теория Шпрага-Гранди? Верно ли, что практически никогда, потому что практически во всех играх возможны ходы, увеличивающие значение SG отдельной подигры, и именно это ломает доказательство для "Нима в поддавки"?

 Профиль  
                  
 
 Re: О "ниме в поддавки" и его обобщениях
Сообщение20.12.2018, 12:49 


17/04/18
143
обобщение буквально такое же, ну типа просто по определению SG функции, увеличивающие ходы ничего не порят, так как на любой увеличивающий ход можно ответить уменьшающим ходом и вернуть игру в прежнее состояние

 Профиль  
                  
 
 Re: О "ниме в поддавки" и его обобщениях
Сообщение20.12.2018, 14:53 


20/12/18
8
Я, конечно, могу ошибаться (потому и спрашиваю), но мне не очевидно, что "возможность возвращаться" в лемме о ниме с увеличениями нигде не вступает в противоречие с утверждением "мы в самом деле всегда можем сделать такой ход, чтобы осталось нечётное число кучек размера 1, т.е. приведём соперника к поражению".

А если переходы-возвраты возможны, но не с той чётностью, которая нам нужна?

И разве единственная игра $g_1$ с $SG(g_1)=1$ не может распасться в сумму двух игр $g_{11}$, $g_{12}$, таких, что $SG(g_{11})=SG(g_{12})=2$ ? Получаем, что $SG(g_1)\oplus z = 1\oplus 1 = 0$, $SG(g_{11})\oplus SG(g_{12})\oplus z = 2\oplus 2\oplus 0 = 0$, и это что -- ход из проигрышной в проигрышную? Откуда именно следует, что теперь это нормально? Насколько понимаю, для именно нима, где нет увеличений, такого контрпримера (или подобия контрпримера) не_возникает...

К тому же, если приём обобщается и Шпрага-Гранди с этим приёмом можно использовать для любой игры, где тот, кому некуда ходить, выигрывает -- почему практически во всех источниках рассматривается только случай, когда тот, кому некуда ходить, проигрывает?

 Профиль  
                  
 
 Re: О "ниме в поддавки" и его обобщениях
Сообщение20.12.2018, 19:26 


20/12/18
8
Кстати, https://habr.com/post/91272/ заканчивается фразой "Не существует общего подхода к мизерным играм, иногда они сводятся к играм с нормальным окончанием, иногда нет, тут просто нужна сообразительность и немного фантазии)". Не до конца уверен в надёжности источника, но всё же явную ересь там почти всегда жёстко минусуют. Так что начальный вопрос "Есть ли какие-то известные правила, определяющие, когда именно это приём обобщается на другие игры, в которых используется теория Шпрага-Гранди?" модифицируется к виду "Известны ли хоть какие-то правила, позволяющие хотя бы в некоторых случаях определять, обобщается ли этот приём на нужную игру?". А недоверие к предыдущему оратору дополнительно возрастает.

 Профиль  
                  
 
 Re: О "ниме в поддавки" и его обобщениях
Сообщение23.07.2019, 08:17 


20/12/18
8
Прошу прощения, но меня опять интересует этот вопрос, так что прошу по возможности ответить.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group