Игра "Вперед и вверх"

[Arigato]

Задачка оказалась интереснее, чем кажется на первый взгляд. Если рассматривать два направления порознь, компьютер играет не оптимально; если рассматривать оба направления вместе, тоже не оптимально. Надо подумать над другой стратегией игры.

[Arigato]

Алгоритм оптимальной игры оказался куда более хитрым, чем казалось изначально.
В конечном итоге я решил уйти от выведения точной математической формулы оптимального хода и сделать, как предлагал LeBron.
А именно: в начале игры мы создаём матрицу, размерность которой такая же, как и игрового поля. В этой матрице просто помечаются те клетки, которые ведут к победе. Компьютеру остаётся только ходит так, что бы он после своего хода попадал в одну из этих клеток.
Если так пойти не получается (игрок играет оптимально и первый занял выигрышную позицию), то надо ходить рандомом вверх или вправо на 1 позицию, что бы затянуть игру.
Вся фишка в том, что нужно правильно определить выигрышные позиции на игровом поле.
Кстати, в этой игре, при оптимальной игре обоих противников, побеждает тот, кто делает 1-й ход.

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

[LeBron]

Сообщение от Arigato

Алгоритм оптимальной игры оказался куда более хитрым, чем казалось изначально.
В конечном итоге я решил уйти от выведения точной математической формулы оптимального хода и сделать, как предлагал LeBron.
А именно: в начале игры мы создаём матрицу, размерность которой такая же, как и игрового поля. В этой матрице просто помечаются те клетки, которые ведут к победе. Компьютеру остаётся только ходит так, что бы он после своего хода попадал в одну из этих клеток.
Если так пойти не получается (игрок играет оптимально и первый занял выигрышную позицию), то надо ходить рандомом вверх или вправо на 1 позицию, что бы затянуть игру.
Вся фишка в том, что нужно правильно определить выигрышные позиции на игровом поле.
Кстати, в этой игре, при оптимальной игре обоих противников, побеждает тот, кто делает 1-й ход.

Пример программы, играющей оптимально, прикрепил к сообщению (игровое поле всегда 20*20, а длину ходов можно задавать).

Думаю, в авторском варианте - читаем размеры поля и потом просчитываем конкретно для них. Что интересно, мне подтвердили, что есть "полное" решение, но гугл находит эту задачу в старых олимпиадах только с "мягкими" ограничениями, позволяющими использовать предложенный мною алгоритм. Я немного опозорился - у меня есть ошибка, невнимательно читал условие, писал для клеток, а не линий сетки, надо единички приплюсовать в моем коде, или сделать перенумерацию с нулевой, так как считает верно, но итоги "урезанные". По поводу выиграшной стратегии - не всегда она есть. И 1/2 динамика, и Шпраг-Гранди дают наличие проиграшных точек. Если начинать с проиграшной точки, то не понимаю, как можно выиграть при оптимальной стратегии противника. Самый примитивный пример - поле 1 на 1 с любыми ограничениями на ход.
Мы начинаем в (0,0) и после любого нашего шага одна из координат 1, а вторая 0. Как тут выиграть?

[Arigato]

Сообщение от LeBron

Самый примитивный пример - поле 1 на 1 с любыми ограничениями на ход.
Мы начинаем в (0,0) и после любого нашего шага одна из координат 1, а вторая 0. Как тут выиграть?

Поле 1*1 всегда даёт победу тому, кто идёт первый.
Если 2*2, то надо походить в позицию 1*1 и опять - победа, т.к. у противника остаётся на выбор 2 проигрышных хода.
Вроде бы, у 1 игрока выигрышная ситуация в любом случае, кроме такого: поле 1*2N, можно пойти только на 1 клетку.

P.S. Вообще-то довольно много полей могут привести к проигрышу, если ходы только на 1 клетку. Но этот случай не интересен, т.к. тут и игры ни какой не будет, тупо идти вперёд (или вверх, что тоже самое).

[LeBron]

Сообщение от Sl1mka.

Пользователь задает максимальную длину линии - X по горизонтали (X<=N) и Y по вертикали (Y<=M).

Как с (0,0) походить в (1,1)? По диагонали, что ли? Или я опять не до конца прочел условие, или сильно туплю.

