Поиск:

Ответ в темуСоздание новой темы Создание опроса
> игра "Точки" -> помогите с AI 
:(
    Опции темы
Immortal
Дата 23.8.2003, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



Решил вот я написать логическую игру "точки", сделал всё что мог: кучу настроек и др. Сделал довольно хорошо работающую проверку замкнутостей, но вот реализация ИИ это проблема. Всё что лезет на ум Это неизбежные многочисленные переборы, а на это нужно время, много время smile.gif

Не подскажите куда мне копать в графы, нейронные сети или вообще куда. Зараннее спасибо за помощь. Да если у вес есть предложения по реализации ИИ, кидайте буду благодарен. smile.gif
PM MAIL ICQ   Вверх
podval
Дата 23.8.2003, 23:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62



Immortal
На всякий случай объясни, что это за игра и что ты понимаешь под этими двумя буквами: ИИ?
PM WWW ICQ   Вверх
&-ray
Дата 23.8.2003, 23:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 406
Регистрация: 15.4.2003
Где: Казахстан, г Аста на

Репутация: нет
Всего: нет



Цитата
На всякий случай объясни, что это за игра и что ты понимаешь под этими двумя буквами: ИИ?

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

ЗЫ ИИ - искусственный интеллект wink.gif
ЗЗЫ Была у меня мысль сделать такую игрушку, но подумав о всей сложности реализации отложил это дело в долгий ящик. Хотя, может и возьмусь за нее, когда закончу со своими незаконченными проектами
ЗЗЫ Immortal дашь поиграть smile.gif


--------------------
"Совсем неважно от чего помрешь, ведь куда важнее - для чего родился..." С.Б.

--------------------
И снова мышь беру я в руки
Куда иду? - Конечно в сруки!
PM MAIL WWW   Вверх
Immortal
Дата 23.8.2003, 23:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



Игра "точки" это логическая, но больше позиционная игра. Для её раелизации в реальности необходимы две ручки разного цвета и лист бумаги в клетку. Цель игры окружать точки притивника и по-возможности не позволять окружать свои, если точки окружают область и интервал между точками одна клетка (по диагонали или ортогонали), то такая область считается захваченной. Точки границы захваченной области соединяются между собой линиями.

Ну и соответственно, что я понимаю под буквами ИИ - Искусственный Ителлект, как грозно звучит. Я понимаю что Исскуственного Интеллекта не существует (если не считать программу в нашем мозге), но мне надо, что бы комп ставил точки взвешивая все за и против.
PM MAIL ICQ   Вверх
Immortal
Дата 23.8.2003, 23:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



&-ray твой ответ пришёл быстрее, но мне бы тоже хотелось в неё поиграть вот я и спрашиваю, куда мне надо лезть, в какие дебри. (страшно... smile.gif)
PM MAIL ICQ   Вверх
&-ray
Дата 23.8.2003, 23:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 406
Регистрация: 15.4.2003
Где: Казахстан, г Аста на

Репутация: нет
Всего: нет



Основная проблема - научить компьютер выбирать наиболее рациональные пути захвата территории.
Я об этом тоже думал, но ничего не надумал sad.gif


--------------------
"Совсем неважно от чего помрешь, ведь куда важнее - для чего родился..." С.Б.

--------------------
И снова мышь беру я в руки
Куда иду? - Конечно в сруки!
PM MAIL WWW   Вверх
Immortal
Дата 24.8.2003, 00:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



Эту проблему возможно решить с помощью алгоритма А*, там можно выбирать проходимость точки (вес), любую пустую клетку можно воспринимать, как область очень трудной проходимости. При встечи любой из вершин, проверять образуется ли в процессе этого какая-либо замкнутость, если образуется, то записывать сколько захватывает точек и за сколько ходов, и соответственно записывать все вершины в массив. При просмотре всех вариантов в районе 3-4 ходов на пустые клетки просмотр можно завершать. А затем выбирать оптимальную замкнутость и ставить точку, в одно из веньев её образующее.

Но слишком много переборов и возможно результат будет самым неожиданным smile.gif На прктике не испытывал.
PM MAIL ICQ   Вверх
December
Дата 24.8.2003, 00:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Antitheorist
****


Профиль
Группа: Участник
Сообщений: 4423
Регистрация: 14.8.2002
Где: Харьков

Репутация: нет
Всего: 57



Immortal, я в 5-6 классах на уроках сам с собой играл в точки. Звучит извращенчески, но эффект налицо: ещё никто никогда у меня не выигрывал. Хвастаюсь? Да, и вызываю на бой любого. Буду очень рад проиграть, или хотя бы просто поиграть с достойным соперником. Думаю, что, написав этот самый ИИ для своей игры, ты станешь этим самым соперником, надо будет как-нибудь попытаться устроить матч.
А пока могу только сказать, что:
1) В флэйме (или Готовые и разрабатываемые проекты) когда-то пробегала ссылка на интернет-вариант этой игры. У меня она почему-то не пошла, поэтому ничего о ней сказать не могу, но, думаю, тебе может быть интересно поковыряться в том варианте. Если не найдёшь сам, сообщи, я постараюсь найти.
2) Графы тебе не помогут. Придётся писать ИИ. Я бы ввёл понятия "линия", "окружение", "разрыв", "угроза" и т.д. и оперировал ими.
3) Насколько помню, на Дельфи ваяешь? Был бы не против присоединиться к проекту (не сейчас, правда, через пару недель).


