Я преподаю программирование на малышах, и сейчас представляю некоторые основные концепции искусственного интеллекта. Начнем с того, что мы собираемся реализовать игру tic-tac-toe, которая выполняет поиск по всему игровому дереву и как таковая играет отлично. Как только мы закончим, я хочу применить те же концепции к игре, у которой слишком много позиций для оценки каждого из них, так что нам нужно реализовать эвристику для оценки промежуточных позиций.
Лучшее, что я мог придумать, было Точки и ящики. Преимущество состоит в том, что я могу установить размер доски сколь угодно большим, чтобы остановить его от поиска всего дерева, и я могу сделать очень базовую функцию подсчета числа ящиков за вычетом количества ящиков противников. К сожалению, это означает, что в течение большей части начала игры каждая позиция будет оцениваться равнозначно со счетом 0, потому что она принимает довольно много ходов, прежде чем игроки начнут делать коробки.
Есть ли у кого-нибудь лучшие идеи для игр? (Или лучшая функция подсчета очков для точек и ящиков)?
Другой вариант игры может быть Reversi aka Othello.
Наивная эвристика состоит в том, чтобы просто подсчитать количество плиток, полученных каждым действительным движением, и выбрать наибольшее. Оттуда вы можете влиять на положение борта и свести к минимуму уязвимость противника.
Одна игра, которую вы можете рассмотреть, Connect Four. Простая игра с простыми правилами, но сложнее, чем Tic-Tac-Toe.
Шашки позволят вам преподавать несколько методов. Простой поиск, поиск глубин в наилучшем случае с наихудшими решениями, различия между краткосрочными и долгосрочными достижениями и что-то, над чем они могли бы продолжать работать после изучения того, что вы хотите учить.
Лично я считаю, что последний бит является самым критическим - есть естественные точки в развитии ИИ, которые хороши, чтобы остановиться, увидеть, можете ли вы победить его, а затем углубиться в более глубокие механизмы ИИ. Это заставляет вашего студента заинтересоваться, не будучи ужасно расстроенным, и дает им больше возможностей самостоятельно, если они хотят продолжить проект.
Как насчет Reversi? Он имеет довольно приятное пространство эвристики, основанное на количестве штук, количестве краевых частей и количестве угловых элементов.
Как насчет Mancala? Только 6 возможных ходов на каждом повороте, и легко вычислить результирующий балл для каждого, но важно учитывать реакцию противника, а игровое дерево становится довольно быстрым.
Gomoku - это хорошая, простая игра и интересная для написания AI для.
Rubik Infinity довольно весело, это немного похоже на Connect Four, но тонко отличается. Эволюция позиции довольно проста.
Я сбил Perl script, чтобы сыграть его некоторое время назад, и на самом деле пришлось уменьшить количество движений вперед, которые он смотрел, или он бил меня каждый раз, как правило, с довольно удивительной тактикой.
Четыре в строке Достаточно сложно, но достаточно легко придумать удобную рабочую функцию оценки, например (расстояние до четырех от моей самой длинной линии - расстояние до четырех от самой длинной линии противника)
Мне очень нравится Connect Four. Очень легко программировать с использованием алгоритма Minimax. Хорошей функцией оценки может быть:
eval_score = 0
for all possible rows/lines/diagonals of length 4 on the board:
if (#player_pieces = 0) // possible to connect four here?
if (#computer_pieces = 4)
eval_score = 10000
break for loop
else
eval_score = eval_score + #computer_pieces
(less pieces to go -> higher score)
end if
else if (#player_pieces = 4)
eval_score = -10000
break for loop
end if
end for
Чтобы улучшить программу, вы можете добавить:
Как насчет того, чтобы начать игру с точками и боксами со случайными строками, которые уже добавлены. Это может привести вас в действие быстро. Просто нужно убедиться, что вы не запускаете игру с помощью любых полей.
Взгляните на Go.
Обновление: упоминалось реверс, который является упрощенным вариантом Go. Возможно, это лучший выбор.
Что касается лучшей эвристики для точек и ящиков, я предлагаю посмотреть онлайн-руководство по стратегии для игры. первый результат в Google для стратегии "точек и коробок" весьма полезен.
Зная, как использовать правило цепи, отделяет игрока OK от хорошего. Зная, когда правило цепи будет работать против вас, это то, что отделяет лучших игроков от хороших.