Давайте напишем игру "Точки". Это будет самая простая игра, но хоть что-то мы, но сделаем. В общем суть игры заключается в том, что дано поле состоящее из квадратов. Точки можно ставить на углах квадратов. Точки ставятся поочередно, то одним игроком, то другим. Требуется закрыть как можно больше точек. Заготовка игры уже есть, теперь дело пока что остановилось на написании логики игры, т.е. компьютер должен определять что точки находятся в окружении точек противника, он должен все это прорисовывать. Точки можно соединять если они находятся на расстоянии одной стороны или диагонали квадарата. Да, и еще, если через в квадрате проведена одна диагональ, то если на двух оставшихся сторонах квадрата есть точки противника, то их уже нельзя соединять. Вот такая игра. Предполагается еще добавить поддержку сетевой игры, так что все кто желает, давайте попробуем сделать такую игру.

email: [email protected] - стучите сюда.

язык?

Цитата(setq @ 12.12.2005, 18:50)

язык?

Все это на VB. Не надо сразу плеваться только потому что это VB. Этой игре не нужна 3D графика со всякими там наворотами. Этой игре нужно просто нормально представление и это представление реально написать используя VB и форму (на которую кстати нежелательно помещать никакие компоненты, вся прорисовка идет через line, circle и т.д)

Зачем изобретать велосипед?
http://www.mega-forum.net.ru/files/poseidon/tochki.exe

Написана на Delphi7

Цитата(Poseidon @ 13.12.2005, 02:13)

Зачем изобретать велосипед? http://www.mega-forum.net.ru/files/poseidon/tochki.exe Написана на Delphi7

Слышь, молодец!!! Мне очень понравилось. А ты можешь свой секрет раскрыть. Особенно как определять то что точки окружены точками противника и еще ИИ. Блин, очень был бы благодарен.
Если можешь, я бы тебе исходник на VB кинул бы, ты бы внес коррективы.
Добавлено @ 01:51
Да, кстати, я бы советовал тебе добавить сюда поддержку сети.

Почитай для начала тут. Очень хорошая статья.

А еще есть форум, полностью посвященный точкам. Загляни туда. Особенно в раздел "Программистам".

Poseidon
а че она так тормозит?)

Думает

Когда именно тормозит?

Poseidon
ДА , по-мойму слишком долгий процесс подсчёта возможных вариантов+)
Интересно, можно ли оптимизировать, а то ,чем больше играешь , тем дольше думает =(

Цитата(Sheridan @ 11.1.2006, 00:21 )

Интересно, можно ли оптимизировать, а то ,чем больше играешь , тем дольше думает

Думаю можно (используя параллельные потоки ). Писалась-то она так, "на скорую руку", да и не мной по-началу. Это только потом я за нее взялся...
В общем посмотрю что можно придумать

Poseidon

Ну это я в принципе...
Просто игра в моем представление не должна так тормозить
А так все остальное сделано классно, мне понравилось+))
Только одно плохо, выигрывает она меня часто

Помню года 3 назад ,что-то похожее пытался реализовать на Паскале, но что-то не пошло, написал морской бой
Правда обидно игры не осталось Затерялась где-то=)

Это сообщение отредактировал(а) Sheridan - 11.1.2006, 01:37

меня вот всегда написание искуственного интелекта приводило в ужас. ну не представляю я, как это всё делать... поэтому игры у мя все только юзер против юзера))

Блин, ребят, вы можно сказать, заставили меня поднять запылившийся проект. В общем вылаживаю версию 0.40 (спасибо Скибину Виталию, он знает за что ). http://www.mega-forum.net.ru/files/poseidon/tochki_v040.exe (245.5 kB)

Добавлено:

• возможность играть с помощью клавиатуры;
• возможность изменять размеры игрового поля;
• горячие клавиши для разделов меню;
• иконка
• ну и безусловно улучшен алгоритм ИИ в сторону ускорения процесса мышления (быстрее думает в общем )
• может еще что, уже не помню...

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

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

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

Poseidon
супер!!!я выиграл первый раз в жизни!!!!

Poseidon
Круто!!+)
И вправду пошустрее стал...=)

Есть тема написать сетевые крестики-нолики. Не обычные 3х3, а на произвольном (задаваемом) поле.

еси без ИИ, я могу) на JS + HttpRequest

В этой теме это как бы оффтоп Создавай новую...

Как ты представляешь игру против компа без ИИ? Ну можно конечно с помощью random, но это не выход . А игра человек-человек only не получит достойного внимания.

Ты очееень ошибся!!!!!!!!!!!!!!
Добавлено @ 00:15
Кстати, насчет доработок, сделай хотя бы разброс уровней побольше, ну например 0..10.
Добавлено @ 00:20
Кстати, не тормозит теперь - это очень радует.

Зачем? Я вообще подумываю сделать "Новичок", "Любитель", "Профессионал" => только 3 уровня.

Не, четвертый уровень пока еще подтормаживает, особенно при нестандартных ходах. Но и третий выиграть не так и легко
Сессия скоро. Сдам, сделаю подсчет лучшего хода в параллельных потоках. Можно будет еще больше вариантов обрабатывать за секунду... Предлагайте еще идеи по доработке или новым фитчам.
Вот мой план по доработке:
План совершенствования программы "Точки"
Что сделать

0.Рефакторинг:
• Вынесение вычислений в отдельный поток
• Разделение программы на блоки по функциональному назначению : на
  
• интерфейс(2 формы - главная и диалога)
  
• движок(логику), реализующий логику и ИИ, имеющий ограниченное число открытых методов а также спсобный отрисовать свое состояние на HDC
  
  1.Функциональность:
• Скорость и качество игры компьютера
• Нерекурсивная реализация поиска в глубину
• Применение некоторых положений из статьи Торгашова Павла http://pointsgame.narod.ru
• метод ветвей и границ
• Применение поля размером больше на 2 по всем измерениям для того , чтобы крайние точки как фиктивные обеспечивали автоматический выход из циклов. Не нужно тогда будет проверять в циклах выход за пределы игрового поля
• Оптимизация процедур проверки окружения и контрокружения вплоть до ассемблерной
• Поиск шаблонов
• Поиск стратегических алгоритмов
• Сетевая игра через интеренет(Но без необходимости введения IP-адреса компа. Очевидно, нужен центральный сервак)
  
  2. Интерфейс:
• Загрузка названий пунктов меню из текстового файла(типа как у FlashGet)
• Английский интерфейс
• Оптимизация относит. размеров точек при любом разрешении
• Устранение мерцания при ходе компьютера(запуск продумывания отдельн. потоком и оставление всех пунктов меню доступными для нажатия)
• Инсталлятор и автоматическая ассоциация типов файлов
• Устранение проблемы отображения вопросиков вместо меню на некоторых нелокализованных системах
• NewGameDialog не всегда запоминал последнй уровень и размер поля-исправить
• Файл tochki.ini с информацией про размер поля и игровые настройки, положение и размер окна программы

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

Это сообщение отредактировал(а) Poseidon - 18.1.2006, 01:44

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

Пусть делает, я же не запрещаю. Но 3D точки наврятли будут популярны, т.к. все привыкли в жизни играть на листике в "клеточку", поэтому если будут навороты типа 3D, то это только отпугнет игроков. В интернете существует достаточное количество версий точек, но большинство из них не учитывает данную особенность и теряют в популярности. Игрокам превычнее двухмерная сетка, и даже если ее нет (встрачались мне такие версии), то это уже отталкивает. Во фразе "отрисовать свое состояние на HDC" не имеется ввиду отрисовывать точки, имеется ввиде отрисовывать состояние ИИ. Т.е. сколько ходов просчитано, сколько вариантов, коэфициент "хорошести" хода и т.п.

Не понял вопрос! Ты хочешь узнать, как определить обведена ли точка противника? Если да, то прочитай хотя бы статью Торгашова Павла . Именно с этой статьи начинают практически все кодеры точек. А вообще зачем начинать новый проект, если можно доработать этот? Я только рад помощи и реализованным идеям.

В данной версии одержать победу можно совершено без напряга, например по следующему алгоритму:

Программа всегда старается поставить точку ближе к внешнему краю. По-етому можно воспользоваться етой слабостью.
Т.е. "состовляете" прямоугольник не допуская ходов по диагонали отступив немного (например 2 клетки) от края. Компьютер в ответ будет пытаться "обвести" ваш прямоугольник своим, но так как ваш прямоугольник меньшего периметра он замкнётся на нескоолько ходов раньше и у Вас будет время прегородить путь компьютера. В принципе победа Вам обеспечена - как только компьютер поставит точку внутри Вашего прямоугольника, так сразу контур прямоугольника замкнётся. Но ето будет победа 1:0. Чтоб выйграть с более внушительным результатом, начинайте делить свой прямоугольник на клетки (пополам,потом опять пополам и т.д) Как только у компьютера не будет хода на зоне вне вашего прямоугольника, он начнет ставить точки внутри "подготовленных" Вами клеток. Имено для того чтоб у Вас было время разбить прямоугольник на клетки, я и предложил отступать две клетки, а не одну. 

После некоторой тренировки (нможно конечно просто посчитать) легко определить нужный отступ.

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


 

 Вы сами-то пробовали? Версия 0.40 пытается обвести ваш прымоугольник изнутри. Т.е. ставит точку ближе к центру, а не краю.
  

Это сообщение отредактировал(а) Poseidon - 27.4.2006, 23:50

Для убедительности моих слов привожу скриншот игры.Победа (счет 80:0 в пользу игрока) основана на алгоритме описанном выше.


Начал игру с точки в верхнем  левом углу (2,2)



На рисунке явно видно обратное 

Добавлено @ 14:17 
Ето не единственная слабость етой программы. Легко окружить точки если окружать не сплошной линией, а с разрывами.

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

Испробовал другой алгоритм (змейкой).  Результат (поле 20х20)  149:0 в пользу игрока. При етом максимально возможный (но недостижимый) результат 200:0


Так что с ИИ надо что-то делать....  

Это сообщение отредактировал(а) mes - 30.4.2006, 01:13

Молодец   


 Буду что-то делать 
 