--------------------
Для друзей с винграда - скидки на разработку сайтов
PM MAIL WWW ICQ   Вверх
Immortal
Дата 24.8.2003, 12:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



Я что-то не нашёл ничего подобного в разделе "Готовые и разрабатываемые проекты".
PM MAIL ICQ   Вверх
p0s0l
Дата 24.8.2003, 12:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



Люди, а возможно ли здесь сделать самообучающийся AI ?



--------------------
С уважением, г-н Посол.
PM   Вверх
mr.DUDA
Дата 24.8.2003, 17:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: нет
Всего: 232



Такой самообучающийся, чтобы сам себя обучал в течение некоторого времени, и потом всех делал smile.gif

Я вот раньше задумывался над этим же вопросом (много играл в точки smile.gif ), и вот что могу подсказать в плане общих идей.

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


--------------------
user posted image
PM MAIL WWW   Вверх
p0s0l
Дата 24.8.2003, 17:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



во-во, надо еще для сравнения эти расклады точек поворачивать на n градусов и отражать вертикально и горизонтально (если я думаю про тоже, что и mr.DUDA). я тоже так думал, но додумал до того, что это будет долговато... Только обучаться нужно не у самого себя, а у игрока...


--------------------
С уважением, г-н Посол.
PM   Вверх
mr.DUDA
  Дата 24.8.2003, 18:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: нет
Всего: 232



ЗЫ, развивая идею

  • Вместе с каждым "полигоном стратегии" можно хранить положение и направление вектора, в котором предполагается ставить следующие точки
  • Обучаться комп должен у игрока, но начальная база знаний не должна быть пустой, поэтому (мой вариант) сначала нужно сутки "погонять" комп против компа (с обучением обоих компов в одну базу знаний smile.gif ), а потом -- недельку: комп против каких-нибудь крутых челов (и можно параллельно, с суммированием полученных знаний в ту же базу). Результаты обучения и будут являться начальным уровнем "знаний" программы
  • Для хранения базы знаний использовать многослойную нейронную сеть (НС), каждая "стратегия" (т.е. цепочка полигонов и векторов направления) представлена набором весовых коэффициентов НС, структура НС и смысл слоёв и связей подбирается экспериментальным путем. Кстати, у меня есть исходники для построения самообучающейся НС перцепторного типа (многослойной, с регулируемым числом связей между слоями, и "доменами" внутри каждого слоя), написанные на Асме под C++ (сдавал как курсовую по системному программированию).
  • "Стратегия" м.б. не просто линейной цепью действий, а деревом из элементов "полигон+вектор"; для выбора наиболее удачной ветви можно сопоставить каждой из ветвей поле плотности точек на листе (малого разрешения по сравнению с разрешением листа)
  • и т.д., продолжая тему...


Это сообщение отредактировал(а) mr.DUDA - 24.8.2003, 18:01


--------------------
user posted image
PM MAIL WWW   Вверх
p0s0l
Дата 24.8.2003, 18:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



Цитата
сначала нужно сутки "погонять" комп против компа (с обучением обоих компов в одну базу знаний  )

А как они ходить будут, если в базе ничего нет ? Рэндомом ?

Третий пункт я не догоняю... У нас только что были НС, имею поверхностное представление о структуре и принципе действия, но только в общем смысле... Что будет на входе и выходе этой сети ? Я так понял, сеть должна выдавать, подходит ли данный расклад точек под эту стратегию, или как ? Можешь ли привести примерчик небольшой стратегии ?
И что, надо будет брать каждый кусок 4x4, например, точек и проверять на все стратегии ? Потом его масштабировать, поворачивать и т.д. ? А потом брать все куски 5x5 и также проверять ? Если так... sad.gif

Насчет исходников - можешь ли кинуть их мне, если не жалко ? А то, возможно, мне тоже придется с ними столкнуться...



--------------------
С уважением, г-н Посол.
PM   Вверх
Immortal
Дата 24.8.2003, 20:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 15.8.2003

Репутация: нет
Всего: нет



С самообучением у вас много чего не получится. Видал я одни точки, с самоубучением, правдо самоубучение заключалось в сохраниении каждой выигрышной позиции. Но есть очень много но. Позиции с участием большого числа точек сохранять неактуально, т. к. вероятность повторения такой позиции ничтожно мала, а позиции с участием малого количества точек к высокой стратегии не приведёт. Есть конечно польза от такого самообучения, но конечно не для проги, а для тебя. В Мозгу прога покруче будет smile.gif. Можете для начала почитать инфу на pointsgame.narod.ru.
PM MAIL ICQ   Вверх
Страницы: (3) Все [1] 2 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0933 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.