RNAInSpace/Реконструкция прошлого: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 46:
Чтобы продемонстрировать отличия данных подходов, сыграем в игру крестики-нолики. Для простоты начнем из состояния изображенного на рисунке. Существует 8 вариантов позиций крестиков дающих выигрыш (занять одну из вертикалей (3), одну из горизонталей (3), одну из диагоналей (2) ). Введем 3 группы. В группу 3 попадают все варианты, где один крестик и 2 пустых позиции на пути к выигрышу. В группу 2 попадают все варианты, где 2 крестика рядом и 1 пустая позиция нужная для выигрыша. И в 3 группу попадают 3 крестика расположенные давая выигрыш.
 
ИИз имеющегося положения надо проанализировать 5 положений и решить куда поставить крестик. Ставя крестик в позицию 1 (позиции отсчитываем слева-направо, сверху-вниз) вы попадаем в состояние из группы 2: 2 крестика и пустая клетка. Аналогично в позициях 3, 7 и 9. А в позиции 6 попадаем в группу 3: 1 крестики и две пустые клетки. Таким образом, в группе 2 имеем 4 варианта.
 
Теперь проанализируем эти 4 варианта на следующем шаге. Из позиций 1 и 3 получаем по 2 варианта выигрыша, а из 7 и 9 по одному. Поэтому в группу один попадают позиции 1 и 3.
 
Заметим, что в таком подходе нам не обязательно анализировать действия противника, и кроме того, мы избавились от достаточно большого перебора.
 
== Ссылки ==