Версия для печати темы

Автор: RathaR 29.09.2009 21:34

Эх...может давайте забадяжим еще один конкурс?
К сожалению последний - крестики-нолики, проводился еще до моей регистрации, и как я понял из его обсуждений, успеха он не имел, НО это ведь не повод отказываться от подобных мероприятий
Побольше рекламы, какоето вознаграждение типа повышения репутации, или особое звание, и я думаю что желающих будет немало... ведь посещают этот форум не только студенты которым одну лабу зделать или курсовую, а еще и заинтересованые люди
что касаеться конкретных предложений:
предлагаю провести чтото типа морского боя, тоесть: учасник пишет програму(не саму игру) которая должна исходя из текущей ситуации на обоих полях определять следующий ход, тоесть две програмы играют между собой, ну как с крестиками ноликами. Программа должна читать из файла оба поля, и принимать решение, после чего вводяться соответствующие корективы в поле. А корабли пусть розполагаються случайно, при каждой игре, тоесть програма учасника - одна единственная процедура которая делает ход. я к чему собственно клоню, в таком случае подобную прогу сможет написать даже школьник, почти ничего не знающий о паскале, и в тоже время даже в этой игре можна придумать уйму стратегий, и ктомуже можно будет организовать чтото типа груповых боёв, пусть за каждую сторону играют по несколько програм которые делают ходы по очереди.
Морской бой - самая интересная и простая игрушка из тех что мне пришли в голову... можно подумать над другими вариантами игр, но я думаю что в любом случае (если програма будет несложной в реализации) люди потянуться человек 10-15 участников должно набраться

Автор: RathaR 29.09.2009 22:32

ок, с пятницы обязательно займусь

Автор: sheka 29.09.2009 23:55

Может я чего - то не понимаю, но какая там может быть особая стратегия? Просто рандом и все! ( разве что для красоты поля выбирать, и явно ложные не выбирать).

Автор: RathaR 30.09.2009 0:54

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

Автор: andriano 30.09.2009 10:11

Наличие выигрышной стратегии в морском бое не доказано. Не доказано даже, что выбор той или иной стратегии способен привести к уменьшению среднего количества ходов необходимых одной стороне для разгрома противника.
Поэтому прежде, чем предлагать конкурс, могу посоветовать сначала поисследовать этот вопрос самостоятельно.
Тем более, что как раз в морском бое для такого исследования не нужен второй игрок: достаточно
1. Придумать N стратегий расстановки кораблей (хотя бы N=2)
2. Придумать M стратегий обстрела (хотя бы M=2)
3. Для каждого из N*M вариантов сочетания стратегии расстановки со статегией обстрела провести K испытаний (K должно быть статистически значимо - могу предложить: квадрат средней длины партии)
4. Получить средние количества ходов необходимых для победы в каждой паре стратегий.
5. На основе 4 сделать вывод, дает ли применение какой-либо стратегии преимущество в игре.

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

Автор: RathaR 30.09.2009 16:09

я наверно сглупил, что не полностью обьяснил свою идею сразу морской бой будет необычный, а именно со стратегией. Кому нибуть приходилось играть в игру на моб телефоне, кажеться Pirates sea battle?, точно названия не помню, но вобщем смысл следующий:
поле 10*10(впрочем розмеры регулируються) на этом поле 4 корабля( 1 5-палубный,1 - 4-палубный, 1-3-палубный, 1-2-палубный). Каждый ход состоит из 3 выстрелов, при этом если у тебя убит пятипалубный, или четырёх палубный корабль, то кол-во выстрелов уменьшаеться на 1, вплот до 1 выстрела за ход. При этом каждый 6 выстрел - можна использовать так называемое супер оружие, это:
1 - указуеш любой столбик или строчку на поле, и по всей этой строчке, или столбике проплывает бомба, ну и если она натыкаеться на враж корабль, то соответсвенно - ранил.
2 - на поле падает одна большая бомба, в виде креста, 5 клеток поражает.
3 - розведка, указываешь поле 3 на 3, и оно розведывается.
4 - указываешь поле 1*5 клеток, и оно соответственно поражаеться.
5 - указываеш поле 3*3, и по нему выстреливаються 4 снаряда, в случайные точки в пределах этого поля.

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

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

Автор: andriano 30.09.2009 19:28

1. Увы, условия сформулированы очень неконкретно и требуют массы уточнений. По такому описанию ни играть, ни разрабатывать стратегию нельзя. Это не придирка: невозможно написать программу на С, Паскале, Ассемблере или любом другом ЯП, если не умеешь внятно описать, что эта программа должна делать по-русски, украински, английски, etc.

2. Усложнения условий никак не говорят о существовании выигрышной стратегии. С другой стороны, этот факт достаточно просто не только проверить, но даже оценить количественно. Как - я писал выше.

3. Все люди разные, у всех разные интересы. Мне, например, вообще неинтересно принимать участие в конкурсах. По моему харакеру лучше принять участие в подготовке, например, выработать условия, сформулировать правила, написать софт, предназначенный для тестирования работ участников и т.п. Другими словами, я скорее ПРЕДЛОЖУ конкурс, чем ОТКЛИКНУСЬ на чье-то предложение. Поэтому делать заключения о том, насколько идея конкурса может быть поддержана участниками форума, мне кажется, неосмотрительно.

