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

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

ru
Offline Offline

« : 14-05-2016 15:38 » 

Пишу свой шахматный движок.
Время от времени возникают затруднения.
Уже какое то время не поддается "алгоритм поиска мата в N ходов".
Высказывание1.
Найти такой ход 1-го игрока, при котором на каждый ход 2-го игрока
верно Высказывание1, пока не достигнута max глубина поиска или не найдена
целевая позиция (мат,пат).
В коде я представляю это так-
перебор в губину на N ходов
Код: (Delphi)
//полный перебор в глубину
procedure analizPosition
//генериреуем все ходы в данной позиции
AllAttack(WP,BP,WP[0],col,false);
mat:= returnMat();
           case mat of
              1:begin //мат черным
              end;
              2,0:begin//0-пат,2-мат белым
              end;
            end;
 if d>=dmax then  begin //еслли достигнута предельная глубина
   Exit;
 end;
 //Запоминаем все ходы и фигуры в данной позиции в зависимости от цвета
//Перебираем все фигуры одного цвета
for i := kFigure - 1 downto 0 do begin
  for j := 1 to nMove do begin//перебираем все ходы одной фигуры          
            // пешки на последней горизонтали          
       for x := 1 to HiP do begin                  
         analizPosition(WPieceNew, BPieceNew,color, d+1);//делаем ответные ходы
         if comback then begin
          comback:=false;
          exit;
         end;
         if SM<>'-' then exit;
           if mat=1 then begin
             mat:=-1;
             exit;
           end;
        end; //x
  end;//j
end;//i
 comback:=true;
if d=2 then begin
SM:=StrMove;
end;
end;

Т.е. если циклы полностью прокручены- comback:=true;
Значит предыдущий ход противника был лучшим и поднимаемся из рекурсии сразу на 2 уровня.
Для теста

* testProjectGroup180416.zip (830.61 Кб - загружено 53 раз.)
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #1 : 15-05-2016 07:39 » 

Переделай так, чтобы работать с "ручным" стеком: элемент стека пусть содержит

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


И для отладки удобнее )

Изначально в стек помещается затравка- клетка, где сейчас фигура. Затем добавляется элемент с инфой о первом ходе. На основе текущей ветки в ходе создаётся следующий элемент и так далее. Здесь очень просто отступить на 2 хода назад
« Последнее редактирование: 15-05-2016 07:42 от Алексей++ » Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #2 : 15-05-2016 12:56 » 

Алгоритм и так работает.
Из всех задач нахождения мата в 2,3,4 хода,которые находятся в той же папке testProjectGroup180416(fen.txt)-90%
решаются с помощью такого простого алгоритма.
Весь алгоритм заключается практически в одной строке
comback:=true;
Вы наверно не смотрели исходники, которые я выложил.
Ваше предложение не дает ответ на вопрос-"алгоритм поиска мата в N ходов"
Записан
AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #3 : 15-05-2016 13:07 » 

Пример нахождения мата в 4 хода

* мат4хода.mp4 (723.4 Кб - загружено 57 раз.)
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #4 : 15-05-2016 13:22 » 

AlexLaw, я не смотрел исходники - никто их не смотрел, уверен на 100% в этом. кроме того, я не знаком с дельфи

ок, "алгоритм поиска мата в N ходов"

нужно проанализировать N состояний
1) состояние N0 - имеется один элемент - сама доска с F фигурами
2) состояние N1- список из как минимум F досок (на самом деле раз в 100 побольше) с одиночным ходом одной из фигур каждая.  Для каждой доски проверяем, находится ли король под ударом и может ли он сделать куда-либо шаг. Там же проверяется пат.
3) состояние N2 - для всех досок из списка N1 делается то же самое, что и с N0.

и так - насколько хватит памяти и/или диска , либо не будет найден мат или пат

Алгоритм будет несложный, но очень ресурсоёмкий из-за особенностей самой игры.
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #5 : 15-05-2016 14:03 » 

Дело в том, что наверное я озвучил задачу не совсем понятно.
А суть поставленоой задачи в этом.
Как определить, что данный 1-й ход белых приведет к мату черным  в N ходов,при любой игре черных?
Математическая модель какая?

* matNmoves.png (87.38 Кб - загружено 59 раз.)
Записан
Qulac
Постоялец

ru
Offline Offline

« Ответ #6 : 15-05-2016 14:23 » 

AlexLaw, если все партии после ходя белых заканчиваться поражением черных в N ходов, то этот ход белых будет искомым ходом.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #7 : 15-05-2016 14:32 » 

