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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 16.05.2008, 15:46
Новичок

Отправить личное сообщение для OwnYou Посмотреть профиль Найти все сообщения от OwnYou
 
Регистрация: 07.05.2008
Адрес: Ярославль
Сообщений: 9

Я рассмотрел Гранди-функцию для этой игры и так получается что она имеет значения только 0 и 1 на любых наборах т.е. заранее известно какой игрок выигрывает... вообще не понимаю как такое может быть... я туплю наверное... подскажите пожалуйста
  #12  
Старый 16.05.2008, 18:48
гость

 
Сообщений: n/a

Ну а что ты ожидал увидеть?

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

Например, шашки - одна из таких игр. И недавно выяснилось что при оптимальной игре обоих сторон будет ничья.
  #13  
Старый 16.05.2008, 20:05
Новичок

Отправить личное сообщение для OwnYou Посмотреть профиль Найти все сообщения от OwnYou
 
Регистрация: 07.05.2008
Адрес: Ярославль
Сообщений: 9

HELP!!!
всё правильно, здесь Take-And-Brake игра, которая заканчивается победой одного игрока... НО, я не об этом.
По условию игры: (1) - это терминальная позиция следовательно Гранди функция G(1)=0 по определению. Гранди функция всех позиций ведущих в терминальную = 1 т.е. G(2)=1. Дальше рекурсивно вычисляем G по правилу:
G(n) = mex{G(n-1,1), G(n-2,2), ... , G(1,n-1)}
а сумма игр т.е. G(X1,X2,..,Xn)=G(X1) xor G(X2) xor ... xor G(Xn) по теореме Sprague-Grandy.
и получается такая штука, что G(2n-1)=0 , а G(2n)=1 при любом натуральном n.
у меня напрашивается из этого такое предположение, что я не могу повлиять на ход игры... т.е. заранее знаю кто выиграет или проиграет.

к примеру если добавить ещё одну терминальную позицию, например (2) то такой ситуации уже не будет и можно влиять на ход игры. Что с этой игрой не так... HELP... где ошибся или всё так?????

G(X1,...,Xn)=0 Это P-позиция, в которой выигрывает игрок сделавший предыдущий ход
G(X1,...,Xn)!=0 Это N-позиция , в которой выигрывает игрок делающий следующий ход

т.е. если мы будем находиться в P-позиции, надо сделать ход снова в P-позицию.
рассмотрим игру (9,8,6) которая будет достаточно большой. G(9,8,6)= 0 xor 1 xor 1 = 0 --> это P-позиция(проигрышная)

G(9,8,6) ходим в первой куче:

G(8,1,8,6) = 1 xor 0 xor 1 xor 1 = 1
G(7,2,8,6) = 0 xor 1 xor 1 xor 1 = 1
G(6,3,8,6) = 1 xor 0 xor 1 xor 1 = 1
G(5,4,8,6) = 0 xor 1 xor 1 xor 1 = 1

G(9,8,6) ходим во второй куче:

G(9,1,7,6) = 0 xor 0 xor 0 xor 1 = 1
G(9,2,6,6) = 0 xor 1 xor 1 xor 1 = 1
G(9,3,5,6) = 0 xor 0 xor 0 xor 1 = 1
G(9,4,4,6) = 0 xor 1 xor 1 xor 1 = 1

G(9,8,6) ходим в третей куче:

G(9,8,1,5) = 0 xor 1 xor 0 xor 0 = 1
G(9,8,2,4) = 0 xor 1 xor 1 xor 1 = 1
G(9,8,3,3) = 0 xor 1 xor 0 xor 0 = 1

Никак нельзя сделать ход в P-позицию.... тут наверно даже доказать можно...

Последний раз редактировалось OwnYou, 16.05.2008 в 20:38. Причина: Чтобы было понятней...
  #14  
Старый 17.05.2008, 13:36
гость

 
Сообщений: n/a

Я немного подумал, и нашел более элементарное объяснение: ваша игра всегда заканчивается за (a-1) + (b-1) + (c-1) ходов, независимо от действий игрока.

Представьте себе что кучки - это полоски бумаги состоящие из n клеточек в ряд, и за один ход разрешается разрезать на две любую из имеющихся бумажек, на длине от края кратной длине клеточки. Очевидно в игре изначально можно сделать a-1 + b-1 + c-1 разрезов, и игра закончится только в момент когда все эти разрезы будут сделаны, а порядок их неважен. (Более формальное доказательство - рассмотреть величину сумма (размер кучки - 1) по всем кучкам, и доказать что она уменьшается на 1 за каждый шаг)
  #15  
Старый 18.05.2008, 08:40
Новичок

Отправить личное сообщение для OwnYou Посмотреть профиль Найти все сообщения от OwnYou
 
Регистрация: 07.05.2008
Адрес: Ярославль
Сообщений: 9

Спасибо! вот теперь я на 99% уверен. пойду теперь на препода наезжать =)
__________________
And Things You Own - Own You
  #16  
Старый 14.03.2011, 19:44
Новичок

Отправить личное сообщение для Templar Посмотреть профиль Найти все сообщения от Templar
 
Регистрация: 29.01.2011
Сообщений: 3

Это и есть классическая игра "Ним";
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
исходник игры домино на С++ Stranger Реализация, исходники, языки 2 01.05.2009 16:07