Автор: Lapp 1.10.2009 15:28

andriano, в данном случае речь не о существовании выигрышной стратегии, а несколько о другом. Предположим, для простоты, что на поле только один корабль из 5 клеток (допустим, остался). И допустим, ты его ранил. Так вот, стратегия совершенно явно будет такова: стрелять в соседние клетки, а не в противоположный угол поля. Выбор же соседних непроверенных клеток - тоже какая-никакая, а все же задача.. Хотя, лично мне тоже не нравится идея морского боя (и тем более, усложненного).

Я бы и поучаствовал - чисто за компанию.. Конечно, хотелось бы писать что-то поинтереснее МБ. Не совсем понятно, в чем там соревноваться. Стратегия все же есть, но она тривиальная..

Автор: Unconnected 1.10.2009 18:25

Шашки?)

Автор: Lapp 1.10.2009 23:02

Шашки на порядки сложнее тех же самых Крестиков-Ноликов.

Автор: andriano 2.10.2009 14:42

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

В этой связи я вспоминаю первую написанную мною игру (реализация карточной игры "Подкидной дурак" в текстовом режиме CGA). Решив начать с интерфейса, я быстренько соорудил простейший алгоримт принятия решений - лишь бы можно было отлаживать интерфейс. Каково же было мое удивление, когда я обнаружил, что программа выигрывает у среднего человека в 50% случаев или чуть более.
Это к тому, что далеко не все, что производит впечатление чего-то хитрого и осмысленного, таковым на самом деле является.

Автор: TarasBer 2.10.2009 21:39

Вспомнилась байка. Один человек написал игру в шахматы с ботом. Думать над интеллектом ему было лень, поэтому он тупо научил бота делать случайный ход в пределах правил. Бот стабильно всех выносил.

Автор: RathaR 2.10.2009 22:01

Что касаеться морского боя:
под стратегией я подразумевал то, что в случае с обычным морским боем у игры есть одна конкретная цель - уничтожить все корабли противника, а учитывая то что они и однопалубные и четырёхпалубные, достигнуть этой цели можно только случайно, как сказал andriano в МБ нету выиграшной стратегии, Но в ЭТОМ морском бою становиться очевидным то, что тот кто первым потопит 5палубный и 4палубный корабли, тот получит явное преимущество в количестве выстрелов за ход, как я говорил если у тебя потоплен один из этих кораблей, то ты делаеш на один выстрел меньше каждый ход(2 и 1 соответственно). Такчто грубо говоря: хочешь увиличить шансы на победу, а точнее уменьшить шансы противника - топи большие корабли, а вот эту задачу можна решить разными путями, для этого есть супер-оружие(которое используеться раз в 6 ходов), и поэтому программа должна исходя из той ситуации что сложилась втечении предыдущих 5 ходов использовать то оружие, которое именно в даной ситуации окажнеться наиболее эфективным. Все вышеописаные действия дают только преимущество, но не 100% победу, поэтому вместе с этим простой случайный обстрел не теряет своей актуальности
Исходя из всего выщеописаного, я и решил остановить свой выбор на этой модификации МБ.
НО я ведь ничего не утверждаю, а только предлагаю Интересно выслушать ваши предложения

З.Ы. Но всётаки уж очень хочеться поучаствовать в каком либо интересном конкурсе поэтому жду предложений по поводу самого предмета конкурса

Автор: RathaR 4.10.2009 15:23

Рас уж никто не высказывает других предложений, продолжу по поводу модифицированого МБ.
Программа которую должен прислать учасник будет довольно простой в реализации, она просто должна делать выстрелы(в худшем случае случайно, в лутчем по определённой схеме), уметь добивать корабли(чтоб не стреляла куда попало если уже есть подбитый корабль), и каждый шестой ход она должна выбирать тип супер-оружия для выстрела, ну и соответственно координаты, куда им стрелять(то что выстрел каждым типом оружия спецыфичен, и как надо указывать координаты точки дложно быть описано в правилах конкурса). А для того чтобы программы с заложеной стратегией успевали реально себя показать, число партий можно увеличить скажем до сотни... незнаю может загнул, но впринципе я не думаю что каждая игра будет продолжаться очень долго... зато в результате получим реальную оценку возможностей прграм...

Автор: andriano 4.10.2009 22:05

Если ты серьезно предлагаешь конкурс, то тщательно сформулируй две темы:
1. Правила игры.
2. Условия, которым должна удовлетворять программа, чтобы выдержать автоматизированную проверку.
Ну и, естественно, нужно подготовить для конкурса набор сервисных программ, которые будут обрабатывать программы участников, проводить матчи, получать результаты и подводить статистику.

Автор: RathaR 4.10.2009 22:23

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

Автор: andriano 5.10.2009 9:52

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

Автор: RathaR 8.10.2009 14:55