AlexLaw,

перебор всех вариантов перемещений далее и анализ
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #8 : 15-05-2016 14:40 » 

Но это понятно.
Логически я это описал в 1 посте-Высказывание1.
А математически это вопрос.
Допустим мат в 2 хода.
1.опускаемся по левой ветке на глубину d=3
      0
    !  ! 
    0
    !
    0
  ! ! !
  0 0 0
Перебераем все ходы белых, если нет мат, то не рассматриваем больше ответы черных на первый ход
а берем следующий, если есть мат, то рассматриваем следующий ответ черных и т.д.
А если мат допустим в 4 хода, то не просто отследить всю логику.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #9 : 15-05-2016 14:47 » 

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

Так вот, пусть анализ некоего узла показывает, что там - пат. Значит - приехали.

Пусть там шах - идём анализировать дочерние узлы. Если их нету (то есть, король не может никуда увернуться) - это мат. Если есть, то N+1
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #10 : 15-05-2016 15:00 » 

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

Добавлено через 3 минуты и 46 секунд:
Кстате если в одной из ветвей есть целевая позиция, то это не соответствует "приехали", т.к. найти целевую
позицию не проблема, проблема найти оптимальный путь.
« Последнее редактирование: 15-05-2016 15:04 от AlexLaw » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #11 : 15-05-2016 15:12 » 

AlexLaw, от найденного шагаешь обратно к корню дерева - это будет путь. Перебором все такие пути найдутся рано или поздно. Список таких путей тебе и нужен
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #12 : 15-05-2016 15:24 » 

Так вот и пришли с чего я начал.
В начале (пост1) я и показал решение, но есть позиции, где этот алгоритм работает не так,
как хотелось.
Например-5n1n/3B4/p2k4/2R1Np1K/1PP1p1PB/2N5/3P1P2/3r1r2 w - - 0 1

Добавлено через 18 минут и 16 секунд:
Вот голая программа, без исходников, для теста.
Задачи брал отсюда http://chessproblem.ru/


* test.zip (807.54 Кб - загружено 58 раз.)
« Последнее редактирование: 15-05-2016 15:42 от AlexLaw » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #13 : 15-05-2016 15:51 » 

AlexLaw, алгоритм может быть правильный, а "не так" может работать реализация Улыбаюсь

Записан

Aether
Молодой специалист

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

« Ответ #14 : 15-05-2016 19:19 » 

Алгоритм упирается в построение того самого правильного дерева ходов для конкретного расположения фигур на доске. Мат - состояние короля под ударом, когда никакое следующее действие не способно устранить удар. Пат - состояние при котором нет возможности сделать ход по причине отсутствия возможности передвижения, либо по причине, что любое перемещение ставит короля под удар. При этом сам король в текущем положении под ударом не находится. В одном раскладе фигур может быть мат, может быть пат, и может не быть их обоих. Мат и пат - это конечные точки дерева. Отсутствие их - продолжение анализа.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #15 : 16-05-2016 04:48 » 

Aether, уточни: в чём заключается твой вопрос?  В выборе/составлении алгоритма или в поиске опечатки в коде на дельфи ?  Для первого случая я свои мысли высказал (и я не вижу, где алгоритм упирается), во втором случае я не смогу помочь.

Или где именно вопрос ?

Вроде всё прозрачно - дерево из узлов(досок), связанных рёбрами(ходами). Проанализировать статус отдельно взятого узла - отдельная задача, но несложная. Это всего 4 состояния:

s1-  есть шах, но уход короля возможен  (продолжать анализ)
s2 - есть шах, но уход короля невозможен (мат)
s3 - нет шаха, но и сделать ход нечем (пат)
s4 - нет шаха, и можно сделать ход (продолжать анализ)

если узел с состоянием s2 имеет глубину N , то это одно из решений. Остаётся лишь построить путь от узла к корню и перевернуть его наоборот
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #16 : 16-05-2016 06:51 » 

Здравствуйте.
У меня сегодня выходной!
А теперь к теме.
Почитал все рассуждения и понял, что мы не умеем выражать свои мысли.
Каждый вроде говорит правильно, но что хочет сказать не понятно.
Вот попробуйте пользуясь своими рассуждениями дать ответ на вопрос.
Какой ход белых первый.
Даю полное дерево перебора.
Я надеюсь, что файл нагляден, и готов для анализа.

