Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: шахматы, жадный алгоритм  (Прочитано 35113 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 12-04-2008 16:33 » 

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

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

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

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

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

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 12-04-2008 18:07 » 

по моему, нужно не более 14 ходов , пример:
Код:
.....<-Ф.
........Ф
........|
....К...V
.........
.........
.........
.........

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

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

Mayor
Специалист

ru
Offline Offline

« Ответ #2 : 13-04-2008 03:46 » 

по моему, нужно не более 14 ходов , пример:
Код:
.....<-Ф.
........Ф
........|
....К...V
.........
.........
.........
.........

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

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


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

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

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 13-04-2008 05:50 » 

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

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 13-04-2008 07:32 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 13-04-2008 11:51 » 

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

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

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

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

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

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 13-04-2008 11:54 » 

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

Sands
Помогающий

ua
Offline Offline

« Ответ #7 : 13-04-2008 21:31 » 

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

ru
Offline Offline

« Ответ #8 : 14-04-2008 13:22 » 

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

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

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

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

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 14-04-2008 14:34 » 

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

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

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

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

Sands
Помогающий

ua
Offline Offline

« Ответ #10 : 14-04-2008 15:10 » 

И все таки гугл рулит ))) Вот тут http://golovolomka.hobby.ru/books/gik/04.shtml написан интересный факт
Цитата
Оказывается, каковы бы ни были размеры доски (она может быть квадратной, прямоугольной и даже бесконечной), и как бы ни располагались в начальный момент два белых ферзя (король им не нужен) и черный король, мат дается не позднее четвертого хода!
Там даже действия приведены. Дальше можно только рассматривать частные случаи, но ето уже дело техники
Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #11 : 14-04-2008 18:26 » 

И все таки гугл рулит ))) Вот тут http://golovolomka.hobby.ru/books/gik/04.shtml написан интересный факт
Цитата
Оказывается, каковы бы ни были размеры доски (она может быть квадратной, прямоугольной и даже бесконечной), и как бы ни располагались в начальный момент два белых ферзя (король им не нужен) и черный король, мат дается не позднее четвертого хода!
Там даже действия приведены. Дальше можно только рассматривать частные случаи, но ето уже дело техники

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

1n c0de we trust
Sands
Помогающий

ua
Offline Offline

« Ответ #12 : 14-04-2008 19:03 » 

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

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #13 : 14-04-2008 22:19 » 

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

Программа – это мысли спрессованные в код.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #14 : 14-04-2008 22:27 » 

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

********
********
****Q***
****К***
******Q*
********
********
********
Если делается горизонтальная или вертикальная вилка.
Первый ход ферзя, ставится шах. Король вынужден уйти с горизонтали. Вторая ферзя закрывает через одну горизонталь. Так чтобы у короля было поле для движения. Но по другую сторону от короля. Потом просто короля подвести поближе к одному из ферзей и поставить мат.
« Последнее редактирование: 14-04-2008 22:38 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Sands
Помогающий

ua
Offline Offline

« Ответ #15 : 15-04-2008 05:29 » 

Вахмурка, И на бесконечной возможно )) И "край" доски тут ни при чем ))
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #16 : 15-04-2008 05:50 » 

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

Вахмурка
Помогающий

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #17 : 15-04-2008 13:11 » 

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

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

Программа – это мысли спрессованные в код.
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 15-04-2008 13:17 » 

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

ru
Offline Offline

« Ответ #19 : 15-04-2008 13:24 » 

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

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

1n c0de we trust
Mayor
Специалист

ru
Offline Offline

« Ответ #20 : 15-04-2008 13:27 » 

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

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

1n c0de we trust
Mayor
Специалист

ru
Offline Offline

« Ответ #21 : 15-04-2008 13:30 » 

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

1n c0de we trust
Sands
Помогающий

ua
Offline Offline

« Ответ #22 : 15-04-2008 14:28 » 

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

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #23 : 15-04-2008 17:01 » 

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

Программа – это мысли спрессованные в код.
Basurman
Опытный

ru
Offline Offline
Пол: Мужской

« Ответ #24 : 29-07-2008 22:18 » 

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

ru
Offline Offline
Пол: Мужской
Программист


WWW
« Ответ #25 : 30-07-2008 05:33 » 

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

Программа – это мысли спрессованные в код.
Basurman
Опытный

ru
Offline Offline
Пол: Мужской

« Ответ #26 : 30-07-2008 11:18 » new

Извините, но мне кажется, что процесс решения задачи свёлся к принципу - хочу, что бы было красиво.
Попробую переформулировать задачу.
На неограниченной (пускай она будет бесконечной, кубической, или шарообразной) шахматной доске используя двух белых ферзей заматовать чёрного короля за минимальное количество ходов.
Соблюдаются шахматные правила - белые начинают, перемещение фигур, король не может встать под удар ...
Начальное положение фигур случайно, опять же соблюдая правило - король не может стоять под ударом.
Мне кажется - это будет пригодная формулировка. Кстати на ограниченной доске агоритм будет усложняться из за необходимости проверки границ.
Продолжу подготовку к построению алгоритма для бесконечной доски.
  Ограниченная часть описания объекта ферзь:
  Текущая позиция - 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? Вот так и справимся с начальной бесконечностью и простым перебором.
Мне кажется это будет не только красиво, но и весьма функционально.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines