(Редактировать: 08.08.2013) - Я написал несколько примеров кода: Ultimate Tic-Tac-Toe, где у меня есть общая реализация поиска минимальных/максимальных игр. Код написан в глупом варианте C++, который называется prepp.
Ваш лучший ресурс - это курс колледжа на искусственном интеллекте. Классический учебник "Artificial Intelligence: A Modern Approach" by Russel & Norvig
Я попытаюсь дать вам разбивку ключевых понятий.
состояния игры - это набор переменных, которые могут быть использованы для определения:
- Сметных «Value» текущего состояния
- ли игра закончена?
Значение - «ценность» конкретного состояния является функцией этого состояния оценивали с помощью текущего игрока, назовем его Р (х). Другим именем этой функции является «эвристическая» функция.Он определяет наилучшее возможное значение, которое мог достигнуть текущий игрок, учитывая состояние платы, x. Как вы моделируете x зависит от вас, но x должен охватывать все, что используется в естественном потоке игры. Итак, в вашем случае x может быть матрицей значений 8x8, отображаемой на куски на доске. И, f будет функцией, которая дает «значение» этой конфигурации платы для красного игрока (или некоторых таких).
Возможное упрощение, которое следует учитывать в пошаговой игре с двумя игроками, состоит в кодировании «текущий игрок» как часть государства. Это добавляет состояние для ввода эвристической функции. Итак, вместо f (x), у нас есть f (x, игрок). Однако это можно упростить путем прокатки игрока в x. В любом случае, f всегда будет возвращать значение «Value» для того же игрока, но в зависимости от того, кто сейчас на очереди.
Для пояснения (упрощенного) примера f в шахматах должен почти всегда возвращать очень высокий балл, если белые могут убить черную королеву. Но если у черных будет возможность убить королеву белых в следующем ходу, то f должен вернуть очень низкое число.
Обратите внимание, что до сих пор не упоминается часть minmax для поиска деревьев. f всегда определяется на основе Текущее состояние. Поэтому, когда я сказал, что «у черных будет возможность ...», я имею в виду, что ваша эвристическая функция может определить, например, что при x существует линия визирования (по диагонали, по горизонтали или по вертикали) между черным слоном или ладьей, до королевы белых. Эвристика для шахмат должна быть достаточно сложной, чтобы знать, что это само по себе создает угрозу, и поэтому ее следует оценивать соответственно при вычислении общего значения f.
Прежде чем перейти к minmax, обратите внимание, что A * - это оптимизация для поиска пространства возможных значений x. Но вам не стоит беспокоиться об оптимизации, пока вы полностью не поймете и не внедрили minmax.
Итак, алгоритм minmax - это способ организации процесса принятия решений AI. Вещи, которые вы должны будете быть в состоянии сделать для реализации MinMax:
- Сформировать действительные игровых состояний от существующего игрового состояния х.
- Стоп-цикл или рекурсия после достижения определенной глубины.
- Помните «Значение» для каждой рекурсии уровня, передавая ее обратно вызывающему.
Начальный поток начинается с понимания, на чей ход? Как я упоминал ранее, f всегда будет возвращать высокие значения, чтобы указать успех для игрока 1, и низкие значения для указания успеха для игрока 2. На каждом более глубоком уровне рекурсии игрок позволит вам понять, следует ли выбирать минимальный или максимум потенциальных значений, обнаруженных через вашу рекурсию.
Позвольте мне сказать это другим способом. Есть две причины для фактической оценки f (x).
- Вы хотите знать, если игра закончена в состоянии х.
- Вы достигли самого глубокого уровня рекурсии, и вы хотели бы оценить, какой счет будет, если игра продвинулась так далеко.
Таким образом, ваш код будет делать что-то вроде этого:
функция MINMAX (х, игрок) возвращает значение
- Мое текущее состояние х, а следующий плеер для передвижения известен. Я знаю это потому, что
- функция выбрать-move сказал мне об этом. (см. ниже)
- Я сам назывался рекурсивно. (см. ниже)
- Игра закончилась тактично? Спросите f (x). Если он возвращает положительную бесконечность, побеждает белый. Если он возвращает отрицательную бесконечность, то черный выиграл. Если ваша игра имеет тупиковый вариант или имеет конечный результат (возможно, как часть более крупной игры), вам просто нужно составить способ представить выигрыш + счет в качестве возвращаемого значения f. Или, если вы хотите отделить его, просто создайте новую функцию g (x), которая делает это. Если игра закончилась, верните это значение вашему абоненту. Если игра еще не закончена, продолжайте.
- От x Перечислите все возможные x '. В игре 8x8 может быть несколько, до десятков или сотен возможных действительных ходов из любого состояния игры. Это зависит от правил вашей игры.
- Если самый глубокий уровень желаемого рекурсии было достигнуто,
- Для каждого х ', вызовите F (X', игрок). Для каждого вызова, мы связываем его возвращаемое значение с определенным х « мы прошли в.
- Else
- Для каждого х», рекурсивный вызов MinMax (х», другой плеер). (Обратите внимание, что другого плеера противоположен плеера на данный момент.) Для каждого вызова, мы связываем его возвращаемое значение с определенным х» мы прошли в.
На этом этапе все возможные последующие шаги должны иметь «значение», связанное с ними.
- Если игрок находится игрок 1, выбрать максимальное значение из всех значений, связанных со всеми х» и возвращает это значение. Это лучшее, что игрок 1 сможет сделать из этого состояния игры.
- Если игрок является игроком 2, выбрать минимальное значения из всех значений, связанных со всеми х» и возвращает это значение. Это лучшее, что игрок 2 сможет сделать из этого состояния игры.
конец функции MINMAX
функция выбрать-ход (х, игрок) возвращение * next_state *
- Мое текущее состояние х, и мы пытаемся выяснить, что игрок следующий шаг должен быть.
- Проверьте, закончилась ли игра, как описано выше.
- От x Перечислите все возможные x '. (Вы должны быть в состоянии повторно использовать любой код, который вы должны были сделать это в MinMax.
- Для каждого х «, вызовите MinMax (х», игрок). Для каждого вызова, мы связываем его возвращаемое значение с определенным х « мы прошли в.
- Если игрок находится игрок 1, выбрать максимальное значение из всех значений, связанных со всеми х» и г этерн это значение. Это лучшее, что игрок 1 сможет сделать из этого состояния игры.
- Если игрок является игроком 2, выбрать минимальное значения из всех значений, связанных со всеми х» и возвращает это значение. Это лучшее, что игрок 2 сможет сделать из этого состояния игры.
конец функции выбрать-ход
Ваш код драйвера просто нужно позвонить выбрать-ход, и он должен вернуться на следующий игровой доски. Очевидно, вы также можете кодировать возвращаемое значение как «перемещение» вместо состояния, для другого представления.
Надеюсь, это поможет. Извините за длинное объяснение, у меня просто был кофе.
У вас есть вопрос? – jakev
Извините, отправлено без моего согласия :) – Cyril
GameDev.StackExchange намного лучше по этому вопросу: http://gamedev.stackexchange.com/ –