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

[svb]

Письмо на форуме от Gil Dogon

Hello all.

The contest is soon going to be finished in about a week's time.

I am glad to say, that although, maybe not that many people had seriously attempted the challenge, the top contestants have achieved some amazing results, that are very interesting (to me at least....).

This forum has been pretty much silent during the competition, but I hope that after it, we will see some posts from the top performers, describing their methods of attacking the problem, and how they achieved their results. I am very interested to know what methods were used by the contestants ...

Anyway , When the competition finishes , I would like those of you that have won a prize (top 5 postions), to send me ([e-mail]) a private message from your private E-mail, so that I'll know where to send the gift certificate :)

In order to Authenticate your message, please send me one of your submitted Sokoban levels, that is on a podium.

Like earlier promised, all the level on the podiums, will be published, a few days after the end of the contest . If you have a level or more on the podium that you are particularly proud of,  You may name it as customary,  just send me an E mail with a list of levels and their chosen names, and I will add it to the levels, one they are published.

[svb]

lepetrandr

Thanks.  BTW, i forget that i have not try to improve some boards for 7_30, and did it right now (with my own approach, not suggested here), and got board with score 509. It's seems that it is a new high score, but it's too late to submit it. Really don't know what to do with this new board :) 

Данный форум ждет ваши новые доски

[lepetrandr]

:)
Видится правильным сначала дождаться презентации текущих максимумов от автора контеста. Потом уже перетирать их новыми :)

[svb]

lepetrandr в сообщении #1032956 писал(а):

:)
Видится правильным сначала дождаться презентации текущих максимумов от автора контеста. Потом уже перетирать их новыми :)

Конкурс уже закончился.

Но... ваше право.

[lepetrandr]

А вот интересно, многие ли пробовали решать уровни с этого соревнования руками? Например, в сети в свободном доступе есть 7_30 требующий 480+ ходов. И сопутствующий вопрос - есть ли какое нибудь распространенное приложение под андроид куда можно закидывать собственные уровни?

[svb]

Можно ввести понятие основного цикла – это путь от любой позиции в ту же позицию. Если рассмотреть проталкивание ящика по основному циклу, то можно выделить точки на этом цикле, из которых грузчику приходится возвращаться назад и проходить путь по основному циклу без ящика. Эти точки принадлежат узлам.

Пусть $C$ - длина цикла, $n$ - число узлов, $L$ - число ячеек, $S$ - score.
Для узлов вида
#####
#...##
#.....
##.###
#.#
$L = C + 4n + T$ , где $T$ - число ячеек не принадлежащих основному циклу. Красными точками отмечен путь ящика. При возвращении грузчику приходится дополнительно проходить по пути отмеченном синими точками.
$S = \left( {C + 2} \right)n + 3C + X$ или $S = \left( {C + 2} \right)n + 2C + X$
Например для уровней 1_128, 1_256, 1_512, 1_1024

         #####   ####
         #   #####  #
         #          #
      ##### ######  #
      #   #  ##### ##
      #      #  ## ##
   ##### ##  #      #
   #   #  ####  #   #
   #      #  ## #####
##### ##  #      #
#   #  ####  #   #
#      #  ## #####
## ##  #      #
## #####  #   #
## ###### #####
## ######@#####
#  ######*####
#            #
#  #######   #
##############

верна формула $S = \left( {C + 2} \right)n + 2C + 6$ , из которой легко находятся $n$ с максимальным $S$ (1090, 4226, 16642, 66050 ). Как располагать узлы значения не имеет.

Для уровней без возврата на место можно использовать стакан и приемник:

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

Но черт прячется в деталях - нужно посмотреть результаты.

[svb]

Рекордная серия 2_L. Далее вычисляем для заданного L число узлов (ищем максимум квадратичной функции) и рисуем соответствующую позицию.

-- Вс июл 05, 2015 21:47:13 --

Если получается нечетное число узлов, то нужно использовать такое начало.

[svb]

Бросилось в глаза не оптимальное расположение сборного стакана в рекорде 4_120. Исправил, но проверить не на чем. Пожалуйста, у кого есть программа, посчитать Score:

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

-- Вт июл 07, 2015 19:12:05 --

Аналогичная просьба посчитать Score для 4_80:

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

[lepetrandr]

Действительно,
3638 -> 3644
1631 -> 1637

[Nataly-Mak]

svb
как я понимаю, улучшаете рекорды?

Кстати, результаты участников из России впечатляют:

Цитата:

