Раздел «Образование».FIVTLecturesTerm4Lecture02:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Лекция 2. Задача "Эндшпиль"

Условие задачи: PROBLEM:048

Задача "Эндшпиль" решается методом динамического программирования. Множество возможных состояний в малофигурных эндшпилях оказывается небольшим и есть возможность рассматривать хрнаить данные для каждого из возможных состояний.

Состояние - это

В нашем случае состояние определяется положением двух фигур — черного короля и белого ферзя. Всего 64*64 варианта положений двух фигур (мы пока небудем исключать различные запретные ситуации, когда две фигуры находятся в одной клетке). Еще флажок хода. В итоге имеем 64*64*2 = 8192 ситуаций.

Каждая из этих ситуаций будет вершиной в графе игры. Граф ориентированный. Рёбра в этом графе соответствуют возможным ходам. Вершины, из которых ходит белый ферзь, назовем белыми, а вершины, из которых ходит король — черными. Граф двудольный, так как все рёбра соединяют вершины разных цветов.

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