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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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