По поводу МБ:
пусть на поле размером P на Р клеток, розмещены несколько кораблей, величиной в N палуб, тогда для того чтобы потопить все корабли, со 100% вероятностью необходимо сделать P²/N выстрелов, стреляя по диагоналям, с интервалом N-1 клеток, между диагоналями, тоесть за P²/N выстрелов мы в любом случае обнаружим все корабли. Таким образом должна действовать програма, стрелять по диагоналям, и как можна ефективнее использовать супер-оружие для добивания/обнаружения кораблей в промежутках между диагоналями. Впринципе можна задавать размеры поля и кол-во кораблей, а также их величину как параметры, и смотреть как програмы будут вести себя в условиях разных масштабов сражений.

Но, посетила меня еще одна мысль по поводу предмета конкурса, а почему бы не "Покер Джокер"(может и бред написал, но гдето видел что именно так назыветься), тоесть покер на костях.
Правила
оба игрока по очереди кидают по 5 кубиков, после этого первый выбирает какие кубики он будет перебрасывать, перебрасывает, затем теже действия выполняет второй игрок, а побеждает тот у которого сильней комбинация:
пара - две кости одинакового достоинства;
две пары - две пары, например 1,1,2,2,3
триада - три кости одинакового достоинства;
стрит - пять костей подряд, это 1,2,3,4,5 или 2,3,4,5,6;
фул - пара + триада;
каре - четыре кости одинакового достоинства;
покер - пять костей одинакового достоинства;

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


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


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


Прикрепленные файлы
 KOSTI.PAS ( 16.22 килобайт ) Кол-во скачиваний: 371

Автор: andriano 8.10.2009 20:55

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

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

Автор: RathaR 8.10.2009 21:08

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

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

Автор: Lapp 9.10.2009 2:05

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

Автор: RathaR 1.11.2009 11:57

Ну что ж... Давайте тогда подумаем над тем, какая игра, или клас игр подойдёт для конкурса.
Примерные критерии:
1) Отсутствие стопроцентной выиграшной стратегии, и "ничейной смерти". Я думаю, что будет глупо если программа кого-нибудь из конкурсантов будет сводить все игры в ничью...
2) Элемент случайности. Я думаю что он дожен присутствовать, хотя его значение - спорный вопрос...
3) Сложность алгоритма действий. Эта игра должна иметь "гибкий алгоритм" незнаю как иначе выразиться. Тоесть дожно быть большое кол-во очевидных, и не очень способов игры... ну чтобы программы не действовали по одному алгоритму, пусть даже с разными реализациями... хотя это в большей степени зависит от програмиста, чем от игры. Вобщем я также подразумиваю то, что программа может быть написана за 20-30 минут, и хоть немного уметь играть, а может за час за два, и будет отлично играть.(Аналогия - морской бой: одна програма среляет просто случайно, а другая еще и проверяет вообще возможно ли наличие корабля в той клетке куда она собираеться стрелять, и впринципе обе проги можна считать полноценными.)
4) Сложность реализации должна быть невысокой, как я уже говорил, чтобы средний студент-програмист мог без проблем реализовать все поставленые задачи, в хотябы примитивной форме (как в аналогии про морской бой), потратив при этом не более часа, а если его попрет, или появиться интерес, то он дальше пойдет совершенствовать програму.
Вроде всё... может быть я чтото упустил?
Крестики-Нолики, я полагаю, были предметом первого конкурса не потомучто они лучше всех подходили, а потомучто просты, и извесны всем.
Если будущие конкурсанты смогут участвовать в выборе предмета конкурса, я думаю это только прибавит желающих поучаствовать.
Выдвигайте варианты игр, добавляйте критерии, вобщем думаем!

Сам я, по прежнему, считаю что "Покер на костях" - неплохая кандидатура. Но еще хочу добавить, может стоит задуматься над карточными играми? Например "Очко", или даже "Дурак" он помойму не настолько сложный чтобы сбрасывать его со счетов:

Автор: Unconnected 9.11.2009 14:44

У меня тут возникла небольшая идея... Не знаю, вызовет ли она одобрение, отторжение или ещё чего-то, но всё же:) Так вот, иногда я играю вот в http://klavogonki.ru Довольно увлекательно, а главное, полезно. И я подумал, может, провести подобное соревнование, но в рамках форума?(никогда не понимал написание нарицательного с большой буквы) С программированием, правда, тут связи мало (если, конечно, кто-нибудь не напишет бота)), но всё равно соревновательный элемент есть) Относительно реализации, можно использовать хотя бы вышеприведённый сайт... Хотя об этом ещё рано думать, пока что высказываемся:)

Автор: RathaR 9.11.2009 17:01

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

А конкурсы между форумчанами можна проводить и в разделе "Свободное общение"

Автор: Unconnected 9.11.2009 18:23

Я же сказал, что к программированию отношения не имеет... Просто, ради интереса:) У меня вот десятипальцевый слепой сам по себе выработался, и я сейчас этим доволен, как слон)

Автор: Lapp 10.11.2009 11:51

Просто ради интереса - в Свободном.