Значитца, по порядку. Сразу предупрежу, что реализацию идеи я взял с потолка, важен только подход к решению задачи. Теперь по существу:
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 аплетов (пока не приобрёл), но если кто шарит, то посмотрите, если это возможно и скиньте сюда принцып работы. (извините за отсутствие, но отсутствовать я буду ещё до середины слкдующей недели, может чуть раньше)