Новый конкурс программистов

[photon]

Alexu007 в сообщении #534004 писал(а):

Лучшесть результата - это наличие на поле более длинной последовательности.

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

[Nataly-Mak]

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

Покажу свои результаты в первых 10 играх:

1 284 345 0.823188 01-21-2012 @ 17:00:26
2 676 693 0.975469 01-31-2012 @ 08:33:52
3 1334 1468 0.908719 01-31-2012 @ 09:13:09
4 1495 1734 0.862168 01-25-2012 @ 10:14:27
5 3749 4255 0.881081 01-26-2012 @ 20:05:41
6 4222 4833 0.873577 01-26-2012 @ 20:06:11
7 8693 9746 0.891956 01-31-2012 @ 12:35:33
8 883 1309 0.674561 01-31-2012 @ 11:53:51
9 1643 2484 0.661433 01-24-2012 @ 07:44:05
10 1447 2249 0.643397 01-31-2012 @ 13:38:12

Около 15 баллов, место 25-ое (из 60 участников).

Конкурсанты очень активны, по крайней мере те, что находятся в верхней половине таблицы рейтинга. Обновления так и сыпятся; там сейчас показывают ввод обновлений участниками (новшество).
Сегодня опять найдено несколько новых рекордов, в частности, в игре №20. А у меня эта игра самая безнадёжная, всего 480 очков. И никак не улучшается! А рекорд получен 1604 очка (предыдущий рекорд - 1582 очка - принадлежал А. Чернову; кстати, он уже на 4-ом месте). У меня нет даже 30% от рекорда. Очень сложная для меня эта позиция.
Попробуйте!

[Nataly-Mak]

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

А я хочу предложить одну задачку. Вот эта позиция у меня получилась в игре № 7:



Вопрос: можно ли свести эту позицию к бонусу, то есть полностью очистить доску?

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

Вроде не так много осталось вариантов в окончании игры, однако с ходу всё не проверяется. Это ручная игра.

[Nataly-Mak]

Задачу решила, довести позицию до бонуса удалось с результатом 8794.

Если кому интересно, могу привести окончание игры.

Но это ещё не максимум в данной игре, лучший результат на конкурсе 9746. Мне ещё далеко до этого результата.

[Nataly-Mak]

Продолжаю сражаться в игре вручную
Уже имею 18,964 баллов, 23-ье место.

А здесь прямо полный покой, никто никак не сражается

Написала пример алгоритма полного перебора окончаний
http://www.natalimak1.narod.ru/gameALG.doc

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

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

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

Кстати, чуть выше приведена позиция в игре № 7.
При ручном доигрывании я получила результат 8794. Можно ли получить больше из данной позиции? Ответ на этот вопрос даст как раз полный перебор окончаний.

Желающих помочь с программой прошу писать в личку.

[Nataly-Mak]

У меня уже 19,6 баллов, 25-ое место.

Тут хоть кто-нибудь ещё играет? Обалдеть! Такой форум и... ни одного участника в конкурсе что ли?

Нашёлся добрый человек на форуме ПЕН, написал несколько дней назад программу по моему алгоритму полного перебора окончаний. Ровно два месяца я сражалась вручную, не имея никаких программ. Ну, вот несколько дней гоняю программу полного перебора окончаний. Некоторые улучшения нашла, но весьма незначительные. До программы у меня было 19,3 баллов, а сейчас 19,6.

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

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

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

В общем, программка, конечно, очень примитивная и толку от неё маловато, хотя и не совсем без пользы.

Придумала, как немного модифицировать эту программу, но опять же сама не могу

У меня в ручной игре получилось несколько окончаний с "паркетом", а также с другими красивыми фигурками. Покажу три "паркета", это в играх №№ 6,8,12:

[Nataly-Mak]

Вот хочу показать пример работы программы полного перебора окончаний.
Это исходная позиция в игре № 14



На картинке видно, что имеем всего 10 вариантов первого хода (это, собственно, главный параметр, по которому я ориентируюсь; автор программы написал, что оптимальный случай, когда вариантов первого хода 9-10; однако тут случаются очень удивительные вещи: иногда при количестве вариантов первого хода равном 10, программа работает часами, как в привнедённом здесь примере, а иногда при количестве вариантов первого хода равном 12-13 программа отрабатывает за несколько минут).

