Выглядело все это примерно так (смотрю код на C, но уже не совсем хорошо его помню):
вызывается рекурсивная процедура искать_мат_за_белых(число_ходов, нет, нет)
сами процедуры на псевдокоде примерно такие
искать_мат_за_белых(число_ходов, угрозы, варианты)
{
сгенерированные_ходы := генерировать_все_ходы(белые)
если (сгенерированные_ходы пусто) то возврат мата_нет
состояние := мат_не_найден
цикл_по (вариант в (варианты и угрозы))
{
ход := первый_ход(вариант);
если (ход в (сгенерированные_ходы))
{
сделать (ход)
результат := искать_защиту_за_черных(число_ходов-1,
дерево_вариантов[ход].угрозы,
дерево_вариантов[ход].ответы);
вернуть(ход)
если (результат = мат_есть)
{
удалить(все_варианты)
состояние :=вариант_проходит;
}
если (результат = мата_нет)
{
удалить(текущий_вариант)
}
если (результат = мат_есть_с_вариантами)
{
добавить_поправки_в_ответ
состояние := вариант_проходит_с_поправками
}
}
если состояние = вариант_проходит
выход_из_цикла
}
если состояние = вариант_проходит
возврат мат_есть
если состояние = вариант_проходит_с_поправками
возврат мат_есть_с_вариантами
цикл_по (ход в (сгенерированные_ходы))
{
сделать(ход)
если (число_ходов > 1 и нет_шаха_черным)
{
результат := искать_мат_за_белых (число_ходов-1, нет, нет)
дерево_вариантов[ход].угрозы := результат
}
результат := искать_защиту_за_черных(число_ходов-1,
дерево_вариантов[ход].угрозы,
нет);
вернуть(ход)
если результат = мата_нет
удалить(текущий_вариант)
если результат = мат_есть
{
добавить_текущий_вариант_в_дерево
состояние := мат_найден // может быть, есть и другие ходы, которые приводят к мату
}
}
если состояние = мат_не_найден
возврат мата_нет
если состояние = мат_найден
возврат мат_есть_с_вариантами
}
искать_защиту_за_черных(число_ходов, угрозы, ответы)
{
если число_ходов = 0
если мат_на_доске то возврат мат_есть иначе возврат мата_нет
сгенерированные_ходы := генерировать_все_ходы(черные)
если (сгенерированные_ходы пусто) то если шах возврат мат_есть иначе возврат мата_нет
цикл_по (ход в (сгенерированные_ходы))
{
сделать(ход)
если ход в (ответы)
результат := искать_мат_за_белых (число_ходов, угрозы, дерево_вариантов[ход].ответы)
иначе
результат := искать_мат_за_белых (число_ходов, угрозы, нет)
вернуть(ход)
если (результат = мата_нет)
{
удалить(все_варианты)
возврат мата_нет
}
если (результат = мат_есть)
{
удалить(текущий_вариант)
}
если (результат = мат_есть_с_вариантами)
{
добавить_вариант_в_ответ
}
}
если были_добавлены_варианты_в_ответ
возврат мат_есть_с_вариантами
иначе
возврат мат_есть
}
Элемент дерева вариантов имеет следующую структуру:
- с какого поля ход
- на какое поле ход
- если не 0, то во что превращается пешка
- указатель на следующий вариант в списке
- указатель на варианты-угрозы
- указатель на варианты-ответы
