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

Не подскажите куда мне копать в графы, нейронные сети или вообще куда. Зараннее спасибо за помощь. Да если у вес есть предложения по реализации ИИ, кидайте буду благодарен.

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

Цитата

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

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

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

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

Ну и соответственно, что я понимаю под буквами ИИ - Искусственный Ителлект, как грозно звучит. Я понимаю что Исскуственного Интеллекта не существует (если не считать программу в нашем мозге), но мне надо, что бы комп ставил точки взвешивая все за и против.

&-ray твой ответ пришёл быстрее, но мне бы тоже хотелось в неё поиграть вот я и спрашиваю, куда мне надо лезть, в какие дебри. (страшно... )

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

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

Но слишком много переборов и возможно результат будет самым неожиданным На прктике не испытывал.

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

Я что-то не нашёл ничего подобного в разделе "Готовые и разрабатываемые проекты".

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

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

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

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

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

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

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

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

Цитата

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

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

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

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

С самообучением у вас много чего не получится. Видал я одни точки, с самоубучением, правдо самоубучение заключалось в сохраниении каждой выигрышной позиции. Но есть очень много но. Позиции с участием большого числа точек сохранять неактуально, т. к. вероятность повторения такой позиции ничтожно мала, а позиции с участием малого количества точек к высокой стратегии не приведёт. Есть конечно польза от такого самообучения, но конечно не для проги, а для тебя. В Мозгу прога покруче будет . Можете для начала почитать инфу на pointsgame.narod.ru.

Значитца, по порядку. Сразу предупрежу, что реализацию идеи я взял с потолка, важен только подход к решению задачи. Теперь по существу:
1) начальное "обучение" состоит в отсеивании явно тупорылых ходов компа, для этого годятся и рандомные ходы (но таких "рандомных" игр должно быть сыграно очень много !)
2) стратегия, как я предложил, состоит из дерева возможных ситуаций. Это не обязательно общий расклад на бумаге. Когда человек играет, он в любой момент времени занят обдумыванием хода, опираясь на очень маленький фрагмент игрового поля, где были поставлены последние N точек (вот вам и полигон из "наших" точек, наложенный на массив "плотностей" вражеских точек; важна последовательность наших действий, которыми мы вызываем ответную реакцию оппонента; неверная последовательность действий приводит к "утоньшению" данной ветви дерева, верная -- к "утолщению")
3) общая стратегия при игре в точки сводится к замыканию вражеских точек в кольцо - отсюда получаем "вектор", стремящийся к точке, с которой начинается полигон
4) таким образом, дерево вариантов состоит из узлов, связанных ветвями разной толщины. В качестве узлов выступают: а) более-менее точное описание расположения наших точек (м.б. в виде списка пар "dx, dy" между точками полигона, в произвольном масштабе), б) матрица распределения плотностей вражеских точек, в) направление вектора, стремящегося замкнуть полигон (т.е. куда нужно ставить след. точку). В качестве ветвей - весовые коэффициенты.
5) НС можно прикрутить к выбору наиболее подходящего варианта для данного расклада. На вход посылаются описание расположения наших точек, распределение вражеских точек и направление вектора, замыкающего полигон. На выходе получаем номер ветви, которую нужно выбрать для удачного разрешения данного расклада. Обратное распространение корректирует весовые коэффициенты НС.

Это, повторяю, лишь общие идеи одного из множества вариантов, как научить комп думать. Пожалуйста, предлагайте ваши варианты.

p0s0l, надеюсь исходники помогли чем-нибудь

Посмотрел я ту гаму по ссылке... Да, в локальных таких маленьких ситуациях играет правильно, т.к. такие
случаи у него уже занесены. Но было что-то типа такого:

* * 1 1 1 * * *
* 1 * 2 1 1 * *
* * X 1 2 * 1 *
* * 1 2 * * 1 *
* * * * 2 1 * *
* * * 1 1 2 * *

мои точки 1
точки компа 2
Ход компа - и он поставил на место "X", хотя видно что я его потом обведу... А по описанию, дак типа должен предугадывать мои действия...
Immortal, придется ждать, пока ты сделаешь свой реально думающий AI...

mr.Duda, спасибо! Мне это может пригодится в этом семестре (поди тоже заставят курсач писать...)

Цитата

Когда человек играет, он в любой момент времени занят обдумыванием хода, опираясь на очень маленький фрагмент игрового поля, где были поставлены последние N точек