[Arigato]

Сообщение от LeBron

Как с (0,0) походить в (1,1)? По диагонали, что ли? Или я опять не до конца прочел условие, или сильно туплю.

Так позиции (0,0) и нет, первый ход делается из (1,1).

[Sl1mka.]

LeBron, к черту узлы сетки. Пускай ходы выполняются по средствам закрашивания точек начиная с точки (1,1).
Так будет куда проще делать графическую обработку кода.
Поле - квадрат или прямоугольник с разлинованными столбцами и строками. Начальная позиция - нижний левый угол, т.е. с точки зрения машинной матрицы это точка point(n,1) , в то время как конечная точка точка - верхний правый угол и, переводя на машинную матрицу, это точка point(1,m). Пользователь выполняет ходы нажатием на стрелочки "вверх" и "вправо" число нажатий отвечает за длину его хода (за число закрашенных клеточек поля) переход хода (или же признак окончания хода) выполняется нажатием на пробел.
Поэтому, грубо говоря, мы не рисуем линии, а закрашеваем клеточки.

По мне, так разбиение игры на 2 подыгры невозможно, т.к. проверяя на бумаге, выяснил, что существуют такие моменты, когда закрашенные клетки добираются либо до верхней границы поля, либо до правой границы поля - и что же в итоге имеем: из-за разницы в x и у (т.е. из-за разницы в макс. длине хода) невозможно закрасить "необходимое" число клеточек, чтобы дойти до победной ("победная" здесь - точки, о которых говорил LeBron в первом сообщении, точки, обозначенные двойкой в его коде). А следовательно, приходится ходить на проигрышную клетку и теряется преимущество.

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

Со стратегией все понятно, определять победные точки умеем. Осталось заставить компьютер искать эту ближайшую победную точку и ходить на нее. А именно: реализовать идею.
Буду благодарен, если поможете.

Одно слово насчет позиций: Arigato позиция (0,0) есть как таковая, но мы её не видим. в самом начале игры (до первого хода) указатель стоит на позиции (0,0) это нужно для организации возможности сделать первый ход на 1 клетку. Т.к. если указатель стоит на позиции (1,1) изначально, первым ходом на 1 клетку будет либо позиция (2,1) - если вправо, либо (1,2) - если вверх.
Но все немного сложнее. Все эти "позиции": (0,0), (1,1), ..., (15, 10),...
Это координаты, если брать за начало координатной системы нашу начальную позицию.
В матрице это будет выглядеть несколько иначе: позиция (1,1) - это point(n,1) и т.д.

Вобщем тут то у меня и появляется новая путанница. Жду идей, спасибо, что стараетесь!

[Arigato]

Сообщение от Sl1mka.

Одно слово насчет позиций: Arigato позиция (0,0) есть как таковая, но мы её не видим. в самом начале игры (до первого хода) указатель стоит на позиции (0,0) это нужно для организации возможности сделать первый ход на 1 клетку.

Вы мою программу посмотрели? Там именно так и реализовано, и стратегия игры оптимальная. Если длинна хода > 1, то всегда выигрывает тот, кто первый делает ход (если оба противника играют по оптимальной стратегии).
Искать ближайшие победные точки очень просто: движемся от текущей точки вправо от 1 до XMax клеток, пока не встретим победную точку; аналогично: вверх от 1 до YMax. Как нашли - ходим. Не нашли - ходим на 1 вверх или право (у меня выбор простым рандомом).

[Sl1mka.]

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

Очень надеюсь, это вас не сильно затруднит... Я еще слишком начинающий программист, с графикой орудую по книге и с натяжкой...

[Arigato]

Сообщение от Sl1mka.

Очень надеюсь, это вас не сильно затруднит... Я еще слишком начинающий программист, с графикой орудую по книге и с натяжкой...

Вообще-то затруднит. Я с Turbo Pascal лет 5 не работал, да и не хочу. Чем вам вариант под Windows плох? Препод не примет ?
Ну так вот вам возможность освоить работу с графикой под DOS.
А мою прогу можете использовать для проверки своего алгоритма: если ваша программа будет в 100% случаев обыгрывать мою, делая ход первой, то вы добились оптимального алгоритма.