2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение25.07.2015, 15:07 


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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение25.07.2015, 15:12 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение25.07.2015, 17:00 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение26.07.2015, 03:55 
Аватара пользователя


01/06/12
788
Adelaide, Australia
svb, несколько вопросов. Что такое узел? Как вы находите эти формулы?

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение26.07.2015, 07:07 
Аватара пользователя


20/01/10
765
Нижний Новгород
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$

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение26.07.2015, 08:28 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение26.07.2015, 09:00 
Аватара пользователя


01/06/12
788
Adelaide, Australia
svb в сообщении #1040580 писал(а):
Для любого числа ящиков $B$ существует базовая область из стаканов, для которых

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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение26.07.2015, 14:24 
Аватара пользователя


20/01/10
765
Нижний Новгород
:D Стакан? Из него можно пить, например.
Код:
#######################
#   ######  ###########
#           ###########
## #######  ###########
## ####### ############
## #......  ###########
## ########$$ $ $ $ $@#
## ########           #
#  ######## ###########
#            ##########
#  #######   ##########
#######################
Но, вообще-то, я в той ссылке, что давал, приводил пример "стаканов". Еще я высказывал предположения. Потом мне показалось, что рекордная серия 3_L ломает мои гипотезы, но, странным образом и для нее формула похожа. Базовая область из стаканов очень проста и для нее можно получить формулы несложными рассуждениями.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Yahoo [Bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group