Привет, васм. Мозг кипит, туплю, похоже, что не замечаю чего-то простого, но глаз замылился. Уверен, что поможете. Делаю ИИ для одной самопридуманной стратегической (типа шахмат-шашек, но не совсем) игры . Что имею: алгоритм альфа-бета отсечений, внутри которого работает оценочная функция. Алгоритм брал из этой статьи http://habrahabr.ru/blogs/artificial_intelligence/111210/ Мой упрощённый с подробными комментариями код (java): Код (Text): private TurnInfo bestTurn = new TurnInfo(); //найденный лучший ход final private int max_deep = 7; //максимальная глубина рекурсии //ищет оптимальный ход private int thinkingBestTurn(int alpha, int beta, int deep, Player currentPlayer) { int value; //противник Player opponent = game.getOppositePlayer(currentPlayer); //получаю список доступных ходов ArrayList<TurnInfo> turnInfos = game.getTurnsList(currentPlayer); //перебираю все ходы for (int k = 0; k < turnInfos.size(); k++) { //беру ход из списка TurnInfo ti = turnInfos.get(k); //сохраняю текущее состояние игры чтобы потом восстановить game.push(); //делаю ход makeTurn(ti); //если мы ещё в состоянии думать хоть на один ход вперёд if (deep > 1) //вызываю рекурсивно метод для определения оптимального хода противника value = -thinkingBestTurn(-beta, -alpha, deep - 1, opponent); //иначе оцениваю текущую позицию else value = evaluatePlayerScore(currentPlayer) - evaluatePlayerScore(opponent); //откатываю сделанный ход game.pop(); //дальше классический алгоритм отсечений if (value > alpha) { if (value >= beta) { //нашли очередной оптимальный ход (только не в глубине рекурсии) if (deep == max_deep) bestTurn = ti; return beta; } //нашли очередной оптимальный ход (только не в глубине рекурсии) if (deep == max_deep) bestTurn = ti; alpha = value; } } //выходим (в bestTurn - лучший ход) return alpha; } Вроде бы в коде ошибок нет. Возникает следующая проблема, опишу (очень упрощённо) абстрактно: Предположим, что всё наше поле это три клетки на которых: пешка пустая_клетка цель Задача пешки дойти до цели. Как бы поступил человек? Сходил бы на пустую клетку, а на следующий ход на клетку_цель. Как рассуждает бот, согласно вышеприведённому алго: 1 ход: получаю список доступных ходов. В списке всего один ход (на пустую клетку). Если я сделаю этот ход, то на следующий у меня будет два доступных хода (смогу сходить на покинутую клетку и на клетку-цель). Отлично, значит имеет смысл делать этот ход (потому что он приблизит меня к цели). 2 ход: (Пешка бота стоит непосредственно возле цели.) Получаю список доступных ходов. Доступно два хода: Первый - пойти влево на пустую клетку, если я на неё схожу, то следующим ходом я смогу пойти на клетку вправо, а потом либо влево, либо на клетку-цель. Шикарно, значит это допустимый ход, отмечаю его как лучший. Второй - пойти вправо на клетку цель. Тоже допустимый ход, вот только он ничем не лучше уже найденного (ведь найденный тоже ведёт к цели), поэтому не вношу изменений в bestTurn. В итоге бот двигает пешку влево-вправо! Внесу пояснения. На самом игра не так выглядит как описано в абстрактном примере выше, просто в игре возникает такая ситуация, когда бот может срубить более слабую фигуру (слабая фигура не может рубить сильную по правилам), но не делает этого, а мечется туда-сюда рядом с ней. Функция evaluatePlayerScore(Player p) считает количество очков для текущей игровой ситуации у указанного игрока - она просто складывает стоимости всех фигур, которыми он владеет (король самый дорогой, пешка дешёвая итд). Заранее благодарен, сам я не могу сдвинуться с мёртвой точки. Пробовал накладывать штраф за глубину рекурсии при вычислении value, но комп начинает иногда совершать глупые ходы.
Нуууу, логично Только как? Дело в том, что "цель" это не всегда перемещение из точки А -> B. На поле может разворачиваться сложная игровая ситуация. И если в алгоритм захардкодить "рубить всегда", то он иногда начнёт делать самоубийственые ходы. Или я чего-то недопонял, что имеете ввиду. Можно конкретный кусок псевдокода реализующего идею "оценить, что у нас есть 2 хода, но какой из них приведёт нас к цели быстрее"?
представляете каждую текущую ситуацию с учетом игровых условий как статический лабиринт и поиск пути в лабиринте для каждой возможной фишки. и сравнение выгодности ходов или это, или это, не знаю подробностей задачи. вот тут еще
zxcv, если я правильно понял, предлагаете не использовать алгоритм альфа-бета отсечений. Тогда, либо придётся отказаться от просчёта на несколько ходов вперёд, либо комп станет думать слишком долго (сейчас при глубине рекурсии = 8 он думает максимум секунд пять если ситуация сложная. В простых ситуациях ходит моментально).
HuXTUS "понятно, что ничего не понятно" (с). насколько понял, эта ваша игра -- "пошаговая стратегия", в связи с чем: 1. Если задача бота выиграть у игрока, то это реализуемо (компьютеры посообразительней людей); т.е. "уровень сложности" в такой игре необходимость. 2. Второй лучше, потому что сначала необходимо экономить время (т.е. приближать конец игры). Видимо в дизайне ИИбота не прописан строгий порядок действий. P.S. если бот не экономит время пользователя -- бот является ТРОЛЛЬлем )))
Я понимаю, что второй лучше) Что нужно внести в тот код, что я раписал, какое-то простое улучшение (или исправить баг, который я не вижу) чтобы бот начал ? Код более-менее работает. Сейчас комп действует рационально в ситуациях, когда от неверного хода он может потерять очки, то есть может прикрыть сильную фигуру слабой от угрозы или начать убегать слабой от сильной пока не окажется под прикрытием. Но когда ему ничто не угрожает (как описано в первом посте), он начинает страдать ерундой.
вы наверно понимаете, что я не знаю о вашей задаче и условиях решения(например, жабаМЕ + нокия 3310 на поле 10000х10000 при 1000 чар с полной свободой и плотной застройкой в неск уровней) совсем ничего. смысл этой фразы в том, что, может, стоит нормализовать условия под возможности целевой платформы? алг A* разработан специально для игр
А* это поиск пути в лабиринте. В моей игре комп не ищет путь, он делает оптимальный ход (как в шашках или шахматах). Надо было сразу дать ссылку на игру, которую я клонирую (с небольшими улучшениями) и делаю ИИ http://www.freeworldgroup.com/games6/gameindex/tomb-chess.htm
HuXTUS ИИ для игр в шашки ? бред. такие игры лехко аписываются матаном и все сводится к тупому вычисленею