Результат, полученный в ручной игре, 1044 очков. Первое улучшение в программе появилось на 79-ой минуте, 1091 очков. После этого программа работала ещё около 9 часов, нашла ещё одно смехотворное улучшение - 1092 очков. Вот такой случай.
Больше я такие эксперименты не провожу, если после одного часа работы программы улучшений не получено, прерываю программу.

[Nataly-Mak]

Вчера удалось с помощью программы найти бонусное окончание в игре № 23.
О! Это очень красиво получается. Вручную такое сделать очень сложно!

Вот картинка финала игры:



Этот результат принёс мне сразу 0,12 балла. Это для меня ну очень много

Сейчас буду пробовать найти бонусное окончание в игре № 22, потом в игре № 21.

[Nataly-Mak]

Игры №№ 19, 21, 22 не поддались пока в смысле бонуса. А вот в игре № 18 только что поймала бонус
Правда, улучшение не очень получилось (с 3283 до 3376), но всё равно довольна, бонусное окончание - это красиво. Зачарованно смотрю, как квадратики друг к другу присоединяются с каждым ходом, образуя всё новые и новые блоки, и так до самого конца игры, когда на доске не остаётся ни одного квадратика.

Повторюсь: в ручной игре так сложить квадратики очень сложно.

[Nataly-Mak]

Конкурс заканчивается.
Пока у меня 17-ое место; 20,928 баллов.

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

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

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

(Оффтоп)

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

[Nataly-Mak]

Можно сказать, что конкурс закончился, осталось 28 минут

Красиво получилось

[Nataly-Mak]

Сейчас отписалась на форуме конкурса. Конечно, сообщение перевела на английский язык в Гугле.
Привожу полностью это сообщение:

Цитата:

Спасибо за конкурс!
Было очень интересно играть.

У меня сначала не было никаких программ, я решала задачу вручную. Так было два месяца.
Потом товарищ по форуму написал программу по моему алгоритму полного перебора окончаний, это представлено здесь:
http://e-science.ru/forum/index.php?sho ... 028&st=120

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

Пример
Решение в игре № 23 с результатом 3988 (получено вручную, без бонуса):

23:I5,L8,J7,L8,K6,O8,N6,M5,L9,L8,I11,L9,K11,L12,K12,L15,I14,O16,M15,M15,H15,G18,M16,M19,J19,J17,J18,I10,I11,I9,L6,M6,O8,N3,K5,J3,P4,O5,O3,N2,P2,O3,O2,L1,M2,M0,M3,I4,L3,O6,M1,O20,G18,K22,L21,H19,J19,J18,P22,N21,N20,P18,G12,J12,H13,G13,I13,N0,N1,O0,N0,L1,L0,L1,J16,O19,G22,J21,H20,L21,O20,N19,P19,O20,M21,P17,P14,M18,O19,O20,N17,O17,N1,M11,M10,O12,P12,M10,P11,O9,N8,O9,N9,P11,P8,O6,O4,O5,P5,O4,P3,O3,O1,P2,P2,P2,L0

Выбираю исходную позицию:
I5,L8,J7,L8,K6,O8,N6,M5,L9,L8,I11,L9,K11,L12,K12,L15,I14,O16,M15,M15,H15,G18,M16,M19,J19,J17,J18,I10,I11,I9,L6,M6,O8,N3,K5,J3,P4,O5,O3,N2,P2,O3,O2,L1,M2,M0,M3,I4,L3,O6,M1,O20,G18,K22,L21,H19,J19,J18,P22,N21,N20,P18,G12,J12,H13,G13,I13,N0,N1,O0,N0

Здесь 23 варианта первого хода.

Оцифровываю исходную позицию:

