Программа поиска мата в 3 хода (шахматы)

← →
Vasya.ru (2004-10-20 21:47) [0]

Нужно написать программу, ищущую мат в 1 - 2 - 3 хода в любой шахматной позиции. Где можно найти решение/алгоритмы этой задачи?

← →
KilkennyCat © (2004-10-20 21:49) [1]

и даже в позиции:
Белые: Король А1
Черные: Король А3

← →
SergP © (2004-10-20 23:08) [2]

> [1] KilkennyCat © (20.10.04 21:49)
> и даже в позиции:
> Белые: Король А1
> Черные: Король А3

В сабжевом посте было написано "ищущую мат в 1 - 2 - 3 хода" ,
а искать и находить - это разные вещи... :-)))

← →
SergP © (2004-10-20 23:09) [3]

← →
Gero © (2004-10-20 23:29) [4]

> Где можно найти решение/алгоритмы этой задачи?

Нигде.

← →
KilkennyCat © (2004-10-21 00:12) [5]

> SergP © (20.10.04 23:08) [2]

Тогда автор - из Маклаудов ;)

← →
GuAV © (2004-10-21 00:15) [6]

В TP7.0 есть демка - шахматы. на Turbo Vision и под Windows.

← →
KilkennyCat © (2004-10-21 00:18) [7]

вообще-то, число заказанных ситуаций конечно. Так что можно просто их все описать. в каком-нить массиве. Что там за терабайтами идет?

← →
GuAV © (2004-10-21 00:47) [8]

KilkennyCat © (21.10.04 0:18) [7]
Что там за терабайтами идет?
function IntToSizeInUnits(I: Int64): string; const Units: array[0..6] of string = ("Б","кБ","МБ","ГБ","ТБ","ПБ","ЭБ"); var J: Integer; begin J := 0; while I >= (1 shl 10) do begin Inc(J); I := I shr 10; end; Result := IntToStr(I) + " " + Units[J]; end;

← →
VMcL © (2004-10-21 07:47) [9]

>>KilkennyCat © (21.10.04 00:18) [7]

"пета-" (10^15), потом "экза-" (10^18).

← →
SergP © (2004-10-21 07:49) [10]

Можно сделать программу тупо перебирающую все возможные варианты для 3 ходов, но думать прога будет долго. :-))

← →
VMcL © (2004-10-21 08:09) [11]

>>SergP © (21.10.04 07:49) [10]

Можно прикинуть ориентировочное количество вариантов на один ход. Больше всего вариантов, как походить, у ферзя - максимально 3 * 7 + 6 = 27, если он стоит в одной из четырех центральных клеток и все варианты хода для него доступны. Фигур максимально 16 с одной стороны. Итого на каждый полуход (т. е. ход одной из сторон) получаем верхний предел в 16 * 27 = 432 варианта. Реальное количество вариантов на полуход намного меньше, поскольку не все ходы доступны и другие фигуры имеют меньше возможностей походить. Для полного хода получаем 432 * 2 = 864. На три полных хода: 864 ^ 3 = 644 972 544 варианта. Это самый, самый верхний предел (если я все правильно посчитал). На самом же деле вариантов будет намного меньше. Можно посчитать точнее хотя бы, если учесть максимально возможное количество ходов для каждой из фигур.

← →
KilkennyCat © (2004-10-21 08:38) [12]

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

← →
KilkennyCat © (2004-10-21 08:43) [13]

вот, выдержкы из сети:

"Существует 1 695 188 229 100 544 * 10^12 вариантов только первых десяти ходов в шахматах.
Общее число возможных вариантов шахматных партий равно 2*10^116"

"число возможных игровых вариантов невероятно велико : подсчитано, что оно составляет 10750, или 1 с последующими 750 нолями."

> [12] KilkennyCat © (21.10.04 08:38)
> но в конечном итоге вариантов намного больше, так как посчитаны
> варианты трех ходов, но не для всех позиций.

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

> SergP © (21.10.04 08:44) [14]

остальные нас не интересуют только в данный момент. в следующий раз юзер задаст другую позицию.

>>KilkennyCat © (21.10.04 08:43) [13]

Ссылку в студию.

>1 695 188 229 100 544 * 10^12

"~1,695*10^27" не проще написать?

>только первых десяти ходов в шахматах

10 и 3 - сравнил ... с пальцем. Задача: найти мат в три хода. Все дальнейшие ходы нас не интересуют. Если не удалось найти, значит ответ отрицательный.

Далее. Есть еще одна проблема. Даже если мы нашли цепочку (или несколько цепочек) ходов приводящую к мату (трехэтажному:), то это еще не значит, что соперник будет ходит так, как мы от него ожидаем. Нужно учитывать то, что нам нужно его вынудить походить так, чтобы поставить ему мат.

Да при чем тут десять. Я думаю тружно представить себе позицию, где возможно более 500 ходов. Т.о. все равно не больше 10^8, а это реально перебором найти за разумное время.

Программа поиска мата в 3 хода (шахматы) Найти похожие ветки