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

[Sl1mka.]

Приветствую вас, великие программисты.
Прошу помощи: получил задание - разработать программу игры "вперед и вверх".
Код труда не представляет, но в игре необходимо выделить беспроигрышную тактику (которой будет следовать компьютер).
Поэтому вот краткая характеристика игры: игра идет на поле в клетку размерами M*N. Пользователь задает максимальную длину линии - X по горизонтали (X<=N) и Y по вертикали (Y<=M). Суть игры: из точки в левом нижнем углу пользователь и компьютер по очереди рисуют линии, не превышающие вышеописанных длин, при том начало очередной линии совпадает с концом предыдущей. Победа в игре: добраться, так сказать, своей линией до конечной точки - верхний правый угол вышеописанного поля.

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

[LeBron]

Алгоритм решения подобных задач, в тому случае, если математически делать влом:
1. Пишем динамику с поиском выиграшных/проиграшных позиций.
2. Вклеиваем в нее масив указателей, чтобы понять, как действовать в выиграшной/проиграшной позиции.
Сейчас я спать пойду, нету времени самому кодить что-то, суть динамического решения такая: крайная верхняя правая клетка - выиграш. Далее просматриваем массив посрочно сверху вниз (В каждой стоке просматриваем справа налево, а не наоборот), если с данной клетки можно попасть только в выиграшные - она проиграшная. Иначе - выиграшная. Если выиграшная - понятно, ходим в проиграшную, а после хода противика повторяем все то же самое с новой клетки.
З.Ы. Усный анализ показвает, что далеко не во всех случаях есть выиграшная стратегия (самый простой пример - поле 2 на 2 и ограничение на длину хода 1). Тогда придется надеятся, что игрок неоптимален и сделает ошибку, после которой можно перейти на выиграшную стратегию.

[Sl1mka.]

Благодарю за ответ, однако, это несколько не то, что я ожидал увидеть.
Как я понимаю, должна быть этакая формула (с использованием переменных n,m,x,y) по которой компьютер будет делать каждый очередной ход.

[LeBron]

Сейчас у меня нету желания что-либо решать математически, когда будет время - напишу то, что посоветовал вам, и сяду выводить решение сам. К вечеру будет готово.

А какие ограничения? может, вообще не нужна никакая стратегия? если поле 100 на 100, то можно и заранее просчитать

var a,b,c,d,i,j,q,t:longint;ar:array[-100..100,-100..100] of longint;
begin
readln(a,b,c,d);
ar[1,b]:=2;
for i:=1 to a do begin for j:=b downto 1 do begin
q:=0;
for t:=1 to c do begin if ar[i-t,j]=2 then q:=1;end;
for t:=1 to d do begin if ar[i,j+t]=2 then q:=1;end;
if q=1 then ar[i,j]:=1 else ar[i,j]:=2;
end;end;

for i:=1  to a do begin for j:=1 to b do begin write(ar[i,j],' ');end;writeln;end;

end.

Вот код для простой проверки выиграшности/проиграшности, в матрице на выходе 2 - проиграшная позиция, 1 - выиграшная. Можете начинать анализировать.

[Sl1mka.]

Всё несколько сложнее...
1. поле может быть квадратным или прямоугольным (10*10, 15*4)
2. длина максимального хода по горизонтали и вертикали могут быть различны (х=3, у=5)
3. размеры поля и макс. длина хода вводятся пользователем.

Вчера написал код, определяющий выигрышные позиции на поле, посмотрите, пожалуйста:

uses crt;

var
point: array[0..100,0..100] of integer; {m*n;m-i;n-j}
n,m,x,y,i,ii,j,jj:integer;

procedure paint(i,j:integer);
var ii,jj:integer;
begin
point[i,j]:=1;
jj:=j+1;
ii:=i-1;
while (m>=jj) and ((j+x)>=jj) do begin
if point[i,jj]=1 then point[i,j]:=0;
jj:=jj+1;
end;
while (n>=ii) and ((i-y)<=ii) do begin
if point[ii,j]=1 then point[i,j]:=0;
ii:=ii-1;
end;
end;


begin
clrscr;
m:=20;
n:=30;
x:=6;
y:=3;
point[1,m]:=1;
i:=m; j:=1;
while (i>0) and (n>j) do begin
for ii:=i downto 1 do
paint(j,ii);
for jj:=j+1 to n do
paint(jj,i);
i:=i-1;
j:=j+1;
end;
for i:=1 to n do
begin
for j:=1 to m do
begin
write(point[i,j],' ');
end;
writeln;
end;

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

[Arigato]

Упростим задачу.

Допустим, имеется игровое поле: горизонтальная линия из N клеток.
За 1 ход можно продвигаться вперёд от 1 до K клеток.
Выигрывает тот, кто при своём ходе достигнет конца игрового поля.

Обозначим за P текущую позицию в игровом поле.

1. Если на нашем ходе P >= N - K, то, очевидно, что мы выиграли, т.к. можно походить (N - P) и достичь конца поля.
2. Если же P = N - K - 1, то, очевидно, что это проигрышная позиция, т.к., как ни пойди, получим 1-й случай для нашего противника, в котором он побеждает.

