шахматы, жадный алгоритм

[Mayor]

на квадратной доске с размером стороны до 10 клеток
размещены в произвольных местах король и противостоящие ему 2  ферзя, один из ферзей должен захавать за минимальное число ходов короля, несмотря на его любые действия

эвристические алгоритмы загона к краю отпадают, тк на центре доски могут быть варианты мата ферзями стоящими по диагонали друг от друга через 1 клетку или по горизонтали\вертикали через 2 клетки и тп

как можно организовать алгоритм перебора и вывести безуспешность любых действий короля?

зы насколько я понимаю жадный алгоритм придется ограничить 7-9 ходами из-за вычислительных ограничений компьютера

насколько уместно альфа бета отсечение для данной задачи? ( запрещается прошляпить возможный  мат за меньшее количество ходов из за эврестического алгоритма)

[Алексей++]

по моему, нужно не более 14 ходов , пример:

Код:

.....<-Ф.
........Ф
........|
....К...V
.........
.........
.........
.........

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

а когда загоним в угол - тут надо подумать ))

[Mayor]

по моему, нужно не более 14 ходов , пример:

Код:

.....<-Ф.
........Ф
........|
....К...V
.........
.........
.........
.........

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

а когда загоним в угол - тут надо подумать ))

еще раз повторюсь 14 ходов не приемлимо для жадного алгоритма - нужно ограничится 7-9 ходами в зависимости от реализации алгоритма, скорости компа

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

[Алексей++]

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

[RXL]

Mayor1, а ферзи знают позицию короля или хотя бы могут узнать "перелет-недолет" в результате хода?

[Алексей++]

вот алгоритм с областями , рекурсивный:

работаем прямоугольником П.

1) П <- вся доска
2) двигаем ферзя ф1 примерно в центр П.

3) король ходит, а если не может - всё, на следующем ходу съедятъ. (*)

4) определение, в какой из четырёх подобластей сейчас король, эту подобласть отныне считаем П.
5) меняем индексы: ф1 становится называться ф2, а ф2 - ф1.
6) идём в пункт 2

[Алексей++]

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

[Sands]

Mayor1, А что говорится по етому поводу в специализированной литературе? Ну тоесть всем известно поведение, к примеру, двух ладей при мате ладьями. Думаю должны быть и общие рекоммендации относительно ферзей. А от етого можно плясать.
Опять же сейчас почему-то рассматриваются варианты когда король бежит подальше от ферзей, а ведь убегать-то можно с умом и на етом выиграть себе пару ходов(ИМХО).

[Mayor]

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

задача: перебрать все варианты в глубину на 7 ходов

хм как-то не задумывался, насчет того знают ли ферзи позицию короля, они просто едят его если представиться возможность ...

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

[Алексей++]

Mayor1, перебрать все варианты в глубину на 7 ходов: 64 в 7 степени байт озу для метода в лоб: это 4096 гиг озу.

в виде дерева ходы займут меньше, конечно Но как прикинуть - не знаю , что то вроде: с каждой из 64 клеток ферзь может подвинуться на одну из (от 21 до 28 клеток). То есть в среднем

64*24*24*24*24*24*24*24 == 273,375 гиг  (и это без учёта информации о связях узлов).

То есть в лоб по любому не выйдет , надо что то хитрое думать

[Sands]

И все таки гугл рулит ))) Вот тут http://golovolomka.hobby.ru/books/gik/04.shtml написан интересный факт

Оказывается, каковы бы ни были размеры доски (она может быть квадратной, прямоугольной и даже бесконечной), и как бы ни располагались в начальный момент два белых ферзя (король им не нужен) и черный король, мат дается не позднее четвертого хода!

Там даже действия приведены. Дальше можно только рассматривать частные случаи, но ето уже дело техники

[Mayor]

И все таки гугл рулит ))) Вот тут http://golovolomka.hobby.ru/books/gik/04.shtml написан интересный факт

Оказывается, каковы бы ни были размеры доски (она может быть квадратной, прямоугольной и даже бесконечной), и как бы ни располагались в начальный момент два белых ферзя (король им не нужен) и черный король, мат дается не позднее четвертого хода!

Там даже действия приведены. Дальше можно только рассматривать частные случаи, но ето уже дело техники

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

[Sands]

А там и не сказано, что четко за 4, сказано не более, чем за 4 - есть разница ))
А почему для бесконечной 5?

[Вахмурка]

 Здаётся мне, что на бесконечной доске короля заматить двумя ферьзями вообще невозможно. Решение задачи заключается в том что бы прижать короля к ближайшиму краю доски используя поочерёдно оба ферьзя. Подсчить количество ходов для этого это уже "дело техники".

[Finch]

Скорее всего тактика нужна такая. Зажать короля в вилку между двумя ферзями по диаганали или вертикали, а затем просто поставить мат.
Что то типа такого

Код:

 
********
********
****Q***
****К***
******Q*
********
********
********

Если делается горизонтальная или вертикальная вилка.
Первый ход ферзя, ставится шах. Король вынужден уйти с горизонтали. Вторая ферзя закрывает через одну горизонталь. Так чтобы у короля было поле для движения. Но по другую сторону от короля. Потом просто короля подвести поближе к одному из ферзей и поставить мат.

[Sands]

Вахмурка, И на бесконечной возможно )) И "край" доски тут ни при чем ))

