|
Главная 5 в ряд
|
Описание алгоритма компьютерного игрока
Общее описание проблемыЕсли рассматривать игры с малым количеством воможных ходов и небольшой длительностью (например, крестики-нолики 3 на 3), то поиск оптимальной стратегии больших проблем не вызывает. Формируем массив всевозможных первых ходов, для каждого элемента смотрим на ситуацию и формируем масси ходов, возможных в этой ситуации и т.д. Получаем дерево, выбираем в нём ту ветку, которая ведёт к выигрышу при любых действиях соперника (для варианта 3 на 3 такой стратегии не существует, если начинать с пустой доски, но в некоторых ситуациях после некоторых ходов бывает, что она есть). В крайнем случае ищем непроигрышную стратегию. Так или иначе можно увидеть все варианты, посмотреть, что где, и выбрать (если рассмотреть всевозможные последовательности ходов, то их получится не больше, чем 9!=362880, что не очень-то и много). Хуже обстоит дело с играми, в которых есть куча возможностей, таких как игра в крестики-нолики на достаточно большом поле. В общем случае, если убрать на время из рассмотрения те узлы, которые приводят к выигрышным ситуациям, и, следовательно, от них дальше ветки идти не будут (а в течение первых 8 ходов в "5 в ряд" в принципе не может быть чьей-либо победы - каждый игрок сделает всего по 4 хода), то рост количества узлов с ростом глубины будет практически экспоненциальный, и каждый раз оно (количество узлов) будет умножаться на количество всевозможных ходов в этой ситуации (в начале партии этот множитель не будет сильно отличаться от количества клеток на поле). Получится много узлов, очень много. Ни в памяти описать, ни по времени обработать... 28.04.2006 |