как бы вы не мучались, а бот он и в африке бот... лучше сделать норм. сетевую игру 

Не хочу огорчать, но ИИ боле менее нормальный в природе пока что отсутствует. Обсуждения на подобные темы ведутся и на сайтах, посвященных игре Го (если кто не знает, очень похожа на "точки", уж тем более с точки зрения создания ИИ). Не смотря на мощную поддержку (спонсоры, премиальный фонд программистам, большое количество участников со всего мира) программу с ИИ (играющем на уровне хоть чуть выше среднего) пока что не удалось создать.
Что касается той программы с ИИ, представленной здесь, то она проигрывает в хлам (тестировал на поле 9х9, максимальный уровень сложности).
Лучше пока что направить силы на улучшение условий для игры по сети... На сайте любителей точек (www.pointsxt.ru) уже создана неплохая версия для игры по сети... может объединить усилия и сделать еще более лучший продукт?
С уважением, Владимир.
P.S.: если интересно, то могу дать ссылки и на сервера по Го
P.P.S.: с удовольствием сыграю с кем-нибудь по инету в "точки" 

Это сообщение отредактировал(а) vms - 23.5.2006, 13:46

 А я и не претендую на премию в этой области. Игра писалась по просьбе друга за выходные. Там многое через Ж сделано. В том числе и ИИ. Так что вот так 
 

Я вот как то на спор на ajax за один день написал точки для игры в браузере через интернет.
После этого родилась идея сайт сделать Игра "Точки", "Дурак" и т.д.

ifinchuk, или я не разобрался, или на вашем сайте нельзя играть против машины. Конечно, с человеком играть интереснее, но суть топика была в том, что бы создать именно игру с ИИ.

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

Все реально и все уже давно придумано. Осталось только реализовать 

если напишите игру с AI равным по силе 1-му дану вы получите 1 000 000 $. Дерзайте)

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

На самом деле, возможно лишь НЕСКОЛЬКО вариантов: поставить точку где-то в середине, поставить точку вблизи границы, поставить точку вблизи угла. Подробная характеристика позиции, на мой взгляд, не нужна. Трудно вообразить, что где-то в середине есть клетка, ход в которую будет хорошим, притом, что ход в соседнюю клетку -- плохим. А раз не видно разницы, как говорится, то зачем платить больше?

То есть, мне кажется, что игра должна анализироваться на двух уровнях, на стратегическом и на тактическом.

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

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

Сражения рассматривается на тактическом уровне. На этом уровне можно рассматривать зону, допустим, 5 на 5 точек в районе, где происходит непосредственное столкновение. Этот район не такой уж и большой, для него можно применят обычную технику поиска эффективного поведения.

То есть, в "сознании" программы игра должна выглядеть так.

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

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

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

Тактическая площадка состоит из отдельных точек и на ней ведётся обычный перебор вариантов, эвристики и т.п.

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

Проблема такого построения программы будет в грамотном подборе оценок важности и сопоставления стратегической и тактической важностей. 

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

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

Мне кажется, тогда Го похожа на Реверси. В Реверси тоже есть выгодные позиции. 

Врочем, про Го я ничего не знаю, говорил именно про точки. Играется на листочке бумажки в клеточку, размер поля не фиксирован. Иногда даже неясно, где точно проходят края. Никаких выделенных точек там точно нет. Хотя, конечно, если поставить точку с краю, то её уже не окружат.

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

Прочитал в Википедии про игру Го. По моему мнению, она не похожа ни на точки, ни на реверси. Это совершенно отдельная игра. 

От реверси отличается тем, что фишки противника не становятся своими, а снимаются с доски. 

От точек отличается тем, что во многих случаях можно ходить внутрь захваченной противником территории. Собственно, и территории там никакой нет.

Все три игры имеют разные правила захватывания. В реверси нужно поставить своих на концах линии, в точках надо построить замкнутый круг, а в Го надо лишить "дыхания".

Чтобы написать программу для игры в Го надо какое-то время поиграть в игру, чтобы познакомиться с тем, как решает задачу мозг. А потом воплотить. Так что по Го я пас.

А вот над точками можно подумать.

А миллионы-то за какую игру дают, за Го или за точки? За Го наверняка!

Миллионы дают за го. И что-то мне подсказывает, что к тому моменту, когда задача будет решена, сумма не раз подрастет... Я читал, что как-то на одном турнире одна участница (по совместительству - один из сильнейших игроков в го с мире) сыграла против компьютерной программы. Программе давалась фора в 25 камней, но она проиграла. То есть это результат аналогичен результату новичка, играющего в го несколько месяцев. А это была сильнейшая программа, которая разрабатывалась с начала 80-х... (Статья про это была в "Компьютерре" где-то лет 5 назад, события происходили в конце 90-х - начале 2000-х). Так что кому там хотелось миллионы заработать - вперед и с музыкой   


А я вот со своим мозгом не дружу...   Сколько ни пытался придумать, как он задачи решает, так ничего и не придумал... Может, специальную литературу почитать?

хочеш создавать игры ? 

http://foryour.isgreat.org/ заходи и читай....если что пиши