Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
knf
16 / 16 / 2
Регистрация: 18.09.2012
Сообщений: 184
#1

Искусственный интеллект для логической игры - C++

16.01.2014, 23:02. Просмотров 1536. Ответов 2
Метки нет (Все метки)

Конечно, громко звучит "искусственный интеллект", но в общем надо сделать бота для логической игры.
Вот сама игра.

Для игры в так-тикль используется доска 4х4, на которой расставлены 4 белые фишки и 4 черные фишки так, как показано на рисунке.
Ходы делаются по очереди. Начинают белые. За одни ход можно передвинуть любую из своих фишек на одну клетку по горизонтали или по вертикали, если она оказывается при этом на свободном поле. По диагонали ходить нельзя. Цель игры — выставить тройку своих фишек в ряд по горизонтали, вертикали или диагонали, как в “крестиках-ноликах”. Кто первым сделал это, тот победил.

Сделал игрок против игрока. А вот как игру с ботом сделать пока не знаю. Может кто идейку подкинуть?)
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2014, 23:02     Искусственный интеллект для логической игры
Посмотрите здесь:
Искусственный интеллект (боты) для игры C++
C++ Необходимо организовать ИИ (Искусственный Интеллект) для игры шашки
C++ Искусственный интеллект
искусственный интеллект C++
Искусственный интелект для игры C++
Интеллект для шахмат C++
C++ Написать программу, которая выводит таблицу истинности для логической функции
C++ Напечатать таблицу истинности для логической функции (A⇔B ⇔C) ∨ A
Интеллект компьютера в игре Крестик-Нолик C++
Кто что знает о Artificial Intelligence (Искуственный интеллект)? C++
Мне очень нужна программа для игры gta samp 0.3c для взлома базы данных C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
knf
16 / 16 / 2
Регистрация: 18.09.2012
Сообщений: 184
16.01.2014, 23:17  [ТС]     Искусственный интеллект для логической игры #2
Я понимаю, что это не просто, но должны же быть люди на этом форуме, которые хоть немного шарят в этом
gunslinger
случайный прохожий
1126 / 744 / 190
Регистрация: 20.07.2013
Сообщений: 2,049
16.01.2014, 23:54     Искусственный интеллект для логической игры #3
Из кэша гугла:
Кликните здесь для просмотра всего текста
Доброго времени суток!
Правила игры "Так-тикль":
1. Играют двое, один за крестики, другой за нолики.
2. Исходное поле 4х4:

XOXO


OXOX

3. Игроки по очереди делают ход (влево, вправо, вверх, вниз)
4. Выигрывает тот, кто быстрее составит ряд хотябы из трех своих фишек. Считаются ряды по горизонтали, вертикали и диагоналям.

Суть в том, чтобы написать алгоритм выбора оптимального хода компьютером. В журнале "Наука и Жизнь" 1977 №1 есть небольшая статья про игру, там сказано, что при оптимальных ходах обоих участников, игра будет продолжаться бесконечно.
Я перебираю все возможные варианты поля на 7-8 ходов вперед. Если представить себе все это дело в виде дерева, то листы -- это либо поле с выигрышной комбинацией, либо поле, для которого дальнейшие ходы не посчитаны (ограничение глубины рекурсии). Как по такому дереву можно определить оптимальный ход?

Заранее благодарен.
Извините за глупые вопросы.
Sbtrn. Devil Постоялец www 19 мая 2010 21:57 #1
Интуиция подсказывает следующее:

1) для текущего состояния посчитать минимальное расстояние до вражеской победы X (найти листок с вражеской победой с минимальной глубиной, X = его расстояние от текущего состояния) и до нашей победы Y (аналогично),
2) аналогично посчитать X и Y для состояний после нашего хода (соседних),
3) если для текущего состояния X>Y или X не определён (нет листков с вражеской победой), то выбрать ближайший листок с нашей победой и сделать ход по его ветке (ход на приближение к победе),
4) иначе: если для текущего состояния X<=Y или Y не определён (нет листков с нашей победой), то выбрать из соседних состояний то, у которого самый большой X (ход на отдаление от поражения).
5) если же не определён ни X, ни Y, то без разницы, куда ходить.