24,16,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,4,0,0,0,0,0,0,0,0,0,0,4,0,0,0,3,0,0,0,0,0,0,6,5,6,0,0,5,0,0,0,0,5,0,0,2,0,0,0,1,0,5,3,0,0,0,5,5,4,0,1,3,0,0,0,0,2,0,3,3,5,0,0,1,0,2,3,0,0,0,4,3,4,0,1,1,0,0,0,0,3,0,4,2,6,1,4,2,0,6,4,0,0,0,6,2,4,1,3,2,0,0,0,0,1,5,2,5,6,4,2,2,6,2,2,0,1,6,5,3,3,1,2,3,0,4,0,0,3,4,3,6,3,2,2,4,6,2,2,2,2,6,1,3,1,4,5,5,6,4,5,0,2,4,2,5,2,2,2,2,2,2,4,2,2,6,5,6,6,4,4,2,6,5,6,0,2,2,2,2,2,2,5,1,6,2,6,2,2,5,1,4,3,1,5,2,3,6,5,1,2,2,2,2,3,6,2,3,3,2,2,2,1,4,6,2,6,2,3,2,2,2,2,2,2,6,2,5,6,2,1,4,2,2,4,2,2,2,2,6,5,4,6,2,2,2,6,1,5,2,2,6,1,2,4,6,6,1,3,3,2,5,5,1,4,

и запускаю программу случайного перебора.

Программа быстро находит лучший вариант решения (два часа!). Теперь полученное решение дорабатываю по программе полного перебора окончаний.
И получаю решение с бонусом! Результат 4828.

23:I5,L8,J7,L8,K6,O8,N6,M5,L9,L8,I11,L9,K11,L12,K12,L15,I14,O16,M15,M15,H15,G18,M16,M19,J19,J17,J18,I10,I11,I9,L6,M6,O8,N3,K5,J3,P4,O5,O3,N2,P2,O3,O2,L1,M2,M0,M3,I4,L3,O6,M1,O20,G18,K22,L21,H19,J19,J18,P22,N21,N20,P18,G12,J12,H13,G13,I13,N0,N1,O0,N0,P20,L1,O21,I11,G17,K4,F22,G22,J16,L10,P4,N10,P2,P4,M8,L12,N7,F22,I1,L0,I21,O11,L14,O18,O5,P12,P18,L19,P15,O14,L12,P11,O12,P11,P11,P11,N11,P11,M14,P9,O10,O11,O10,O8,N8,O7,O3,P3,O2,O1,O1,P2,O0,P1,P1,O0,P0
У меня возникли проблемы в написании кода: определение одноцветных блоков, составление и хранение списков этих блоков и дальнейшая работа с элементами этих списков. Теоретически я это знаю, а реализовать не смогла. Товарищ на форуме оказал мне техническую поддержку, написав программы по моим алгоритмам.

Здесь приведён конкретный пример использования двух имеющихся у меня программ: случайного перебора и полного перебора окончаний.

[Nataly-Mak]

На форуме конкурса выложили максимальные решения:
http://infinitesearchspace.dyndns.org/c ... -aftermath

Беру из таблицы максимальное решение в игре № 23, 6844.
Запускаю для него программу полного перебора окончаний, через 20 минут получаю результат 6852:

23:F13,D11,N3,M0,G20,K22,O12,H21,P2,N11,M3,L15,D18,I5,L8,O8,G13,O20,L21,D1,J7,M16,
E15,M15,H19,N14,H3,J21,L12,J11,H7,K6,F20,H1,G18,L10,M19,L9,G9,K18,I19,E22,N0,H3,E23,
N20,N21,P18,L14,P22,O16,L0,J9,N0,N1,L6,M1,L6,O22,J23,J2,N6,M22,M1,O8,L8,I0,I13,J15,
H13,N1,M2,N22,M3,M13,O19,N16,P4,O8,L6,O5,O6,M5,J16,O14,P12,N13,O15,N14,N10,M12,
P11,P10,N9,O8,O8,P5,M3,N4,O1,P0,O0

Такое впечатление, что автор максимального решения не делал полный перебор окончаний
У него работал другой алгоритм!

[Nataly-Mak]

Более точная ссылка на таблицу максимальных результатов:
http://infinitesearchspace.dyndns.org/s ... metops.csv

На форуме ПЕН Pavlovsky тоже нашёл несколько улучшений максимальных результатов.
Плохо работали авторы этих рекордов, не довели решения до ума

[Nataly-Mak]

Мой рекорд в игре № 23 уже побили