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

Автор: Lapp 7.04.2009 4:12

В этой теме можно обсудить прохождение конкурса Крестики-Нолики.
Просьба соблюдать Правила Форума, Условия Конкурса и уважать собеседников.
Удачи!

Автор: Lapp 23.04.2009 12:10

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

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

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

Дело в том, что я, никогда не занимаясь играми сколько-нибудь серьезно, всегда к ним тяготел. За всю историю своего "свободного" времени я написал несколько простых программ, причем обычно в целях освоения новой техники/теории. Так вот, эти самые of question "крестики-нолики" входили в число моих самых первых творений (на Фортране, интерфейс через АЦПУ, машину не буду называть - смеяться будете)). И еще тогда, посмотрев на результаты моих "гениальных" идей, я понял, что явно недооценивал сложность вопроса.. И я успешно забросил всякие попытки сделать это. Но..

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

.. НО осталась еще одна возможность: возможность загрести жар чужими руками)). И вот какой у меня аргумент..

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

Итак, я вот, что хотел сказать. Не нужно думать, что если вы не чувствуете себя в состоянии программно обыграть хотя бы и трехлетнего ребенка, то вам не следует участвовать в конкурсе. Еще как надо!

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

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

Автор: Lapp 25.04.2009 23:54

Первый Раунд Конкурса Крестики-Нолики окончен. Прислано 0 (ноль) работ.

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

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

В Конкурс вносятся изменения.
1. За проявленные высокие показатели в Конкурсе объявляются премии в виде софта или харда:
- за 1 место: до $100;
- за 2 место: до $50;
- за 3 место: до $25.
Конкретные воплощения предлагаю обсудить.

2. Для занятия призового места участие во Втором Раунде обязательно.

3. Результат Конкурса оценивается как сумма результатов в раундах 2 и 3 с весами 0.5 и 1 соответственно.

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

Автор: Lapp 26.04.2009 21:23

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

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

Да, может. Более того, она как правило меньше, и только при совсем уж тривиальных условиях на доске 3х3 длина выигрышной последовательности равна стороне. Вообще, у нас, когда я был в школе, эта игра называлась "крестики-нолики на бесконечном поле". В качестве "бесконечности" обычно выступал размер тетрадного листа, и на нем обычно умещалось несколько партий. Я также встречал название "пять в ряд", и тут тоже поле обычно не ограничивалось. Собственно, размер 15х15 я взял из восточной игры Рэндзю, которая очень похожа, но есть и отличия (скажу о них позже как-нить).

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

Еще раз спасибо за вопросы)). Я скоро официально объявлю Второй Раунд.


Добавлено сильно позже:
Перечитывал и нашел ошибку в этом своем ответе((. Исправленное в тексте выделено курсивом. Не знаю, как я мог так ошибиться и ответить, что ход нолика..

Автор: Unconnected 26.04.2009 21:35

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

Автор: Lapp 26.04.2009 21:59

А на каком поле ты играл? Боюсь, при таких условиях на полях, больших чем 5х5, игра обречена на ничью при сколько-нибудь внимательной игре противников.

Кстати, это повод поисследовать вопрос оптимальной длины для различных размеров полей. На вскидку могу предположить, что она колеблется между 3 и 5 (случаи 3х3 и "бесконечность" я считаю крайними). Кстати, есть еще игра "Connect 4" (http://www.dazadi.com/Toys-and-Games/Board-Games/Milton-Bradley-Connect-Four-Board-Game.html?utm_source=yahooshopping&utm_medium=shopping&utm_campaign=Milton-Bradley-Connect-Four-Board-Game&CID=yahooshopping можно ее посмотреть), она на поле 7х6, при этом "в поле тяжести", то есть фишки кладутся в щель сверху и проваливаются до дна (на картинке видно, что они все лежат внизу).

Добавлю еще вот, что.. По крайней мере пока я предполагаю в конкурсе в основном использовать игру 15/5 (будем так обозначать пару m/l). Так что советую всем сконцентрироваться именно на такой игре. Хотя, другие размеры не исключаются .

Завтра я приведу тут картинки-примеры партий. А может, дам ссылку на страничку, которую я подготовил для просмотра партий, сыгранных в рамках конкурса. Наполню ее простенькими программами (типа random хода). Тогда будет легче представить себе, о чем собственно речь.

Автор: Unconnected 26.04.2009 22:20

3x3 обычно Про ничью - это да, кстати у нас на поле 3*3 придумали практически 100%-ый способ выигрыша)

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

Автор: Lapp 26.04.2009 22:27

Любые l клеток подряд, в любом месте.

Автор: Айра 27.04.2009 17:19

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

Автор: Lapp 27.04.2009 19:52

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

Иными словами, боишься проиграть? Потому что я не верю, что твоих мозгов не хватит, чтоб написать программу, читающую массив из файла и выдающую два числа в другой файл. Ну, твое дело, наседать не буду..

Сейчас попробую сыграть сам с собой в блокноте)).