[Алексей++]

dctвсего 2 шага достаточно для того, чтобы сделать "край" - король будет находится в прямоугольнике, на границу которого нельзя шагнуть

[Вахмурка]

dctвсего 2 шага достаточно для того, чтобы сделать "край" - король будет находится в прямоугольнике, на границу которого нельзя шагнуть

 Это будет не мат, а пат. Меня же интересует вопрос: существует ли тактика придерживаясь которой король может бесконечное количество ходов избегать мата, при условии что игровое поле бесконечно?
Помоему такая тактика есть, значит поставить мат королю можно только подогнав его к краю. Как я уже описал.

[Вад]

От двух ферзей? Мне кажется, нет такой тактики Если ферзь закрыл линию, то король уже не может к нему подойти. То есть, за пару ходов у короля остаётся 1 линия, и оставшимися ходами, насколько я понимаю, его стискивают, как показал Finch

[Mayor]

Здаётся мне, что на бесконечной доске короля заматить двумя ферьзями вообще невозможно. Решение задачи заключается в том что бы прижать короля к ближайшиму краю доски используя поочерёдно оба ферьзя. Подсчить количество ходов для этого это уже "дело техники".

мат в 2 хода можно осуществить если король зажат в коробке 2 на 6 2мя ферзями, другое дело, что не при всякой позиции не на всякой доске можно создать такую коробку за 2 хода, поэтому может потребоваться 5й ход, что бы прижать короля краем этой коробки

[Mayor]

Меня же интересует вопрос: существует ли тактика придерживаясь которой король может бесконечное количество ходов избегать мата, при условии что игровое поле бесконечно?

не существует через 2 хода, он окажется в коробке 2 на бесконечность, еще через ход у края коробки, и через 2 хода последует мат

[Mayor]

хм с переборным алгорнитмом я облажался, так что теперь возникает вопрос как реализовать жадный алгоритм?

[Sands]

Mayor1, Жадный - ето тот, в котором используется "коробка" из ферзей? Я правильно понял?

[Вахмурка]

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

[Basurman]

Мааленькая подсказка: для постановки мата двумя ферзями на бесконечной доске (в центре конечной доски) - один из ферзей должен распологаться ходом коня от короля.
Вот вам печка.
На конечной доске, надо учитывать близость края доски. Ну и начальную позицию.
На доске 10*10 - тупо гоня короля к БЛИЖАЙШЕМУ краю доски получим максимально 6 ходов.

[Вахмурка]

Шесть- много больно. Тут задача это сделать это за минимальное число ходов. Простым методом перебора решить можно , но не хватит вычислительных мощностей. Нужен жадный алгоритм. Один из вариантов отсекать в дереве ходов, цепочки ходов без шаха длинной в три хода как явно безперспективные ( или что-то типа этого) , тогда должно получится. Вообще мне кажется что задачу даже для бесконечной доски можно свести к некой элементарной на конечной доске. Хотя бы потому что король за пять ходов далеко не уйдёт, а ферзям нет разницы конечная доска или нет , перемахнуть она могут любую доску за один ход.

[Basurman]

Извините, но мне кажется, что процесс решения задачи свёлся к принципу - хочу, что бы было красиво.
Попробую переформулировать задачу.
На неограниченной (пускай она будет бесконечной, кубической, или шарообразной) шахматной доске используя двух белых ферзей заматовать чёрного короля за минимальное количество ходов.
Соблюдаются шахматные правила - белые начинают, перемещение фигур, король не может встать под удар ...
Начальное положение фигур случайно, опять же соблюдая правило - король не может стоять под ударом.
Мне кажется - это будет пригодная формулировка. Кстати на ограниченной доске агоритм будет усложняться из за необходимости проверки границ.
Продолжу подготовку к построению алгоритма для бесконечной доски.
  Ограниченная часть описания объекта ферзь:
  Текущая позиция - x.y - знакомый тип точка.
  Следущая позиция (позиция куда ферзь может переместиться за один ход) - (x+k).(y+m) - здесь надо учесть занятые и загороженные другими фигурами позиции.
  Ограничения к k и m - (k=0) and (m<>0); (m=0) and (k<>0); (abs(k)=abs(m))<>0.
  -----
Так же опишем объект король.
Теперь закурим и прикинем - доска неограничена и бесконечна, следовательно количество начальных позиций тоже бесконечно. А как насчёт заключительных, где король заматован?
А их всего 32. И характеризуются они следущим:
К(x.y), Ф1((x+a).(y+b)), Ф2((x+c).(y+d)) - где a,b зависят от x,y и c,d уже зависят от a,b. Причём если одна пара коэффициентов во множестве [-1..1], то вторая пара позволяет расположить Ф1 или Ф2 ходом коня от К, и наоборот.
Кстати оперировать лучше полуходами. Полуход - перемещение одной из фигур, белой или чёрной. Полуходы делаются по очереди, полуход белых + полуход чёрных = ход.
Зависимость коэффициентов посчитайте сами.
Итак имеются жёстко определённые характеристикм конечной позиции.
Определим характеристики допустимой предыдущей позиции и т.д.
На каком шагу коэффициенты a,b,c,d перестанут зависить от x,y? Вот так и справимся с начальной бесконечностью и простым перебором.
Мне кажется это будет не только красиво, но и весьма функционально.