Нельзя думать, что человек отхватывает потихоньку. Этим могут воспользоваться те люди, которые поймут принцип AI.
Например, та гама (по ссылке Immortal'а) в таких случаях тупит: я поставил пару точек в середине, а потом стал ставить точки рядом с краями с расстоянием между собой в 3 клетки. Когда так обвел по периметру, стал потихоньку заполнять промежутки. Ну и время от времени подкидывал "работенку" компьютеру в центре поля - он там хорошо обводил . А на то что я собираюсь сделать смотреть не хотнл... Я так до конца и не доиграл - гама стала думать по минуте каждый ход. Может быть в конце бы и увидела, что я тут замыслил. Но в принципе это надо видеть раньше.
Такие ситуации, mr.Duda, будут вылавливаться заранее? Я имею в виду обманные действия ?

Это сообщение отредактировал(а) p0s0l - 25.8.2003, 00:39

Можно сделать несколько вариантов поведения. Например, всё вышеописанное подпадает под "наступательную" тактику, а можно сделать "оборонительную", "портящую", "предупредительную" и т.п. в зависимости от того, как решит комп: чего текущими действиями пытается достичь оппонент ?

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

Все так сложно и абстрактно...

Надо почитать про то, как думают шахматные игры. Их ведь море предумано. Просто принципы взять. По-моему они как раз переберают все возможные варианты, потому что в одной такой игре в опциях можно было менять кол-во просчитываемых ходов. И ещё я помню, что в Borland C++ 5.0 был пример игры в шахматы.

RAN, загляни туда, куда сказал Immortal - там лежит гама, AI которой работает перебором всевозможных комбинаций на глубину n ходов (n - сложность).
+у перебора отбрасываются ненужные ветви.
+система анализа важности точек и ходов.
И все равно получился AI, играющий на уровне наивного 10-летнего дитя.

Цитата(p0s0l @ 25.8.2003, 18:25)

Все так сложно и абстрактно...

Во-во.
Господа, вы перемудрили самих себя. Тут сам алгоритм сделать трудно, а вы замахнулись на самообучение (вполне в стиле vingrad, конечно).

Immortal, я имел в виду топик
http://forum.vingrad.ru/index.php?act=ST&f...t=3446&hl=точки
Я так понял, ты уже написал движок игры? Можно будет у тебя его позаимствовать, когда (и если) алгоритм придумаю? Гарантирую нераспространение без твоего согласия.

December, я не согласен насчет "перемудрили". Всегда нужно начинать с общей идеи, и только когда всё уже ясно в общих чертах, садиться за написание кода. Почему, по-твоему, я должен придумывать свой вариант исходников, если p0s0l всё равно будет делать по-своему, как он привык и в соотв. с логикой уже написанного кода ?

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

Если нагрузил рассуждениями, извиняюсь
Просто если бы стояла такая задача передо мной, всё бы сделал именно так как описал, а не иначе.

ЗЫ, до сих пор не прозвучало ни одного другого варианта общего решения задачи.

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

А насчёт подхода... Честно говоря (можете обозвать меня анахронизмом), когда задача довольно запутанна, я применяю старое доброе линейнон программирование. То есть сажусь и начинаю переводить свои мысли на Delphi - шаг за шагом. А поскольку данный процесс весьма способствует формализации задачи, потом мне проще переделать код в культурный вариант. И, если г-н Immortal любезно согласиться предоставить движок игры, я попробую именно так написать пару-тройку стратегий.
ЗЫ Ни в коем случае не претендую на правильность этого подхода.

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

TiHo, в точках имхо совсем другой алгоритм (окружить любыми способами и не быть окруженным самому), чем в крестиках (сам задумывался, можно ли взять чей-то AI для крестиков)

TiHo, ты, может быть, имел в виду Рэндзю?

Цитата

у меня есть простое предложение, попробуйте написать ИИ для такой простой игры как крестики-нолики

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

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

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

mr.DUDA
Я не имел ввиду похожесть алгоритмов, подразумевалась своеобразная тренировка в написании ИИ.

December
Что я имел ввиду?

maxim1000

Цитата

точнее, для "точек" сложнее

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

Посмотрел я тот самый Java-вариант точек... Скорее всего, автор "забил" несколько десятков комбинаций ходов, примерно 5x5; начиная ставить точки далеко друг от друга, замечаешь странное поведение компа.

Цитата(TiHo @ 31.8.2003, 14:13)

December Что я имел ввиду?

Рэндзю - это те самые пять в ряд на бесконечном поле (в некоторых версиях поле таки ограничено). Игра, похоже, узкоглазая по происхождению.

в голову только приходит альфа-бета отсечения и без перебора не выкрутиться...

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

beif прежде чем кидать новое следует просмотреть уже написанное, такой вариант уже реализован на здеся если хочешь посмотри и поиграй. Оценка сложности за тобой. И подумай над тем как думаешь ты при игре, ведь ты не перебираешь ходы и не запоминаешь позиции в виде матрицы 3х3 или 5х5, а строишь стратегию.

как движется, Immortal?

Кстати, нужно учесть, что запоминать надо не только выигрышные ходы, но и проигрышные, дабы использовать в дальнейшем ошибки соперника. И нейтральные тоже - в общем, все, в итоге.... Главное - как это все расположить, чтобы не занимало кучу места...
Теперь по поводу самого алгоритма. Я, конечно, алгоритмист хреновый, но как насчет анализа всех "открытых" точек (то есть, не замыкающих область) с просчетом расстояний до других и применением уже известных комбинаций ходов к ним? Кажется, примерно на таком принципе шахматы и работают... Хотя опять же думать она будет долго... Но если отсеить хотя бы откровенно бессмысленные ходы, то можно немного улучшить положение дел