Автор: Unconnected 27.04.2009 19:57

Где в интернет можно проверить время исполнения программы?

Автор: Айра 27.04.2009 20:15

Ну уж точно не это) да и опыт поражений у меня имеется.. Мозгу нужно время, времени нужно, чтоб оно было.. А у студентов, как известно, май\коллоквиум\контрольные подкрадываются незаметно)
*сорри за оффтоп)

Автор: Lapp 27.04.2009 21:13

Боюсь, пока нигде..
А какие сложности? Даешь входные данные, запускаешь секундомер и ждешь ответа .

Это не оффтоп, все правильно. Что ж, я могу продолжить этот список - работа, семья, дети, дача, внуки, старость... . Нужно делать все и всегда .
Из этого делаю вывод, что я тебя пока еще не сумел заинтересовать..

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

Начало.  Крестик (Х) ходит в центр, нолик (О) - где-то 
недалеко от крестика.

           x
             o

Стандартное продолжение: Х развивается, О его немного 
сдерживает.

             o
           x
         x   o

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

             o
           x x o
         x   o

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

             o   x
           x x o
         x   o   o

Это требует от Х немедленного закрытия с одного из концов.  
О все же строит свои четыре подряд..

           x
             o   x
           x x o
         x   o   o
                   o

.. а Х их тоже закрывает.  Тогда О снова ставит три - не  
подряд, но практически столь же опасно.

           x
             o   x
           x x o
         x   o   oо
                   o
                     x      

Х встает в промежуток: хорошая защита, но плохо для 
собственного развития.  О делает себе блочок 2х2.

           x
             o   x
           x x o
         x   o x o o
                 o o
                     x      

Х надо защищаться..  Он закрывается слева внизу.  
Правильно ли это?  О сразу делает вертикальную тройку.

           x
             o   x
           x x o   o
         x   o x o o
                 o o
               x     x      

Х срочно закрывается, одновременно делая себе тройку 
внизу.  О легко разбивает эту тройку, заодно делая себе 
еще одну.

           x
             o   x
           x x o   o
         x   o x o o
                 o o
               x o x x      

Х закрывается снизу - удачно, он хорошо сдерживает О и 
развивается сам.  Но О уже трудно сильно навредить: 
еще одна его тройка, по диагонали.

           x
             o   x
           x x o   o
         x   o x o o o
                 o o
               x o x x      
                 x

Х закрывается снизу - ошибка!!  Основные резервы О наверху!  
О продолжает тройку до четверки сверху..

           x
             o   x
           x x o   o   o
         x   o x o o o
                 o o
               x o x x      
               x x

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

           x
             o   x       x
           x x o   o o o
         x   o x o o o
                 o o
               x o x x      
               x x

У Х снова нет выбора - только в промежуток.  Но посмотрите - 
он сделал себе тем самым задел для очень хорошей комбинации: 
две пересекающиеся незакрытые тройки (вилка 3х3).  Но она 
требует еще одного хода, а О не дремлет и ходит именно туда - 
зарубая Х игру на корню и делая себе еще одну четверку.

           x
             o   x o     x
           x x o x o o o
         x   o x o o o
                 o o
               x o x x      
               x x

Х закрывается, но это его не спасает..  О ставит вилку 3х4 
(диагональ и горизонталь).  Это смерть для Х.  В нормальной 
партии он сдается, тут я сделаю еще ход, чтоб пояснить.

           x       x
             o   x o     x
           x x o x o o o
         x   o x o o o o
                 o o
               x o x x      
               x x

