Шахматы

[AlexLaw]

Пишу свой шахматный движок.
Время от времени возникают затруднения.
Уже какое то время не поддается "алгоритм поиска мата в 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 уровня.
Для теста

[Алексей++]

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

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


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

Изначально в стек помещается затравка- клетка, где сейчас фигура. Затем добавляется элемент с инфой о первом ходе. На основе текущей ветки в ходе создаётся следующий элемент и так далее. Здесь очень просто отступить на 2 хода назад

[AlexLaw]

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

[AlexLaw]

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

[Алексей++]

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

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

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

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

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

[AlexLaw]

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

[Qulac]

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

[Алексей++]

AlexLaw,

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

[AlexLaw]

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

[Алексей++]

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

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

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

[AlexLaw]

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

Добавлено через 3 минуты и 46 секунд:
Кстате если в одной из ветвей есть целевая позиция, то это не соответствует "приехали", т.к. найти целевую
позицию не проблема, проблема найти оптимальный путь.

[Алексей++]

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

[AlexLaw]

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

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

[Алексей++]

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

[Aether]

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

[Алексей++]

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

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

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

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

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

[AlexLaw]

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

[Алексей++]

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

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

[AlexLaw]

Сначала идет 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

[Алексей++]

ход рассуждений по моему алгоритму будет такой (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 ходов просто не строить дерево

[AlexLaw]

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

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

Добавлено через 10 минут и 49 секунд:
Дело в том, что более 4-ходов белых в дереве нет.

[Алексей++]

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

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

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

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

Добавлено через 41 секунду:

Дело в том, что более 4-ходов белых в дереве нет.

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

[AlexLaw]

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

[Алексей++]

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

[AlexLaw]

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

в моём алгоритме есть.

[Aether]

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

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

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

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

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

Добавлено через 7 минут и 18 секунд:

Вопрос стоял найти единственный ход,

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

[Алексей++]

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

[Aether]

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

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

[Алексей++]

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

[x77]

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