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

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

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

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

Модификация игры Ним
Помогите пожалуйста подсказать способ решения. суть такова: Даны 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Играют человек и компьютер. Нужно придумывать выигрышную стратегию для компьютера. Долго думал, так не до чего и не дошёл . реализация у меня будет на С.
  #2  
Старый 10.05.2008, 12:03
гость

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

Нужно пользоваться теоремой Sprague-Grundy.

Если не ошибаюсь, функция Гранди для одной кучки размера n равна 1 если n четно, и 0 если нечетно.

Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(c).
Если это выражение равно 0 первый игрок проигрывает, а иначе выыигрывает.
  #3  
Старый 10.05.2008, 12:19
Новичок

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

Скорей всего так... а можно поконкретней???. Это игра отличается от классической Ним игры...
  #4  
Старый 10.05.2008, 12:34
гость

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

Да это элементарное приложение упомянутой уже выше теоремы.
Подробнее смотрим в гугле и учебниках по комбинаторной теории игр.

http://en.wikipedia.org/wiki/Sprague-Grundy_theorem
http://www.google.com/search?q=sprague+grundy
http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
  #5  
Старый 10.05.2008, 12:43
Новичок

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

???
Даже если нашли такую функцию Гранди. предположим, что у нас начальная позиция (k,n,m). Пусть из этой позиции существуют S выигрышных позиций. Снова применяем нашу функцию Гранди для выигрышных позиций и т.д. В итоге надо выбрать такой путь при котором шансы на победу максимальны... Каким оразом это организовать? Древо игры? Но для k,n,m>10 оно уже будет непомерно большим и к тому же в нём будут одинаковые позиции...
  #6  
Старый 10.05.2008, 12:54
Новичок

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

>> http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
Спасибо за ссылочку! сейчас читаю...
  #7  
Старый 10.05.2008, 13:35
гость

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

Никаких деревьев не нужно рассчитывать.
Все что вам тут нужно знать - гранди-функцию G(n) игры в которой изначально есть только одна единственная кучка из n фишек.

Есть у вас изначально несколько таких кучек, с k, n, m фишками, то у вас получается то, что называется "суммой игр". Гранди функция суммы игр есть xor гранди-функции каждой игры по отдельности (теорема Шпрага-Гранди).
Т.е. G(k,n,m) = G(k) ^ G(n) ^ G(m).

G(n) по ее определению, а также еще раз используя т. Шпрага-Гранди, можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }.
где mex S = наименьшее неотрицательное целое, не входящее в множество S, а ^ -- операция xor.
  #8  
Старый 10.05.2008, 13:46
Новичок

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

Огромное спасибо, очень помогло!!!! я то было уже отчаился... осталось только написать. ещё раз спасибо!
  #9  
Старый 10.05.2008, 13:54
Новичок

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

Ещё один вопрос. Какие книги посоветуете по теории игр на русском языке???
  #10  
Старый 10.05.2008, 14:07
гость

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

Теория игр это очень широкая область. Игра Ним и теория Шпрага-Гранди относится к той ее части, что называется combinatorial game theory.

А по ней я могу только порекомендовать русские переводы (если они вообще существует) классических англоязычных книг:
E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays
J. H. Conway. On Numbers And Games.
 


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

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


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