Х закрывает горизонтальную четверку.  О продлевает 
диагональную тройку до четверки.  Незакрытая с двух 
сторон четверка - это конец.

           x       x
             o   x o     x
           x x o x o o o
         x   o x o o o o x
                 o o     o
               x o x x      
               x x

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

P.S.
Извиняюсь за формат - нужно было делать с разбивкой, через пробел.. Попробую исправить.

P.P.S.
Все, сделал разрядку - вроде лучше смотрится - да?..

Автор: Lapp 28.04.2009 22:34

Никаких откликов на партию не поступило((. Игра в одни ворота продолжается..


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

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

Партии, представленные здесь сейчас, сыграны теми самыми "куклами", о которых я говорил раньше. Наиболее "развитые" из них названы по именам: Alex, Betty, Catherine. У остальных названия говорят за себя, но если нужны пояснения, я могу дать.

Итак, вот эта ссылка: http://forum.pascalnet.ru/contest/c01/

P.S.
Пожалуйста, не судите строго, утилита сляпана на коленке за короткое время. Если заметите баги - сообщайте.

Автор: Айра 29.04.2009 6:37

Решила просмотреть партию Alex vs Catherine, но на этом шаге все застряло и дальше не двигалось
http://radikal.ru/F/s41.radikal.ru/i091/0904/36/97c2bf492304.jpg.html

з.ы. чет они не многим хуже меня играют)

Автор: Lapp 29.04.2009 9:37

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

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

Автор: Айра 29.04.2009 15:03

Adsl, не уверена, что скорость соединения имеет значение.. просто в определенный момент реакцией на нажатие кнопок перемещения оказывается отображение одной и той же картинки (даже если ты уже выбрал для показа другую партию). Может браузер? У меня FF.

Игралки вродь имеются.. А вот действия народа предсказать не могу Что-то как-то у нас пусто..

Автор: volvo 29.04.2009 15:13

Браузер ни при чем. У меня тоже FF:


P.S. В Хроме на всякий случай тоже проверил, тоже работает...

Автор: Lapp 29.04.2009 21:31

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

Автор: Lapp 30.04.2009 2:12

Занимался аж три часа к ряду.. ничего не нашел. На всякий случай уточнил идентификацию cookies - 43, может они как-то интерферируют с форумскими куками.. Некоторые сложности могут быть, если много раз (раз под 20) зайти, потом закрыть браузер, снова зайти, и т.д. Но мне представляется, что это не тот случай - в логе смотрелки был только один заход. Айра, большая просьба к тебе: проверь еще разок, и если будет снова эта бяка - пожалуйста, пришли мне эту cookie - ту, которая с путем /contest. Контактни со мной в аське, ладно?

И еще: просматривал весь тред и заметил ошибку в своем ответе (тут: http://forum.pascalnet.ru/index.php?s=&showtopic=23953&view=findpost&p=132631 ). Исправил, очень извиняюсь. Как я мог такое сморозить?..

Автор: volvo 30.04.2009 8:28

Андрей, а вот теперь оно перестало работать везде, кроме IE. Шаг назад/вперед не работает нигде больше (в Опере делаются какие-то попытки, но о них я написал ниже), показывается только полная партия. Кэш чистый, куки удалил, и зашел сразу на /contest, без захода на форум, чтоб не было взаимодействия с форумскими куками.

+ Опера после трех шагов "назад" выдает "Ошибка! Соединение закрыто удалённым сервером"

Как вариант объяснения такой избирательной работоспособности: если проверить эту страничку Validate-ором (или просто открыть FF -> View Page Source), то сообщается о смещенном теге </form> (у тебе TD и FORMы "нахлестываются" друг на друга), отсюда на некоторых браузерах может возникать проблема.

Автор: Lapp 30.04.2009 11:11

Ok, все это проверю. Завтра.
Спасибо. Хорошо, что я выложил раньше)).

Автор: Lapp 2.05.2009 3:20

Ну вот, проверил, нашел парочку ошибок. Сколько осталось - не знаю)). Заходите, смотрите, тестируйте.. Я пробовал IE, FF, AS и GC - вроде работает. Еще раз кладу ссылку, чтоб вам не лазить далеко:

http://forum.pascalnet.ru/contest/c01/ .

Всем спасибо и - жду конкурсных работ .