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

[Nataly-Mak]

Предлагаю вниманию форумчан небольшую статью о конкурсе:
http://www.natalimak1.narod.ru/contest4.doc

[General]

11е место - поздравляю!!!

[Nataly-Mak]

Спасибо!

[Nataly-Mak]

Короткий экскурс в историю конкурсов, в которых я приняла участие
http://www.natalimak1.narod.ru/contests.htm

[Nataly-Mak]

Объявили, что следующий конкурс начнётся 1 июня сего года.
Ну, почти полтора месяца отдыха

[Nataly-Mak]

Pavlovsky улучшил рекорд конкурса в игре № 16, на конкурсе был получен максимальный результат 3118, он получил 3125:

16:C0, M2, L1, N0, J0, M0, N3, E12, F13, G5, K4, J3, K1, N5, L3, L0, I4, G9, K11, M7, M9, I5, F11, I9, L8, I9, J10, M10, N0, L2, N10, N10, N10, J11, H7, N9, N9, M1, N3, M3, M5, N6, L5, N5, N5, M5, M0

Пока этот рекорд не побит (браво, Pavlovsky!).

Я попыталась улучшить результат 3125 по своей программе. Покрутила. Интересно, что вариантов решений с результатом 3125 получается куча, например:

16:B0,M2,L1,M1,J0,L0,M3,E12,E13,F5,K4,J3,K1,M5,I4,I2,I4,E11,J11,L7,M9,I5,F11,H11,L8,I9,J10,M10,E7,J11,L10,N10,N10,J11,N9,N9,K2,J9,K6,N7,L6,M6,M6,N3,M3,M5,M0

Этот вариант существенно отличается от оригинального решения последовательностью ходов. Вот до этой позиции всё совпадает:



А теперь в решении Pavlovsky удаляется синий блок, то есть делается ход N0, а в моём решении делается ход E7, и только потом удаляется синий блок. Далеко не всегда такое нарушение последовательности ходов не изменяет результат, в этом случае результат сохранился.

А вот перепрыгнуть этот результат не удаётся.

Второй интересный момент: от этого решения легко получается и результат 3118 (предыдущий рекорд), например:

16:B0,M2,L1,M1,J0,L0,M3,E12,E13,F5,K4,J3,K1,M5,I4,I2,I4,E11,J11,L7,M9,I5,F11,H11,L8,I9,J10,M10,E7,F2,I3,J11,L10,N10,N10,J11,N9,N9,J9,K6,N7,L6,M6,M6,N3,M3,M5,M0

Наконец, последний интересный момент: мне не удаётся получить результат между этими двумя рекордами, то есть такой результат x:
3118 < x < 3125.

[Pavlovsky]

До следующего конкурса более месяца. Можно неспешно поколдовать над рекордами предыдущего конкурса. Анализирую задание №12. Для анализа взял два лучших решения.

wes,"12","12:H4,L5,J10,H13,J4,J12,N10,B8,F5,F8,G6,K8,M9,L9,L4,I11,M8,M8,G2,D1,F0,E11,E2,K13,M8,J3,J0,J4,M9,L3,N8,M0,N1,N1,M1,M0,N0","5139"
spurious,"12","12:G1,I3,H3,K7,F0,E1,J9,F2,H12,J11,M10,F6,A8,I4,L3,F7,K7,M8,L8,I10,L8,E11,L8,M8,I4,K2,J12,F9,N0,M8,M3,J10,M0,N0,N2,N0,K1,M0,M1","5127"

Поменял в них порядок ходов, чтобы выявить одинаковые последователности ходов.

i12,j11,j9,g1,f0,f1,h3,l5,b8,f7,j4,f5,g6,k7,j8,n10,k8,k8,l8,n7,i9,e10,k12,l3,e1,j2,j0,m8,j4,l2,n8,m0,n1,n1,k1,m0,m1
i12,j11,j9,g1,f0,f1,j2,h3,l5,b8,f7,g2,g6,k7,j8,n10,k8,k8,l8,n7,i9,e10,k12,j4,l3,i4,k2,j0,m9,m4,n0,j10,n4,n0,n0,n0,k1,m0,m1

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

[Nataly-Mak]

Вы можете оптимизировать вашей К-оптимизацией последние 20 ходов?

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

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

[Pavlovsky]

Nataly-Mak в сообщении #562922 писал(а):

Вы можете оптимизировать вашей К-оптимизацией последние 20 ходов?

Смысл К-оптимизации в том, что я могу оптимизировать любую последовательность ходов. Совсем не обзательно последние 20 ходов.

[Nataly-Mak]

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

[Pavlovsky]

