PMG

Пытаюсь найти алгоритм для данной игры (выигрышная стратегия)
имеется какое-то кол-во горизонтальных площадок, которые состоят в свою очередь из какого-то кол-ва клеток - короче, обычная сетка - т.е. матрица. Сначала расставляем по одной фишки в любой одной из клеток каждой из площадок (строки матрицы).
!--!--!--!---!---!---!---!
!____________*
!--!--!--!---!---!---!---!
!___________*
!--!--!--!---!---!---!---!
!____*
!--!--!--!---!---!---!---!
!___________*
!--!--!--!---!---!---!---!
!____*
!--!--!--!---!---!---!---!
к примеру такое поле 5-площадок, 7 клеток, где * - фишка

Далее делаются ходы - передвигаются фишки строго влево на любую клетку этой площадки. И так далее, выиграет тот, кто поставит фишку в самую левую клетку игрового поля последним. Фишки все общие - ходить любой

Не могли бы, посоветовать алгоритм игры или, если встречали, ссылочки на нечто похожее
Заранее благодарен

Не совсем понял. Здесь по-моему всегда выигрывает тот, кто поставил свою фишку на самую крайнюю правую клетку, так как если сдвигать фишку надо при ходе и ход делать надо и сдвигать только влево, то тот у кого крайне правая фишка заведомо выигрывает.

Или я что-то не понял .

_________________
С уважением, Сергей

Все фишки общие
Если бы было деление на фишки - свои и соперника, то да, выигрыл бы тот у кого сумма клеток свободных для ходов больше - или в некоторых ситуациях самая правая фишка (а может в принципе и вообще)
Но так как нет деления, здесь это отпадает

Это типа накладываешь монетки в стаканчик, а он на воде. Или убираешь палочки со стола ... Ничего не напоминает?

Я точно не знаю, но если есть решение таких задач, то надо видимо интересоваться дискретной математикой...

_________________
С уважением, Сергей

"фишку в самую левую клетку игрового поля последним" - т.е. проигрывает тот, кто ставит первым фишку в самую левую клетку? Я прав? Т.е. ему больше некуда ходить как поставить фишку на крайне левую клетку любой площадки?

_________________
С уважением, Сергей

Ну да (только эта фишка должна быть предпоследней, т.е. уже все остальные фишки поставлены на эту клетку)
после же этого хода, соперник ставит единственную фишку на левую крайнюю клетку и выигрывает

Т.е. как какая то фишка попадает на крайнюю левую клетку - она просто выбывает из игры и, грубо говоря, нужно последним завершить игру - последним поставить фишку на самую левую клетку площадки

Мне это напоминает квест Ике-Баана из Космических рейнджеров
Алгоритм я не знаю, но что-то мне подсказывает, что без рекурсии тут не обойтись.

А зачем тебе это?

В принципе я сейчас нашел алгоритм, он практически аналогичен алгоритму НИМ. Только вместо фишек как в алгоритме НИМ, нужно оперировать свободными ходами

Это что за алгоритм НИМ?

_________________
С уважением, Сергей

Нда, как все запущено
Это старая игра
Небольшое описание есть здесь
http://www.hardline.ru/selfteachers/Inf ... 2_7_3.html

Ни когда не играл в эту игру ... Интересно, хоть кто-то из моих знакомых знает о ней ... поспрашиваю ...

_________________
С уважением, Сергей

Кстати, в твоей игре, количество клеток, площадок, и расположение фишек вначале игры как-то фиксируются? Или случайно?

_________________
С уважением, Сергей

Ним крайне похож, только там выигрывает последний, а не проигрывает. Но скорее всего ничего от этого принципиально не меняется.

В общем, у меня возник такой алгоритм:

Надо убрать фишки со всех площадок кроме двух, причем в них должно быть четное кол-во оставшихся клеток, если на этот момент ходишь ты.

Т.е. тот кто ходит первым, должен всегда стараться иметь по всем площадкам четное число оставшихся клеток, и максимально быстро убрать все фишки из всех площадок кроме двух.

Вот примерно такая заготовка.

_________________
С уважением, Сергей

Кол-во клеток и площадок нефиксированно.
Алгоритм на основе убирания фишек - это мой первый вариант стратегии игры. Но там может возникнуть ряд исключительных ситуаций. Допустим я то убираю фишки, а соперник не убирает, а ходит и на этом он может подловить


-------*
-------*
---*
-----*----
-----------*
К примеру такая ситуация 5- фишек

убираем (ставим на самую левую клетку), например, самую ближнюю фишку
Получаем
-------*
-------*
*
-----*----
-----------*
Соперник ходит
-------*
-------*
*
-----*----
-----*

Всё я проиграл - образовались две пары, я буду на ход впереди

Вообщем эту ситуацию, конечно, можно обойти - не спорю - я так и делал, это только в качестве примера. Однако рассчитывать все возможные ситуации - ох как не просто, если вообще возможно.
Лучше алгоритма игры НИМ нет, я это проверил сыиграв своей старой стратегией с новой . Старая конечно проиграла
Стратегия игры НИМ абсолютно выигрышная и там явно определяется, могу ли я выиграть или нет
Если я могу - всё соперник обречен - как бы он не ходил, чтобы невытворял , я выиграю
Другой такой алгоритм врятли удастся придумать, а если и удастся то он будет я уверен раза в 5 больше данного.

Алгоритм:
Пусть дан список расстояний до левого края (игроки своим ходом могут его только уменьшать). Представим его в двоичном виде. Например
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).