Если у нас 3), и есть несколько соседних листков с одинаковым Y, выбрать из них тот, у которого максимальный X (при наличии нескольких ходов, равноприближающих к победе, выбираем тот, который больше отдаляет от поражения).
Если у нас 4), и есть несколько соседних листков с одинаковым X, выбрать из них тот, у которого минимальный Y (при наличии нескольких ходов, равноудаляющих от поражения, выбираем тот, который больше приближает к победе).
Если же есть несколько листков с одинаково максимальными X и минимальными Y, выбрать из них любой.
Arturchik Пользователь www 19 мая 2010 23:54 #2
Sbtrn. Devil
Спасибо за ответ.
Одинакого у нас интуиция работает =)
Данный метод дает сбой в такой ситуации ( E - пустые клетки ):

E E X E
E E O E
O X E O
X O X E

ходят крестиками ( третья сверху фишка во втором столбце вправо ):

E E X E
E E O E
O E Х O
X O X E

Ходят они так из соображений, что нолики уберут свою фишку из третьего столбца, что приведет к скорой победе крестиков. Именно так сработает алгоритм, т.к. для крестиков это ближайшая достижимая победа.
Нолики, ( считаем, что они не дураки ) ходят третьей сверху фишкой первого столбца вправо:

E E X E
E E O E
E O Х O
X O X E

И вот крестики в тупике, как бы они не ходили, победа следующим ходом за ноликами.

В ответ на данную тупость можно предложить следующую идею: найдем варианты, когда при любом моем ходе, победа противника наступит по-любому ( меня загнали в угол ) и будем стараться избегать ходов, которые ведут к этим ситуациям. Самая большая тут проблема в том, что ближайшая победа -- весьма неточная оценка, т.к. противник не достаточно туп, чтоб допустить мою эту самую ближайшую победу.

Правка: 19 мая 2010 23:55
Monstradamus Постоялец www 20 мая 2010 4:21 #3
Минимаксный метод и альфа-бета отсечения курить нужно, как я понимаю.
Sbtrn. Devil Постоялец www 20 мая 2010 11:44 #4
Arturchik
> Ходят они так из соображений, что нолики уберут свою фишку из третьего столбца,
> что приведет к скорой победе крестиков. Именно так сработает алгоритм, т.к. для
> крестиков это ближайшая достижимая победа.
> Нолики, ( считаем, что они не дураки ) ходят третьей сверху фишкой первого
> столбца вправо:

> И вот крестики в тупике, как бы они не ходили, победа следующим ходом за
> ноликами.

Но при таком раскладе "расстояние до поражения" и "расстояние до победы" должны быть одинаковыми (по 3), и в действие вступил бы пункт 4) (про отдаление от поражения). Или не?
Arturchik Пользователь www 21 мая 2010 11:56 #5
Sbtrn. Devil
При таком раскладе получается, что ранооцененные ходы:
1. ходить вверх крестиком вторго столбца, третий сверху
2. ходить им же вправо
3. ходить вверх крестиком третьего столбца, четвертый сверху
4. ходить им же вправо

во всех этих вариантах считается, что самая близкая победа наступит после "правильного" (выгодного крестикам) хода ноликов, а у ноликов, во всех вариантах, победа дальше на один ход.
Sbtrn. Devil Постоялец www 21 мая 2010 12:19 #6
Гм. Ну тогда, действительно, остаётся ходить только по веткам, по которым меньше поражений (или столько же, но они дальше), и только при отсутствии поражений в поддереве следующего хода искать ход на победу.
Как ещё вариант, ходить на победу, если ближайшее поражение дальше ближайшей победы не менее, чем на 2-3-4 хода, и веток с поражениями в этом поддереве меньше, чем веток без них - тогда можно будет успеть сориентироваться на следующем ходу.
Arturchik Пользователь www 21 мая 2010 16:20 #7
Может быть, стоит идти не к просто победам, а к победам, как в примере победа ноликов, потому как обычная победа слишком наивная и в этом вся проблема.
Sbtrn. Devil Постоялец www 21 мая 2010 22:39 #8
Если попадётся поддерево, заканчивающееся победами, то, конечно, логично двигаться к нему. Но часто ли оно такое бывает?
Arturchik Пользователь www 22 мая 2010 9:06 #9
нет, такое бывает крайне редко
Sbtrn. Devil Постоялец www 22 мая 2010 12:35 #10
Тогда остаётся ходить на избежание поражения и на победу только в том случае, если она лежит в поддереве, где меньше поражений.
Arturchik Пользователь www 23 мая 2010 23:23 #11
Это все тоже не прокатывает. Ладно, спасибо большое всем за помощь, сделал кое-как через одно место.
Yandex
Объявления
16.01.2014, 23:54     Искусственный интеллект для логической игры
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru