Кто победит чёрного рыцаря?

[General]

Две шашки-рыцари стоят на противоположных краях прямоугольной доски 2х33 доски. Между ними 31 клетка. Начальная скорость каждого рыцаря – единица.

Каждым своим ходом рыцарь может или продвинуться в сторону противника на количество клеток, равное своей текущей скорости, или пришпорить лошадь, увеличив скорость на 1, и приблизиться к противнику на увеличенной скорости.

Максимальная скорость рыцарей равна шести. Ходы делаются по очереди. Выигрывает тот, кто своим ходом приблизился к противнику вплотную, или прошёл ещё дальше.

У первого существует выигрышная стратегия. Попробуйте её найти, сыграв в компьютерную версию этой игры.



Скачать игру “Рыцарский турнир” 1.0

[TOTAL]

Надо смело мчаться с ускорением и целиться рыцарю в живот.

[ewert]

TOTAL в сообщении #228363 писал(а):

Надо смело мчаться с ускорением и целиться рыцарю в живот.

Да? А если оппонент особо так торопиться не будет? Ведь притормозить-то Вы не сможете.

[TOTAL]

ewert в сообщении #228370 писал(а):

Да? А если оппонент особо так торопиться не будет? Ведь притормозить-то Вы не сможете.

Оппонент торопиться не не будет, а не сможет, т.к. дохлый он уже, пал от моего копья. (Сначала хожу 2, потом 3, потом 3 ..) Вообще условие задачи непонятно. Требуется победить для данного расстояния? Или требуется придумать способ вычислять длину хода для произвольного расстояния?

[General]

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

Для данного случая вы нашли одну ветку стратегии
Ходы 2, 3, 3, 4, 5, 6 (Видите, вы ведь тут не бездумно разгоняетесь, а делаете небольшую паузу) приводят к победе, если чёрный рыцарь своими первыми тремя ходами идёт на 1, 2, 2. Если же он на ваш второй ход в 3 тоже ответит ходом в 3, то разгон не приведёт к победе.

ИИ чёрного рыцаря я устроил так, что в проигрышной позиции он выбирает ход случайным образом, а в выигрышной - никогда не теряет инициативы.

[maxal]

General
Подобная задача в двумерном варианте когда-то была на конкурсе по программированию у братьев Уваровых: Dead Racing.

[General]

Оо, да-да-да, когда в поезде с олимпиад, бывало, возвращался, любил с друзьями в гоночки играть на бумаге.

[TOTAL]

General в сообщении #228391 писал(а):

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

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

[General]

Хм, странно, видимо рендом вам подыгрывает

Вот ситуация (слева ходы белого, справа - чёрного):
2 - 1
3 - 2
3 - 2
Здесь дальнейшие ходы белого
4, 5 и 6 приведут к победе

А что делать в позиции:
2 - 1
3 - 2
3 - 3?

Собственно, разобрав эту ветку можно считать данный конкретный случай решённым.

[anja]

General в сообщении #228756 писал(а):

А что делать в позиции:
2 - 1
3 - 2
3 - 3?

Собственно, разобрав эту ветку можно считать данный конкретный случай решённым.

2 - 1
3 - 2
3 - 3
3 - 3\4
4\3 (соответственно в зависимости от того, что выше строчкой у второго) - и победа обеспечена первому

если первый сделает неверный 4-ый ход, то есть выигрышная стретегия 2-ого
2 - 1
3 - 2
3 - 3
4 - 4
4\5 - 5

-- Вт июл 14, 2009 19:14:04 --

в общем стратегия:
первые ходы первого: 2-3-3, а дальше если после очередного хода второго рыцаря оказывается 18, то надо пришпоривать - соответственно ходы 4-5-6 первого приведут к его победе, а если после хода второго остается 17, то ходы первого 3-4-5 приведут к победе

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

[General]

Да, так.
Ну а теперь большой вопрос: при каких начальных расстояниях выигрышная стратегия есть у первого, а при каких - у второго?

Цитата:

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

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

[anja]

1 - I
2 - I
3 - II
4 - I
5 - I
6 - I
7 - II
8 - I

в общем случае - надо подумать

[TOTAL]

General в сообщении #228756 писал(а):

Хм, странно, видимо рендом вам подыгрывает

Что Вы имеете в виду? Что первому не гарантирован выигрыш с любого первого хода?

[General]

Нет-нет, если первый будет играть правильно, выигрыш гарантирован.

Это я к тому, что после ходов
2 - 1
3 - 2
3 -
комп может ответить как 2, так и 3, и там будут различные варианты выигрышной последовательности ходов для белого.