* Tree.txt (911.83 Кб - загружено 54 раз.)
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #17 : 16-05-2016 07:29 » 

AlexLaw, я не компьютер, чтобы в уме всё это охватить Отлично  Формат такой записи тоже не знаю

Чем конкретно мой алгоритм противоречит поиску решения?
Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #18 : 16-05-2016 07:40 » 

Сначала идет FEN-нотация (можно скопировать и вставить в мою программу),
затем ходы из начальной позиции эту позицию (можно подвигать фигуры в проге).
Посмотрите строки 486,2055,5549,6334,8419,9169,9945,10348,11472,-мат
Остальные строки можете удалить.
И дайте ход ваших рассуждений и ответ на вопрос.

Добавлено через 9 минут и 3 секунды:
Вот, чтобы легче было
Код: (Text)
Начальная позиция
8/8/2P5/8/8/8/2K5/k1N5 w - - 0 1 мат в 4 хода
полное дерево перебора
b-ход черных
w-ход белых
X мат
= пат
R7/8/8/8/8/1N6/k1K5/8 b -  c1-b3  a1-a2  c6-c7  a2-a3  c7-c8Л a3-a2  c8-a8 X
R7/8/8/8/8/8/k1K5/8 b -  c1-a2  a1-a2  c6-c7  a2-a3  c7-c8Л a3-a2  c8-a8 X
8/8/Q7/8/8/8/k1K1N3/8 b -  c1-e2  a1-a2  c6-c7  a2-a3  c7-c8Ф a3-a2  c8-a6 X
8/8/Q7/8/8/3N4/k1K5/8 b -  c1-d3  a1-a2  c6-c7  a2-a3  c7-c8Ф a3-a2  c8-a6 X
R7/8/8/8/8/8/k1K1N3/8 b -  c1-e2  a1-a2  c6-c7  a2-a3  c7-c8Л a3-a2  c8-a8 X
R7/8/8/8/8/3N4/k1K5/8 b -  c1-d3  a1-a2  c6-c7  a2-a3  c7-c8Л a3-a2  c8-a8 X
8/8/Q7/8/8/1N6/k1K5/8 b -  c1-b3  a1-a2  c6-c7  a2-a3  c7-c8Ф a3-a2  c8-a6 X
8/8/Q7/8/k7/3N4/2K5/8 b -  c1-d3  a1-a2  c6-c7  a2-a3  c7-c8Ф a3-a4  c8-a6 X
8/8/Q7/8/8/8/k1K5/8 b -  c1-a2  a1-a2  c6-c7  a2-a3  c7-c8Ф a3-a2  c8-a6 X
« Последнее редактирование: 16-05-2016 07:49 от AlexLaw » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #19 : 16-05-2016 08:09 » 

ход рассуждений по моему алгоритму будет такой (Nx - это узел дерева)
Код: (Text)
8/8/2P5/8/8/8/2K5/k1N5 w N0 Начальная позиция
R7/8/8/8/8/1N6/k1K5/8 b  N1
... w                    N2
R7/8/8/8/8/8/k1K5/8 b    N3
... w                    N4
8/8/Q7/8/8/8/k1K1N3/8 b  N5
... w                    N6
8/8/Q7/8/8/3N4/k1K5/8 b  N7
... w                    N8
R7/8/8/8/8/8/k1K1N3/8 b  N9
... w                    N10
R7/8/8/8/8/3N4/k1K5/8 b  N11
... w                    N12
8/8/Q7/8/8/1N6/k1K5/8 b  N13
... w                    N14
8/8/Q7/8/k7/3N4/2K5/8 b  N15
... w                    N16
8/8/Q7/8/8/8/k1K5/8 b    N17  мат чёрным


это означает, что найдено одно из решений, а именно цепь досок

N0-N1-....-N16-N17

проверяем количество ходов белых (оно тут, насколько понимаю, 9, не равно 4, значит, это решение откинуто)

алгоритм отступает на доску N16 и продолжает оттуда перебор ходов


Даже не  так: в процессе поиска сразу нужно было учесть, что нужно всего 4 хода, и до 9 ходов просто не строить дерево

« Последнее редактирование: 16-05-2016 08:10 от Алексей++ » Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #20 : 16-05-2016 08:30 » 

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

Добавлено через 10 минут и 49 секунд:
Дело в том, что более 4-ходов белых в дереве нет. Улыбаюсь
« Последнее редактирование: 16-05-2016 08:41 от AlexLaw » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #21 : 16-05-2016 08:43 » 

