PMG https://forum.pmg.org.ru/ |
|
Сдвиг фишек https://forum.pmg.org.ru/viewtopic.php?f=3&t=111 |
Страница 1 из 2 |
Автор: | SparkerPRO [ 17 окт 2005 23:04 ] |
Заголовок сообщения: | Сдвиг фишек |
Пытаюсь найти алгоритм для данной игры (выигрышная стратегия) имеется какое-то кол-во горизонтальных площадок, которые состоят в свою очередь из какого-то кол-ва клеток - короче, обычная сетка - т.е. матрица. Сначала расставляем по одной фишки в любой одной из клеток каждой из площадок (строки матрицы). !--!--!--!---!---!---!---! !____________* !--!--!--!---!---!---!---! !___________* !--!--!--!---!---!---!---! !____* !--!--!--!---!---!---!---! !___________* !--!--!--!---!---!---!---! !____* !--!--!--!---!---!---!---! к примеру такое поле 5-площадок, 7 клеток, где * - фишка Далее делаются ходы - передвигаются фишки строго влево на любую клетку этой площадки. И так далее, выиграет тот, кто поставит фишку в самую левую клетку игрового поля последним. Фишки все общие - ходить любой Не могли бы, посоветовать алгоритм игры или, если встречали, ссылочки на нечто похожее Заранее благодарен |
Автор: | MagicWolf [ 18 окт 2005 08:36 ] |
Заголовок сообщения: | |
Не совсем понял. Здесь по-моему всегда выигрывает тот, кто поставил свою фишку на самую крайнюю правую клетку, так как если сдвигать фишку надо при ходе и ход делать надо и сдвигать только влево, то тот у кого крайне правая фишка заведомо выигрывает. Или я что-то не понял . |
Автор: | SparkerPRO [ 18 окт 2005 09:23 ] |
Заголовок сообщения: | |
Все фишки общие Если бы было деление на фишки - свои и соперника, то да, выигрыл бы тот у кого сумма клеток свободных для ходов больше - или в некоторых ситуациях самая правая фишка (а может в принципе и вообще) Но так как нет деления, здесь это отпадает |
Автор: | MagicWolf [ 18 окт 2005 16:13 ] |
Заголовок сообщения: | |
Это типа накладываешь монетки в стаканчик, а он на воде. Или убираешь палочки со стола ... Ничего не напоминает? Я точно не знаю, но если есть решение таких задач, то надо видимо интересоваться дискретной математикой... |
Автор: | MagicWolf [ 18 окт 2005 16:22 ] |
Заголовок сообщения: | |
"фишку в самую левую клетку игрового поля последним" - т.е. проигрывает тот, кто ставит первым фишку в самую левую клетку? Я прав? Т.е. ему больше некуда ходить как поставить фишку на крайне левую клетку любой площадки? |
Автор: | SparkerPRO [ 18 окт 2005 17:21 ] |
Заголовок сообщения: | |
Ну да (только эта фишка должна быть предпоследней, т.е. уже все остальные фишки поставлены на эту клетку) после же этого хода, соперник ставит единственную фишку на левую крайнюю клетку и выигрывает Т.е. как какая то фишка попадает на крайнюю левую клетку - она просто выбывает из игры и, грубо говоря, нужно последним завершить игру - последним поставить фишку на самую левую клетку площадки |
Автор: | ENGor [ 19 окт 2005 14:09 ] |
Заголовок сообщения: | |
Мне это напоминает квест Ике-Баана из Космических рейнджеров Алгоритм я не знаю, но что-то мне подсказывает, что без рекурсии тут не обойтись. А зачем тебе это? |
Автор: | SparkerPRO [ 19 окт 2005 15:12 ] |
Заголовок сообщения: | |
В принципе я сейчас нашел алгоритм, он практически аналогичен алгоритму НИМ. Только вместо фишек как в алгоритме НИМ, нужно оперировать свободными ходами |
Автор: | MagicWolf [ 19 окт 2005 16:03 ] |
Заголовок сообщения: | |
Это что за алгоритм НИМ? |
Автор: | SparkerPRO [ 19 окт 2005 21:43 ] |
Заголовок сообщения: | |
Нда, как все запущено Это старая игра Небольшое описание есть здесь http://www.hardline.ru/selfteachers/Inf ... 2_7_3.html |
Автор: | MagicWolf [ 20 окт 2005 10:55 ] |
Заголовок сообщения: | |
Ни когда не играл в эту игру ... Интересно, хоть кто-то из моих знакомых знает о ней ... поспрашиваю ... |
Автор: | MagicWolf [ 20 окт 2005 10:58 ] |
Заголовок сообщения: | |
Кстати, в твоей игре, количество клеток, площадок, и расположение фишек вначале игры как-то фиксируются? Или случайно? |
Автор: | MagicWolf [ 20 окт 2005 11:11 ] |
Заголовок сообщения: | |
Ним крайне похож, только там выигрывает последний, а не проигрывает. Но скорее всего ничего от этого принципиально не меняется. В общем, у меня возник такой алгоритм: Надо убрать фишки со всех площадок кроме двух, причем в них должно быть четное кол-во оставшихся клеток, если на этот момент ходишь ты. Т.е. тот кто ходит первым, должен всегда стараться иметь по всем площадкам четное число оставшихся клеток, и максимально быстро убрать все фишки из всех площадок кроме двух. Вот примерно такая заготовка. |
Автор: | SparkerPRO [ 20 окт 2005 18:53 ] |
Заголовок сообщения: | |
Кол-во клеток и площадок нефиксированно. Алгоритм на основе убирания фишек - это мой первый вариант стратегии игры. Но там может возникнуть ряд исключительных ситуаций. Допустим я то убираю фишки, а соперник не убирает, а ходит и на этом он может подловить -------* -------* ---* -----*---- -----------* К примеру такая ситуация 5- фишек убираем (ставим на самую левую клетку), например, самую ближнюю фишку Получаем -------* -------* * -----*---- -----------* Соперник ходит -------* -------* * -----*---- -----* Всё я проиграл - образовались две пары, я буду на ход впереди Вообщем эту ситуацию, конечно, можно обойти - не спорю - я так и делал, это только в качестве примера. Однако рассчитывать все возможные ситуации - ох как не просто, если вообще возможно. Лучше алгоритма игры НИМ нет, я это проверил сыиграв своей старой стратегией с новой . Старая конечно проиграла Стратегия игры НИМ абсолютно выигрышная и там явно определяется, могу ли я выиграть или нет Если я могу - всё соперник обречен - как бы он не ходил, чтобы невытворял , я выиграю Другой такой алгоритм врятли удастся придумать, а если и удастся то он будет я уверен раза в 5 больше данного. |
Автор: | R.I.P. [ 08 авг 2006 17:16 ] |
Заголовок сообщения: | |
Алгоритм: Пусть дан список расстояний до левого края (игроки своим ходом могут его только уменьшать). Представим его в двоичном виде. Например 22=10110 19=10011 12=01100 посчитаем сумму в каждом столбике и возьмем остаток при делении на два. Получим: 01001 Своим ходом нужно сделать так, чтобы данная цифра(далее сумма) стала равна 00000. 1 0 1 1 0 1 0 0 1 1 0[1]1 0[0] --------- 0[1]0 0 1 Ищем самую левую единицу в сумме, затем ищем единицу в этом столбике. В числе, где нашли единицу, все цифры в тех разрядах, где в итоге 1, меняем на противоположные. Получаем: 10110=22 10011=19 00101=5(очевидно, это число меньше начального) ------- 00000 Вывод: третью фишку нужно подвинуть на 12-5=7 клеток. После хода противника повторяем алгоритм (и так до выигрыша). Выигрышность стратегии в том, что любым своим ходом противник делает сумму ненулевой. А мы обнуляем ее до тех пор, пока не достигнем выигрышной позиции(после своего хода!), где все расстояния нули(кстати, сумма там тоже равна 0). |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |