Код для этой статьи:GitHub.com/parade to/eat…

Демонстрационный адрес:woo woo woo.parade to.com/v UE-китайский…

Все мы знаем, что нужно три шага, чтобы положить слона в холодильник. Точно так же написание шахматной программы ИИ занимает всего три шага:

1. пройти все возможные ходы
2. Выбери лучший ход
3. идти

Третий шаг на самом деле просто составление чисел здесь, и его можно удалить, чтобы было проще написать программу ИИ, и требуется всего два шага.

Среди них первый шаг не представляет сложности для людей с небольшими познаниями в шахматах и ​​программировании, если вы обратите внимание на особые правила некоторых шахматных фигур, такие как хромота «коней», «пушек» нужно отдельно, чтобы поесть, и т. д. Эта часть не является предметом обсуждения в этой статье.

В центре внимания этой статьи находится второй шаг.Первый вопрос, который нам нужно решить, заключается в том, как, учитывая шахматную партию, судить о качестве игры?

оценка ситуации

Многие ученые проводили исследования по оценке шахматных ситуаций, включая статические монады, будущие ситуации, шахматные знания и дополнительную информацию о ситуациях. В этой статье используется статический монадический тип.

Так называемая статическая монадическая оценка относится к рассмотрению типа и положения каждой фигуры на шахматной доске, определению ее оценочного значения в соответствии с важностью типа и плюсами и минусами позиции, а затем прямым накоплением оценочных значений. всех своих фигур на шахматной доске.Для боевой силы своей стороны сложите значения оценки всех фигур противника, чтобы получить значение боевой силы противника, и вычтите значение боевой силы противника из значения боевой силы вашей собственной стороны, чтобы получить окончательную оценку значения ситуации.

Например, в зависимости от важности частей мы можем указать вес частей следующим образом:

帅/将: 1000000
仕: 110
象/相: 110
马: 300
车: 600
跑: 300
卒/兵: 70

Например, позиционный вес красной «машины» выглядит следующим образом:

Алгоритм макс. мин.

При методе оценки ситуации каждый раз просматривая все возможные ходы, а затем выбирая ход с наивысшей оценкой ситуации, является простейшим шахматным ИИ. Но этот ИИ будет немного глупым и немного недальновидным. Например, следующая шахматная партия:

Если предположить, что сейчас очередь красной команды, то по нашему алгоритму «одна машина въезжает в семерку» и съедает черную «пушку», и можно получить максимальное значение оценки ситуации. Но, очевидно, что проигрывает. Проблема в том, что наш алгоритм учитывает только один слой, и такой алгоритм, который заботится только о непосредственных интересах в данный момент, явно ненадежен.

В этом случае вы можете подумать, что вам нужно рассмотреть еще несколько слоев, прежде чем подсчитывать балл ситуации, а затем выбрать ход с наибольшим баллом из всех ветвей. Как на картинке ниже:

Сначала я прохожу все возможные ходы (черные квадраты на рисунке), затем продолжаю обход на основе ходов этого слоя (белые квадраты в последней строке рисунка), затем вычисляю оценку ситуации и выбираю ход с наибольшим забить, то есть выбрать Ход черного квадрата слева.

Однако вы забыли одно очко.После того, как вы закончите ходьбу, наступит очередь вашего противника уйти.Если вы хотите получить 100 очков, вам нужно, чтобы ваш противник сотрудничал с вами, чтобы выбрать ход на 100 очков. Очевидно, что ваш противник не будет таким глупым, он попытается помешать вам получить высокий балл, поэтому он выберет ход со счетом 1.

И если вы выберете ход с черным квадратом справа, ваш противник выберет ход со счетом 33, а вы вместо этого получите более высокий балл.

Люди могут легко принимать такие решения, но как научить компьютеры думать так же? Это требует использования алгоритма max-min. Алгоритм max-min делит дерево поиска на слой максимального значения и слой минимального значения. ИИ находится на слое максимального значения, а оппонент находится на слое минимального значения. Слой максимального значения всегда выбирает наибольшее значение из следующего слой в качестве результата, а слой с минимальным значением всегда находится снизу. Один слой выбирает в качестве результата минимальное значение. Как показано ниже:

Идея понятна, код очень прост в реализации, нижеследующее взято изwikiКусок псевдокода:

/**
 * node 当前节点
 * depth 当前搜索层数
 * maximizingPlayer 是否为最大值层
**/
function minimax(node, depth, maximizingPlayer) is
    // 到达搜索最底层，或 node 是一个叶子节点
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    // 最大值层，从下层选择分数最大的
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    // 最小值层，从下层选择分数最小的
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

Этот алгоритм также можно смоделировать скучной игрой со следующими правилами:

Есть два больших мешка, и в каждом большом мешке есть два маленьких мешочка внутри, и в каждом маленьком мешочке находится разное количество золотых монет.

Теперь вам нужно выбрать большую сумку, а затем оппонент выбирает для вас маленькую сумку внутри. Ваша задача — получить как можно больше золота, а задача вашего противника — помешать вам получить как можно больше золота.

Прежде всего, эту игру можно разделить на четыре ветви:

В слое противника (соответствующем слою минимального значения в алгоритме) из следующего слоя будет выбран мешок с наименьшим количеством золотых монет:

В вашем слое (соответствующем слою максимального значения в алгоритме) сумка с наибольшим количеством золотых монет будет выбрана из следующего слоя:

Суммировать

В этой статье описываются основные шаги по реализации шахматного ИИ, приводится алгоритм минимум-макс и анализируется его с помощью скучной игры. Однако этот алгоритм требует много времени.Предполагая, что каждый обход генерирует в среднем 30 ходов, ИИ с глубиной 5 должен выполнить в общей сложности 24 300 000 вычислений оценки ситуации. На самом деле алгоритм можно оптимизировать через определенные правила, о которых пойдет речь в следующей статье.

Ссылаться на

1. Исследование технологии оценки ситуации с компьютерными играми в китайские шахматы
2. Minimax
3. IntelligentChineseChessSystem
4. gobang

Добро пожаловать в публичный аккаунт, спасибо!