К-оптимизация позволяет изменять порядок ходов в большом диапозоне. При этом не ухудшает оценку решения по сравнению с исходным.
Пример:
Это рекордное решение для задания №13.
J11, C10, F10, K3, L11, F2, I14, M15, G19, L7, M4, F18, D19, B0, L20, L2, F14, D18, K1, N8, D13, G15, D12, L9, I2, D0, D6, K10, I12, G16, K0, I1, L13, I17, L16, K7, M13, H10, G0, L14, N1, N14, L4, L0, N1, N1, N4, N0, N0, N0

А вот примеры решений после обработки К-оптимизацией.
g19,f19,m20,g18,e18,m15,j14,f14,h15,h16,e13,j11,d10,f10,e12,m11,j9,l7,n8,k10,i12,m13,i17,n16,n13,i10,e6,k7,k3,f2,n4,l2,k1,j2,c0,e0,l0,i1,g0,l14,n15,n1,l4,l0,n6,n1,n1,n0,n0,n0

c0,k3,f2,n4,l2,k1,e0,l0,j2,i1,e6,l7,n8,f10,k7,m9,e10,h10,j11,m11,e13,e12,k10,i12,j14,m15,f14,g18,g19,f19,m20,e18,h15,m13,n13,m16,n16,i16,g0,n1,m4,m13,n14,l0,n1,n1,n0,n0,n3,n0

g19,f19,c0,m20,g18,e18,k3,f2,m15,n4,l2,k1,e0,l0,j2,j14,f14,h15,h16,i1,e13,e6,l7,j11,d10,f10,e12,m11,n8,m9,k10,i12,l13,i17,l16,n13,k7,h10,g0,n1,m13,m4,n14,l0,n1,n1,n0,n0,n3,n0

Все решения имеют рекордную оценку 9842. Специфика К-оптимизации такова, что она с трудом улучшает (или хотя бы изменяет большие группы). Поэтому после 38 хода, перед удалением большой группы, позиции получились одинаковыми. Но если смотреть позиции до 38 хода, то они очень сильно отличаются. А значит можно для каждого решения применять перебор хвостика.

[Nataly-Mak]

Цитата:

Но если смотреть позиции до 38 хода, то они очень сильно отличаются. А значит можно для каждого решения применять перебор хвостика.

Нет, вот как раз перебор "хвостика" здесь ничего не даёт!
После удаления красного блока во всех трёх решениях позиции делаются совершенно одинаковые, вот такие:



И что же здесь теперь перебирать? Для всех трёх ваших вариантов полный перебор этого "хвостика" моментально выдаёт тот же самый результат - 9842.

А уровни до удаления красного блока моя программа не берёт (слишком много вариантов первого хода).

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

[Pavlovsky]

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

[Nataly-Mak]

Ага, а ход назад сделайте и вариантов первого хода становится 18
[а ещё ход назад - и вариантов первого хода 21]!

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

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

[Nataly-Mak]

Спросила на форуме конкурса, можно ли ввести вариант решения головоломки № 16 с максимальным результатом. Ничего не ответили. Смотрю, другие вводят варианты максимальных решений, ну и я сейчас ввела. Этот вариант здесь приведён, он существенно отличается от оригинального решения (автор Pavlovsky) последовательностью ходов.

Стало любопытно провести эксперимент.
Беру из БД конкурса решение А. Чернова в игре № 22:

Alex Chernov,"22","22:
G3,J6,N6,I12,C2,L4,N4,F3,C13,L6,L7,M6,P9,K4,O10,P9,K9,M9,O10,O10,O8,P10,E12,L9,M0,P3,
P13,L13,F2,L12,L13,M14,M10,H0,G1,I8,K12,O0,L8,M0,J2,I11,J3,K10,J1,N0,M0,L9,O1,M8,P3,
P2,M9,N0,P1,M5,M2,N7,P1,O6,O0,P0,P5,O4,P4,N5,P4,O3,P3,P3,O2,P2,P3,P2,P0,
"3295"

У меня в этой игре результат 2565, максимальный результат на конкурсе 3815.

Выбираю исходную позицию в этом решении, всего 10 вариантов первого хода:



Запускаю программу полного перебора окончаний, через 5 минут получаю результат 3314:

22:G3,J6,M6,G12,C2,K4,M5,F3,B13,K6,K7,L5,P9,K3,N10,N11,J10,L10,O10,M10,O7,N10,E12,
L9,L0,P3,O13,L13,D1,L11,L13,L14,M10,H0,G1,I7,K12,N2,L8,M0,I2,I11,I3,J11,J0,N0,M0,L9,F8,
K8,N1,J11,M9,N10,M12,N10,O10,P9,P9,P9,O8,P8,P8,O7,O8,O7,P6,O6,N0,P1,P0,N1,O1,O0

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

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