игрока после удаления симметричных случаев.
Если мы будем продолжать, чтобы пройти все возможные ходы, в результате график даст нам пространство состояний.
Угадайте, сколько возможных состояний есть? Если вы достаточно терпеливы, чтобы проследить все возможности, вы увидите, что есть более чем 250000 возможных последовательностей. Вместо того чтобы идти через все случаи, давайте дальше расширять только один конкретный случай.
Здесь все возможные размещения 2-го крестика после этого конкретного выбранного состояния, и все возможные места размещения 2-го кружка.
3-я шаг со стороны игрока с крестиком приведет к первому возможному состоянию выигрыша.
Кроме того, 3-й шаг для кружка приведет ко второму возможному состоянию выигрыша.
Также есть состояние ничьей.
Эти результаты состояния победы вместе с состоянием ничьей образуют множество конечных состояний.
Есть много больше конечных состояний, которые не показаны здесь.
И после прочтения этой книги, вы должны уметь писать программы для такого рода игр или даже более сложных задач.
Пример задачи
Давайте рассмотрим другой пример, чтобы проиллюстрировать, как выбор соответствующего представления может упростить поиск решений более сложной задачи.
Как и в игре крестики-нолики, задача здесь начинается с матрицы 3х3, но в этой задаче, клетки занимают квадратные яблоки.
Давайте назовем это задачей квадратных яблок.
Люди на самом деле могут вырастить квадратные яблоки или даже квадратные арбузы.
Предположим, что в исходном состоянии этой задачи существует червь в средней ячейке.
Вопрос в том, может ли червь съесть все яблоки, выполнив следующие два правила.
Во-первых, после того, как червь закончил целое яблоко в текущей ячейке, он может двигаться только в другую ячейку, которую разделяет общая сторона, так что эти стрелки показывают 4 возможных хода и 2-е правило состоит в том, что вы не можете переместиться в ту ячейку, которую посещали прежде.
То есть, червь может двигаться только в ячейку, где есть еще несъеденное яблоко внутри.
Рисунок показывает, что червь начинает с середины. После того, как заканчивается среднее яблоко, он может двигаться в одну из четырех клеток на стороне, но не в углу. Таким образом, червь может двигаться вправо, двигаться вниз, двигаться влево и двигаться вверх.
Я хочу, чтобы вы подумали, есть ли решение этой задачи.
То есть, может ли червь съесть все 9 яблок.
Это должно быть совершенно очевидно.
Здесь часть пространства состояний графа и это возможный путь, который может привести к решению.
На самом деле, вы обнаружите, что есть 7 других пути для решения, пробуя другие ходы.
Можно написать программу Java, которая была бы создана для решения этой задачи.
И после прочтения этой книги,
