Как вы уже знаете, идея Minimax заключается в глубоком поиске наилучшего значения, предполагая, что противник всегда будет играть ход с наихудшим значением (худшим для нас, поэтому наилучшим для них).
По идее, вы будете пытаться дать значение каждой позиции.Позиция, в которой вы проигрываете, отрицательна (мы не хотим этого), а позиция, в которой вы выигрываете, является положительной.Вы предполагаете, что всегда будете пытаться получить позицию с наивысшей ценностью, но вы также предполагаете, что противник всегда будет стремиться к позиции с наименьшей ценностью, что имеет худший для нас результат и лучший для них (они выигрывают, а мы проигрываем).Таким образом, вы ставите себя на их место, стараетесь играть настолько хорошо, насколько можете, и предполагаете, что они это сделают.
Итак, если вы обнаружите, что у вас есть два возможных хода, один из которых дает им выбор: выиграть или проигратьВ любом случае, один из которых приводит к ничьей, вы предполагаете, что они пойдут на ход, который заставит их выиграть, если вы позволите им сделать это.Так что лучше пойти на ничью.
Теперь для более «алгоритмического» представления.
Представьте, что ваша сетка почти заполнена, за исключением двух возможных позиций.
Подумайте, что происходит, когда высыграйте первую:
Оппонент сыграет другую.Это единственный возможный ход, поэтому нам не нужно рассматривать другие ходы от них.Посмотрите на результат, свяжите результирующее значение (+ ∞, если выиграл, 0, если ничья, -∞, если проиграл: для крестики-нолики вы можете представить их как +1 0 и -1).
Теперь рассмотрим, что происходит, когда высыграйте второй:
(то же самое здесь, у противника есть только один ход, посмотрите на полученную позицию, оцените позицию).
Вам нужно выбрать между двумя ходами.Это наш ход, поэтому мы хотим получить лучший результат (это «максимум» в минимаксе).Выберите тот, у кого более высокий результат, в качестве нашего «лучшего» хода.Вот и все для примера «2 хода от конца».
Теперь представьте, что у вас осталось не 2, а 3 хода.
Принцип тот же, вы хотите присвоить значение каждому из 3 возможныхходы, так что вы можете выбрать лучший.
Итак, вы начинаете с рассмотрения одного из трех ходов.
Вы находитесь в ситуации выше, только с 2 возможными ходами, но это ход противника.Затем вы начинаете рассматривать один из возможных ходов для противника, как мы делали выше.Кроме того, вы смотрите на каждый из возможных ходов, и вы найдете значение результата для них обоих.Это ход противника, поэтому мы предполагаем, что они сыграют «лучший» ход для них, тот, который имеет худшую явку для нас, так что это тот, у которого меньшее значение (это «мин» в минимаксе).Игнорировать другой;Предположим, они все равно сыграют то, что вы нашли для них.Это то, что даст ваш ход, так что это значение, которое вы назначаете первому из трех ваших ходов.
Теперь вы рассматриваете каждый второй возможный ход.Вы даете им значение таким же образом.И из ваших трех ходов вы выбираете тот, который имеет максимальное значение.
Теперь рассмотрим, что происходит с 4 ходами.Для каждого из ваших 4-х ходов вы смотрите, что происходит с 3-мя ходами вашего противника, и для каждого из них вы предполагаете, что они выберут тот, который даст вам наихудший возможный результат из лучших из 2-х оставшихся для вас ходов.
Вы видите, куда это идет.Чтобы оценить ход n шагов от конца, вы смотрите на то, что может произойти для каждого из n возможных ходов, пытаясь дать им значение, чтобы вы могли выбрать лучший.В процессе вам нужно будет попытаться найти лучший ход для игрока, который играет с n-1: противником, и выбрать шаг с меньшим значением.В процессе оценки хода n-1 вы должны выбрать между возможными ходами n-2, которые будут нашими, и предположить, что мы будем играть так же хорошо, как можем на этом шаге.И т.д.
Вот почему этот алгоритм по своей сути рекурсивен.Независимо от n, на шаге n вы оцениваете все возможные шаги на n-1.Промыть и повторить.
Так как сегодняшние крестики-нолики достаточно мощные, чтобы вычислить все возможные результаты с самого начала игры, потому что их всего несколько сотен. Когда вы захотите реализовать его для более сложной игры, вам придется в какой-то момент прекратить вычисления, потому что это займет слишком много времени. Таким образом, для сложной игры вам также нужно будет написать код, который решит, продолжать ли искать все возможные последующие ходы или попытаться определить значение позиции сейчас и вернуться рано. Это означает, что вам также придется вычислять значение для позиции, которая не является окончательной - например, для шахмат вы должны учитывать, сколько материала у каждого оппонента на доске, непосредственные возможности проверки без мата, сколько плиток вы контролируете и все, что делает его не тривиальным.