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
766
Нижний Новгород
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
766
Нижний Новгород
$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
1016
Adelaide, Australia
svb, несколько вопросов. Что такое узел? Как вы находите эти формулы?

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


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

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


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

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

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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