Как создать функцию оценки для варианта игры TIC-TAC-TOE

Question

Я на самом деле работаю над настольной игрой, которая является вариантом TIC-TAC-TOE игра. Специфика игры заключается в следующем:

1. Игра ведется на nИксn доска, с n переменная.

2. Игрок выигрывает, если ему удается разместить k расклады первые, k является переменной

3. Выравнивание состоит из l отметки (X или O) по горизонтали, вертикали или диагонали. l фиксированный.

4. Если nИксn сетка заполнена (ни один игрок не может добавить отметку X или O), и ни один игрок не смог разместить k выравнивания, так что игра нарисована.

Я использую minmax с alpha-beta prunning алгоритм. Это моя первая программа с искусственным интеллектом, и я не знаю точно, как создать функцию оценки, которая будет использоваться алгоритмом. Я видел в сети несколько примеров, в которых для оценки позиции используется взвешивание материала, но я не могу применить это в моем случае. На самом деле, я использую функцию оценки radom, которая возвращает значение между -100 а также 100,

    float Conf_eval(Configuration c)
       {
         return (rand()%201)-100;
       }

Любая идея о том, как я могу оценить данную конфигурацию платы?

Answer 1

Это подробно обсуждается в книге " Искусственный интеллект - современный подход".

Также доступны отличные реализации (это Java, есть также Python, вы можете Google для более), основанные на серии книг. В том числе для крестики-нолики (и альфа-бета обрезки).

Если вы используете алгоритм min-max с альфа-бета-отсечкой, вы можете использовать отсортированный список "Действия", чтобы выполнять лучше в дополнение к своей эвристической функции (тривиальная служебная функция назначала бы 1 для победы, 0 для ничья и -1 к потере - это все листовые узлы расширенного дерева min-max).

Например, для сортировки действий вы можете предпочесть действия, в которых ваш символ (X, O) добавляется на путь "к победе". Это должно в конечном итоге привести к улучшению обрезки.