1 48.20 Lezhankin Petr Ufa Russia Jun 29 08:54:09 2015
2 47.11 Wes Sampson Springfield USA Jun 29 08:42:56 2015
3 35.71 Artem Ripatti Ufa Russia Jun 30 04:02:52 2015
4 34.48 Alex Chernov Penza Russia Jun 11 18:26:53 2015
5 33.02 Tom Sirgedas Okemos Michigan USA May 29 04:47:23 2015
6 28.28 Bent Seegert Aarhus Denmark Jun 30 19:06:18 2015
7 26.06 Yang Chao Guangzhou China May 1 00:25:30 2015
8 24.46 Sergey Belyaev Nizhny Novgorod Russia Jun 22 01:51:56 2015
9 22.69 Igor Dimitrijevic Paris France Apr 13 00:04:52 2015
10 22.53 Pseudononymous San Francisco USA Apr 8 04:07:33 2015

Поздравляю!!
Особые поздравления коллегам alexBlack и svb.

Из Уфы аж двое лидеров

[svb]

lepetrandr спасибо!

Посмотрел рекорд Wes Sampson для 3_80. В нем за пределами особой области идет цикл с 5 узлами. Если эту область применить для 3_160 то, вроде, число узлов нужно увеличить до 15, что я и сделал:

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

Опять нужно считать Score. Моя древняя программа была сделана для минимизации перемещения ящиков и врет при минимизации числа ходов . Петр, если нетрудно, проверьте этот вариант. Надеюсь на 5328 .

-- Ср июл 08, 2015 01:44:28 --

Ну и для 3_240 аналогично (25 узлов):

(Оффтоп)

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

Надеюсь на 11648.

[svb]

На форуме SLDC-discussion было высказано мнение о квадратичном росте Score в зависимости от L. Скорее всего это так. Можно выдвинуть следующие гипотезы.

1. $Score=O(BN^2)$
2. Для конкретного $B$ при достаточно большом $L$ число узлов основного цикла для максимального Score равно $n=[(L-T)/8]$, где $T$ некоторая константа.
3. Для достаточно большого $L$ и заданного $B$ можно получить аналитические формулы вычисления Score.
4. Для каждого $B$ существует базовая конфигурация (1 или 2), т.ч. при больших $L$ нужные уровни получаются простым подсоединением к этой конфигурации цепочек из простейших узлов из 6 клеток.

В пользу простейших узлов говорит то, что для них минимальна потеря клеток (4) при включении их в основной цикл.

При больших $B$ картина резко усложняется. Доказать справедливость гипотез сложно, легче опровергнуть некоторые из них. Особый интерес вызывает нахождение базовых конфигураций. Пока они имеются только для $B<4$, да и то требуют проверки

[lepetrandr]

5171 -> 5248
11341 -> 11488

Что-то вы ничего не упомянули про уровни с 9 и 10 ящиками - паттерн, который там используется, дает уже экспоненциальный рост от B. Он, в общем-то, уже давно известен, но для 10_40 самый лучший паттерн который можно добыть в интернете дает около 1500. На соревновании мы его улучшили до 2100+ (сколько он будет давать на B > 10 пока не проверял). Так что на больших B доминировать будут уже не комнаты, а вот эти 3xN прямоугольники с "хвостом", вокруг которого сокобан будет прогуливаться O(c^B) раз. Хотя 8_48 с подиума показывает, что возможно можно получать еще более крутую экспоненту другими паттернами при достаточном L (колбаса с хвостом на циклическом больше 1000 не дает там никак, я долго старался :), а рекорд 1156 )

[svb]

lepetrandr в сообщении #1034630 писал(а):

Что-то вы ничего не упомянули про уровни с 9 и 10 ящиками - паттерн, который там используется, дает уже экспоненциальный рост от B.

Просто мне нечего сказать Очень красиво и очень непонятно - сокобан есть сокобан. Я его считаю одним из лучших полигонов.

По поводу экспоненты. Пусть имеется некоторое $B$, не меняя его начинаем увеличивать $L$. Как будет расти Score? С какого-то момента этот рост будет за счет клеток за пределами 3xN прямоугольников. Если каждой клетке поставить в соответствие число проходов через эту клетку сокобана, то клетки 3xN прямоугольников могут быть со сколь угодно большим числом, но при очень большом $L$ основной вклад будут давать другие клетки основного цикла, а вот число проходов через эти клетки пропорционально $B$. Это нужно доказать или опровергнуть - вопрос открыт.

[svb]

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

10_39 Score=2193?

И из той же серии 11_42

(Оффтоп)

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

Score=3575?