Костёр 1986-03, страница 44

25

2,4 жд„

2*г

25 t

20

программиста стал набрасывать на бумаге рисунок, не прерывая рассказ.

Похоже на дерево, метил я,— только вверх ногами.

Да. Такая схема и называется «деревом вариантов». Наша программа «строит» его заново для каждой позиции при своем ходе. Она просматривает по очереди свои возможные ходы, все ответы «овечек», свои следующие ответные реплики и так далее до глубины в 4 своих хода. В конце каждого такого варианта определяется соответствие возникающей позиции «целевой» для игры. ,

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

d8—е7?

— Это объясняется порядком перебора ходов, принятым в программе: для «волка» возможные ходы рассматриваются с левого «нижнего» поля /с7/ против часовой стрелки; есть определенный порядок просмотра и для «овечек». Пока соответствующие варианты не

просчитаны машиной до конца, ^! %

то есть на 4 хода, другие первые ходы ждут своей очереди. А поскольку в этой позиции, Саша указал на диаграмму, уже просмотр вариантов после 23. ...d8—с7 привел машину к цели, то другие пути программа не стала изучать. Если бы ни один из первых ходов не приводил в конце расчета к выигрышу, был бы выбран первый из рассмотренных.

По-моему, такой подход неэкономичен,— предположил я.— Если можно выиграть быст-то так и надо делать. Согласен. Но тогда усложняется программа, ведь машине надо запоминать при всех возможных продолжениях, сколько ходов требуется для достижения цели. В такой простой игре, как «Волк и овцы», это не требуется. В принципе, улучшив нашу программу, можно заставить ее считать до конца партии, если не ограничить глубину просмотра четырьмя ходами. Кстати, так мы и сделали в программе игры «Крестики-нолики», но там конец ближе.

Значит, у вас есть и другие играющие программы? оживился я.

Есть, еще несколько:

«морской бой», «шашки» /правда, пока слабая/...

— ...«шахматы»...— вставил я, втайне надеясь взять реванш у машины.

Нет, за шахматную программу мы не брались.

— Почему? Доска та же, только фигур чуть больше.

— Разница не только в количестве, но и в качестве. Во-первых, в шахматной игре цель /дать мат/ значительно отдаленнее, во-вторых, вариантов в «дереве» неизмеримо больше.

— Ну и что? — возразил я.— Ты сам рассказывал по пути сюда, что ваша ЭВМ может за одну секунду проделать сотни тысяч действий. Будет отвечать на ход не сразу, а через пару минут или чуть позже...

— Не через пару минут, и даже не через пару часов, если заставить ее считать до конца. Математики определили, что на полный перебор вариантов для обычного многофигурного положения из середины шахматной партии машине потребовались бы многие миллионы. /!/ лет.

— Выходит, и смысла нет учить машину игре в шахматы?

39