Солверы для игры Сокобан. Конкурс.

[lepetrandr]

Вообще говоря, тем способом, которым я находил циклические доски, можно находить и доски согласно предложенному правилу "non zero pushes". Просто в этом случае sokoban_scorer пишется чуть сложнее. Я почти уверен что именно поэтому сейчас такие правила, потому что они чуть проще реализуются.

[svb]

dimkadimon, хорошо, что конкурс вызвал обсуждение. Конечно, дело не в претензиях - я думаю, что Gil Dogon хотел прежде всего привлечь внимание к особенностям игры Сокобан и некоторым вещам, интересующим его.

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

И немного о том, что меня заинтересовало. Я попробовал, не вдаваясь в теорию, исследовать уровни 3_L. Доказательства меня пока не интересовали, я просто попытался экспериментировать.
Для примера взял серию уровней вида:

######################
######   #######  ####
######            ####
####### ########  ####
####  # ######## ##  #
###   #  ######      #
#  $ $   ######   #  #
#    ## @########## ##
##$#######  ####### ##
##   #####           #
###  #####  ######   #
###  ###### ##########
##  ####### ##########
##      ...  #########
##  ######   #########
######################

Длину нижнего прямолинейного участка пока не пробовал менять, поэтому эксперимент пока не закончен.
$Score = L\left( {3n + 15} \right) - 12n^2 - 96n - 195$
Для показанного уровня $n=8$ и $L=104$.
Мне кажется, что кого-нибудь заинтересует предложенный подход.

Надеюсь, что конкурс это только начало.

[svb]

$Score =T+ L\left( {3n + 15} \right) - 12n^2 - 96n - 201$
У Петра $T=26$, $L=240$, $n=26$, получаем $Score=11537$.
$T$ - длина нижнего прямолинейного участка,
$n$ - число узлов

[dimkadimon]

svb, несколько вопросов. Что такое узел? Как вы находите эти формулы?

[svb]

dimkadimon в сообщении #1040570 писал(а):

svb, несколько вопросов. Что такое узел? Как вы находите эти формулы?

Некоторые определения имеются здесь. Там нарисован и основной узел из 6 клеток, из которых рисуется "паркет" основного цикла. Для того, чтобы найти формулы, достаточно 5 уровней.

Алгоритм получения формулы для серии с одинаковой базовой областью. Пример серии 4_L
1. Исходные значения
$L_1=68$ $S_1=1197$
$L_2=70$ $S_2=1263$
$L_3=80$ $S_3=1653$
$L_4=82$ $S_4=1735$
$L_5=102$ $S_5=2663$
1 и 2 уровень имеют $n_1=5$ узлов,
3 и 4 уровень имеют $n_2=n_1+2=7$ узлов
5 уровень имеет $n_3=n_1+4=9$ узлов.

2.
$K_1=(S_2-S_1)/(L_2-L_1)=33$
$K_2=(S_4-S_3)/(L_4-L_3)=41$
$k=(K_2-K_1)/2=4$
$c=K_1-k\cdot n_1=13$

3.
$a_1=S_1-L_1(k n_1+c)=-1047$
$a_2=S_3-L_3(k n_2+c)=-1627$
$a_3=S_5-L_5(k n_3+c)=-2335$
$z_1=a_2-a_1=-580$
$z_2=a_3-a_2=-708$

$A=(z_2-z_1)/8=-16$
$B=z_1/2-2A(n_1+1)=-98$
$C=S_1-K_1 L_1-(A n_1+B)n_1=-157$

Окончательная формула
$Score=L(k n+c)+A n^2+B n+C=L(4 n+13)-16 n^2-98 n-157$

[svb]

Замечание.
Для любого числа ящиков $B$ существует базовая область из стаканов, для которых
$k=B$ и $A=-4B$

[dimkadimon]

svb в сообщении #1040580 писал(а):

Для любого числа ящиков $B$ существует базовая область из стаканов, для которых

Что такое "стакан"?

[svb]

Стакан? Из него можно пить, например.

#######################
#   ######  ###########
#           ###########
## #######  ###########
## ####### ############
## #......  ###########
## ########$$ $ $ $ $@#
## ########           #
#  ######## ###########
#            ##########
#  #######   ##########
#######################

Но, вообще-то, я в той ссылке, что давал, приводил пример "стаканов". Еще я высказывал предположения. Потом мне показалось, что рекордная серия 3_L ломает мои гипотезы, но, странным образом и для нее формула похожа. Базовая область из стаканов очень проста и для нее можно получить формулы несложными рассуждениями.