Задача сводится к тому, что бы прийти не к победе, а к позиции (N - K - 1).
Обозначим N1 = N - K - 1.
Условие задачи остаётся тем же, только теперь нам требуется достичь не позицию N, а позицию N1.
Аналогично, те же 2 случая, что и для исходной игры.

И т.д....

Остаётся вычислить эту цепочку: N, N1, N2, ..., которая гарантированно приводит нас к победе:
N0 = N
N1 = N - K - 1
N2 = N1 - K - 1 = N - K - 1 - K - 1 = N - 2 * K - 2
N3 = N2 - K - 1 = N - 2 * K - 2 - K - 1 = N - 3 * K - 3
...
Ni = N - i * K - i = N - i * (K + 1)

Вычисляем, сколько всего Ni будет существовать, т.е. каково максимальное i:
imax = N div K - 1
Вычитаем 1, т.к. нумерация N у нас от 0.

И так, ход компьютера, текущая позиция после хода игрока P (в начале игры P = 0).
Определяем индекс i текущего хода:
i = (N - P) div (K + 1)

Нам необходимо сделать следующий ход (обозначим его за L):
L = Ni - P
Если L = 0 (значит противник играет по оптимальной стратегии), то ходим L = 1, т.е. продвигаемся вперёд на минимальное расстояние, что бы затянуть игру и повысить вероятность ошибки игрока.

Ваша же задача состоит из 2 одинаковых подзадач, которые я описал выше. Т.е. движение по горизонтали и вертикали можно рассматривать как независимые подзадачи. Как именно ходить (по вертикали или по горизонтали) надо определять исходя из того, где мы сбились с оптимального пути, т.е. надо выйти на Ni как по горизонтали, так и по вертикали.

На самом деле идея очень простая, если понять принцип. Это только в описании много получилось, но тут нет ничего сложного.

Может, чуть позже, напишу программку в Делфи, демонстрирующую этот принцип.

[Arigato]

Sl1mka.
Такой нюанс: линия рисуется только горизонтально или вертикально или же под произвольным углом? Если под произвольным углом, то тут не совсем понятно, как именно она будет рисоваться, т.к. длинна же считается в пикселях.

[Sl1mka.]

Arigato, рассматривал такой ход решения, но, вероятно, где-то сбился с мысли. Буду благодарен за полный анализ (и вертикаль, и горизонталь).
Линии рисуются или только вправо, или только вверх. За один ход нельзя нарисовать кривую линию, также нельзя рисовать линии под углом (след. две рядом стоящие линии дадут или угол 180 гр., если идут в одном и том же направлении, или же 90 гр., если идут в разных направлениях).

С таким ходом решения не справился из-за того, что поле может быть не квардатным, т.е. n<>m, а также вертикальный и горизонтальный предел хода может быть различен, т.е. x<>y. Не справился с выведением формулы.

Однако был замечен интересный момент: каким бы образом не строились линии (по какой бы траектории не проходил путь к выйгрышной точке), сумарное количество клеток, встречаемых на пути будет равно (n+m)-1 и при том неизменно, независимо от траектории, т.е. (n+m)-1=const
Пример: для поля 10*10. n=10, m=10. Количество клеток, по которым могут быть совершены ходы от начальной точки до конечной будет равно (m+n)-1=(10+10)-1=19

[Arigato]

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

Буду благодарен за полный анализ (и вертикаль, и горизонталь).

По сути, там ни какой разницы, что прямая, что плоскость.
Просто за N принимаем (n + m - 1) - расстояние до победы. А дальше всё точно так же, как я расписал выше. Только двигаться надо или вверх или вправо, главное, сокращать расстояние на требуемое значение (если вверх не хватает клеток, идём вправо; если вправо не хватает, идём вверх; если можно идти и вправо и вверх, идём куда угодно, главное, заданное число клеток преодолеть).

P.S. Как мне кажется, всё же лучше именно разделить на 2 подъигры и параллельно играть в обе (отдельно двигаться вправо и отдельно вверх), контролируя, что бы в обоих подъиграх путь был выигрышным. Т.к. если рассматривать только расстояние до победы, может получиться, что мы будем стоять на диагонали, а в верху и справа поле будет заканчиваться раньше, чем то расстояние, которое мы должны пройти.

Сейчас попробую реализовать игру в Делфи, посмотрим, что получится.

[LeBron]

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

Всё несколько сложнее...
1. поле может быть квадратным или прямоугольным (10*10, 15*4)
2. длина максимального хода по горизонтали и вертикали могут быть различны (х=3, у=5)
3. размеры поля и макс. длина хода вводятся пользователем.

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

Я все учел - посмотрите внимательно на мой код.
Суть тактики подобрана верно.
Arigato, фактически Вы правы, так и надо. Действительно, как мне кажетася, оптимальный вариант - именно независимая игра по 2 направлениям. Если противник движется по иксам - уравниваем по иксам, если движется по игрекам - уравниваем по игрекам. Довольно легко доказать, что это всегда возможно.