GotAI.NET - Форум - Искусственный интеллект

Все темы | Новая тема

Стр.14 (19)

<< < Пред. | След. > >>

Поиск:

Автор

Тема: На: Целеполагание в железе

tac
Сообщений: 2601

На: Целеполагание в железе

Добавлено: 23 май 13 6:23

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

Пример задания дискретной функции полезности неаналитическим способом
0. (выигрышная) 3 крестика (или нолика) по горизонтали, вертикали или диагонали через 1
ход;
1. (группа защиты) так как это игра с двумя игроками, в которой один противодействует
другому, метод X-тюнинг нужно применять последовательно для оценки действий каж-
дого игрока. Если позиция игрока-противника попадает в группу 0, 2 или 3, то она
является опасной для игрока, и ему нужно защищаться и не допустить такой позиции.
Для этого можно занять соответствующую позицию крестиком, чтобы противник не
поставил бы туда нолик;
2. (2 крестика (или нолика) и 1 пустая позиция) при этом одновременно больше 2 вариан-
тов;
3. (2 крестика (или нолика) и 1 пустая позиция) при этом одновременно больше 1 варианта;
4. (2 крестика (или нолика) и 1 пустая позиция);
5. (1 крестик (или нолик) и 2 пустые позиции).
Видно, что группы выстроены в порядке возрастания приближения к выигрышу. При этом
только группа 0 приоритетнее защиты, а если нет угрозы со стороны противника, ориентируемся
на группы 2-5, которые последовательно ведут к выигрышу.
В методе Мини-Макс необходимо построить полное дерево возможных исходов игры. Число
узлов при построении дерева в эксперименте равно 255168. Это число получается как сумма всех
возможных вариантов ходов – 9 вариантов на первом шаге, 8 – для каждого из 9 на втором шаге,
7 – на каждом из 72 вариантов на третьем шаге и т.д., за вычетом ситуаций досрочного оконча-
ния игры. Сравнительно: для метода X-тюнинг за всю игру нужно просчитать 1000-2000 состоя-
ний игры в зависимости от ходов игроков. При этом первый ход не имеет предпочтений и дела-
ется случайно, а за второй ход оценивается около 1000 позиций, и соответственно, все последую-
щие ходы занимают менее 500-1000 оценок состояний. Таким образом, метод X-тюнинг переби-
рает сравнительно незначительное число состояний, и на несколько порядков быстрее вычисляет
ход, который должен сделать игрок. При этом, несмотря на то, что варианты ходов по сравнению
с методом Мини-Макс разные, метод X-тюнинг также в наихудшем случае всегда сводит игру к
ничьей.

Форум: Проблемы искусственного интеллекта