Определение полезности хода в определенном состоянии связано с опытом программиста и его / ее знанием игры.
Значения полезности в состоянии терминала легко определить. Например, в крестики-нолики терминальное состояние для игрока X - это когда X выровнены по диагонали, по вертикали или по горизонтали. Любое движение, которое создает такое состояние, является состоянием терминала, и вы можете создать функцию, которая проверяет это. Если это состояние терминала, функция возвращает 1 или -1.
Если агентом игрока является игрок X и после хода игрока X он определяет, что игрок O победит, то функция возвращает -1. Функция возвращает 1, если она определяет, что это ее собственный ход победы.
Если все ячейки заняты последним возможным ходом и никто не выиграл, то функция возвращает ноль.
Это только в терминальных состояниях. Очень важно оценить промежуточные состояния, потому что даже в игре 3х3 есть много комбинаций, которые необходимо учитывать. Если вы включите симметричные ходы, у вас есть 9! возможные состояния в крестики-нолики. Для этих промежуточных случаев вам нужно придумать функцию оценки, которая возвращает оценку для каждого состояния, поскольку они связаны с другими состояниями.
Предположим, что я назначаю значения состояния терминала 810, 0 и -810. За каждый ход счет будет 810 / (количество ходов). Поэтому, если я достигну состояния терминала за 6 ходов, счет будет 810/6 = 135. В 9 ходах счет будет 90. Функция оценки, созданная таким образом, будет отдавать предпочтение ходам, которые достигают состояния терминала быстрее. Тем не менее, он все еще оценивается как конечный узел. Мы должны оценить, прежде чем достичь конечного узла, но это также может быть частью функции оценки.
Предположим, что в приведенной ниже игре игрок 1 - это Х. Поэтому Х движется следующим. Ниже приведены допустимые шаги (строка, столбец) для X:
(1) 0,0
(2) 0,2
(3) 2,0
(4) 2,1
(5) 2,2
| | O | |
| O | X | X |
| | | |
Значение полезности для каждого хода должно благоприятствовать лучшим ходам.
Наилучшими ходами в этом случае являются (2) или (5). Таким образом, функция оценки назначит значение полезности 81, например, каждому из них. Ход (4) является наихудшим из возможных ходов для игрока X (и также гарантирует, что вы проиграете игру против интеллектуального игрока), поэтому функция присвоит этому ходу значение -9. Ходы (1) и (3), хотя и не идеальные, не заставят вас проиграть, поэтому мы можем присвоить 1.
Поэтому, когда минимакс оценивает эти 5 ходов, потому что у вашего игрока X - макс, выбор будет либо (2), либо (5).
Если мы сосредоточимся на опциях (2) или (5), игра будет в терминальном состоянии через два хода после них. Таким образом, в действительности функция оценки должна выглядеть на 2 шага впереди текущих юридических шагов для возврата значений полезности. (Эта стратегия следует линиям поиска с ограниченной глубиной, где ваша функция оценивает на определенной глубине и выдает служебное значение, не достигая конечного узла или конечного состояния)
Теперь я вернусь к своему первому утверждению. Значение утилиты будет определяться функцией оценки, закодированной согласно знаниям программиста об игре.
Надеюсь, я вас не смущаю ...