IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Стратегия игры "Три числа"
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 98
Пол: Мужской
Реальное имя: Andriy

Репутация: -  0  +


Есть игра "Три числа" - на листке бумаги написано 3 числа, не отрицательных, большых от нуля или равных ему.
Тот, у кого есть ход, вычеркивает ОДНО из этих чисел и на его место ставит меньшее, но НЕ МЕНЬШЕ НУЛЯ. НУЛЬ НЕЛЬЗЯ ВЫЧЕРКИВАТЬ. Игра заканчивается, когда не возможно ничего сделать, выигрывает тот, который сделал последний ход. Как, зная все 3 числа и того, кто ходит первым, определить, кто выиграет (то есть какая стратегия и тактика этой игры)?
ПОДСКАЗКИ:
1) при числах 3, 4, 5 выигрывает тот, кто ходит первый;
2) при числах 7,0,7 выигрывает второй, он должен повторять ходы противника wink.gif

Просьба помочь мне, а именно - подсказать тактику/стратегию этой игры wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


http://ru.wikipedia.org/wiki/%D0%9D%D0%B8%...%D1%80%D0%B0%29

И дальше - гуглом ищешь более подробное объяснение, если нужно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 98
Пол: Мужской
Реальное имя: Andriy

Репутация: -  0  +


Большущее спасибо...
Возник вопрос - а как к этому можно додуматься самостоятельно, если ничего об этом ранее не знал?
А ведь задача-то с школьной олимпиады - задание следующее: определить по трем числам победителя и вывести общий счет первого и второго игрока unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ну, как-то можно smile.gif Меня тоже такой вопрос интересует иногда, только для других задач smile.gif И кстати в свое время и для этой тоже - сам не придумал. Действительно, очень уж специфично, на первый взгляд.

А на самом деле, этот алгоритм лежит в основе значительно более крупного объекта в теории игр - чисел Спрага-Грюнди. Хочешь - погугли-почитай.

От школьников никаким образом не может требоваться придумывать такие вещи на школьных олимпиадах; просто именно эта игра - считай, классика теории игр, и такие вещи считаются общеизвестными (да и, начиная с некоторого уровня, такими и являются).

Так что ты столкнулся скорее с проблемой нехватки знаний чем с проблемой нехватки смекалки, не расстраивайся smile.gif

P.S. Хочешь, подумай над обратной игрой: тот, кто делает последний ход - проигрывает. Вот тут уже можно придумать самому, хотя тоже непросто.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


Цитата
А на самом деле, этот алгоритм лежит в основе значительно более крупного объекта в теории игр - чисел Спрага-Грюнди. Хочешь - погугли-почитай.

Не поверишь - вообще не гуглица, даже не яхухица, а о рамблере даже вспоминать не буду blink.gif Ноль, полный ноль nea.gif
Цитата
считаются общеизвестными (да и, начиная с некоторого уровня, такими и являются).

Это ж какой уровень надо, если всемирная паутина о таком не слышала... rolleyes.gif

Сообщение отредактировано: Bokul -


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 98
Пол: Мужской
Реальное имя: Andriy

Репутация: -  0  +


Bokul , ищи обширнее yes2.gif
Кое-что находит об "Спаре-Грюнди" и "Шпраге-Грюнди" wink.gif
Например: http://mashinnyi-razum.narod.ru/mirovoegos...ospodstvo1.html
Ну и статья, которая ставит "все точки над i": http://en.wikipedia.org/wiki/Sprague–Grundy_theorem (в Википедии ТОЛЬКО на английском) yes2.gif
Ну и на иглише можно что-то найти...
В тему: http://en.wikipedia.org/wiki/Category:Comb...ial_game_theory
http://en.wikipedia.org/wiki/Dynamic_programming (на разных языках, но на английском - самая полная версия статья) wink.gif
Цитата
От школьников никаким образом не может требоваться придумывать такие вещи на школьных олимпиадах; просто именно эта игра - считай, классика теории игр, и такие вещи считаются общеизвестными (да и, начиная с некоторого уровня, такими и являются).
Так что ты столкнулся скорее с проблемой нехватки знаний чем с проблемой нехватки смекалки, не расстраивайся

Наверное, так и есть (никогда бы не додумался слаживать размеры кучок в двоичной системе, шел в совершенно другом направлении - смотрел парность кучек, их размеров и т.д. и т.п.).
Спасибо за советы wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Кстати, кстати. Теория - теорией, но такой вопрос: какие были ограничения на числа? Чисел ровно три, и если каждое, скажем, не больше 100, то она решается очень легко без всякой теории smile.gif (как?)

Относительно недавно на одной польской олимпиаде была задача на очень сложную теорию игр, и после тура организаторы (в высшей степени компетентные люди) рекомендовали вот эту ссылку: http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

Сам не смотрел, но смело рекомендую smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 98
Пол: Мужской
Реальное имя: Andriy

Репутация: -  0  +


Все три числа >=0 и <=1000 rolleyes.gif
Это что-то меняет?
Документ скачал, буду разбиратся (английским владею не свободно), спасибо wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Меняет принципиально.

Тогда все решалось проще (конечно, кодить проще классический алгоритм, но придумать его сложнее).

Просто генерим все проигрышные тройки, т.е. такие тройки, в которых игрок, делающий первый ход, проигрывает.

1) Тройка (0, 0, 0) - проигрышная (нельзя сделать ход).
2) Тройка (a, b, c) - проигрышная тогда и только тогда, когда из нее нельзя сделать ход в проигрышную тройку.

Делаешь три вложеных цикла, и проверяешь. Тут, правда, есть свои сложности - с хранением найденных троек, особенно если давали только турбо паскаль (память >64K можно выделить только динамически).

Довольно удобна такая уловка: из второго правила сразу видим, что для данных a и b может быть только одно с такое, что тройка (a, b, c) - проигрышная. Поэтому можно завести двумерный массив 1000х1000, и его значение в точке (a, b) - это соответствующая с, или -1, если с еще не нашли. В таком вот духе smile.gif

Разобраться стоит и с этим решением, возможно, от вас ждали именно чего-то такого.

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:46
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name