AlexLaw, я имел в виду, что эти 18 досок - последовательные ходы. Расписывать и проверять эти ходы мне нет времени

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

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

Ответ я не могу дать - я не компьютер. Для этого мне пришлось бы нужно реализовывать алгоритм в коде и запускать эту программу )

Добавлено через 41 секунду:
Дело в том, что более 4-ходов белых в дереве нет. Улыбаюсь
в моём алгоритме есть. Ходы в дереве чередуются, а то, что в примере прописано - я просто не смотрел, что там за ходы. Это лишь пример
« Последнее редактирование: 16-05-2016 08:45 от Алексей++ » Записан

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #22 : 16-05-2016 08:46 » 

Вопрос стоял найти единственный ход, т. к. конечная позиция зависит еще от хода
черных, и нужно принудить их к той конечной позиции, которая нам нужна, помимо их воли.
Спасибо за дисскусию.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #23 : 16-05-2016 08:49 » 

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

AlexLaw
Интересующийся

ru
Offline Offline

« Ответ #24 : 16-05-2016 08:52 » 

Даже не  так: в процессе поиска сразу нужно было учесть, что нужно всего 4 хода, и до 9 ходов просто не строить дерево
в моём алгоритме есть.
Записан
Aether
Молодой специалист

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

« Ответ #25 : 16-05-2016 08:56 » 

Aether, уточни: в чём заключается твой вопрос?

Вроде всё прозрачно - дерево из узлов(досок), связанных рёбрами(ходами). Проанализировать статус отдельно взятого узла - отдельная задача, но несложная. Это всего 4 состояния:

s1-  есть шах, но уход короля возможен  (продолжать анализ)
s2 - есть шах, но уход короля невозможен (мат)
s3 - нет шаха, но и сделать ход нечем (пат)
s4 - нет шаха, и можно сделать ход (продолжать анализ)

если узел с состоянием s2 имеет глубину N , то это одно из решений. Остаётся лишь построить путь от узла к корню и перевернуть его наоборот
Это не вопрос - мысли вслух.) Пытаюсь сам понять. Задача анализа на мат/пат не стоит отдельно от поиска возможных продолжений партии, просто это один из вариантов окончания какой-либо ветви дерева. Вопрос первый в том, правильно ли это дерево строится, правильно ли находятся варианты ходов?

Добавлено через 7 минут и 18 секунд:
Вопрос стоял найти единственный ход,
Даже ближайший путь к мату может оказаться не единственным, просто алгоритм выберет ближайший исходя из своей реализации, например, будет перебор фигур в том или ином направлении. Если построить полное дерево ходов, то в нём будут абсолютно все возможные варианты, естественно, строить его получится лишь на определённую глубину, иначе не хватит времени собственной жизни на ожидание результата. Если искомый, тестовый, заранее правильный вариант отсутствует в переборе - проверяем перебор в первую очередь.
« Последнее редактирование: 16-05-2016 09:03 от Aether » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #26 : 16-05-2016 09:04 » 

Aether, предлагаешь проверять код автора в прицепе к первому посту ? )) Я к такому подвигу не готов
Записан

Aether
Молодой специалист

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

« Ответ #27 : 16-05-2016 09:15 » 

Aether, предлагаешь проверять код автора в прицепе к первому посту ? )) Я к такому подвигу не готов
Я тоже, поэтому и предлагаю автору проверить код самостоятельно. Из опубликованного кусочка на Паскале многое непонятно, например, определение ходов у фигур.
Ещё интересный нюанс, будем конкретное положение партии называть State. Предположим мы начинаем со State[0], и в ходе первого анализа найдены возможные варианты State[0-1], [0-2], [0-3]. Моё мнение - их стоит как-то сохранять, погружение в многократно вложенные циклы само по себе может спровоцировать ошибки. Потом будет State[0-1-5]... State[0-1-5-6-78-1]... Прогрессия требований геометрическая, и программа должна уметь эти структуры обрабатывать без ошибок.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

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


« Ответ #28 : 16-05-2016 09:24 » 

Aether, при построении дерева в узле нужно хранить не только доску, но и список всех возможных новых текущих ходов - их можно помечать опробованными, если в ту ветку заходили. Множества Вложенных циклов не будет, вижу один цикл - обработка элемента дерева из стека + проверка ситуации на доске - это ещё два цикла. Итого их намечается три вложенных
Записан

x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #29 : 24-08-2016 18:25 » new

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

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines