2014 dxdy logo

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

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





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


20/01/10
765
Нижний Новгород
Письмо на форуме от 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 (gildogon@mobileye.com) 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.

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


20/01/10
765
Нижний Новгород
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 :)
Данный форум ждет ваши новые доски :D

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение02.07.2015, 16:11 


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

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


20/01/10
765
Нижний Новгород
lepetrandr в сообщении #1032956 писал(а):
:)
Видится правильным сначала дождаться презентации текущих максимумов от автора контеста. Потом уже перетирать их новыми :)
:?:
Конкурс уже закончился.

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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение03.07.2015, 14:55 


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

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


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

Пусть $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 ). Как располагать узлы значения не имеет.

Для уровней без возврата на место можно использовать стакан и приемник:
Код:
      ####
      # @#
      # $#
      #  #
      # $#
   ####  #               
   #  # $########       
   #    $ ###   #       
####  ###       #       
#  ## ###.#### #####   
#      ##.###  #   #   
#  #   ##.###      #   
## ######.###  ## ##   
# ############## ##   
## ##  ######   #  #   
#      ######      #   
#   #  ####### ##  #     
##### ######## #####   
    # ######## ##       
   ## ########  #       
   #            #   
   #   #######  #   
   #####     ####   

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

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


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

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

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

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


20/01/10
765
Нижний Новгород
Бросилось в глаза не оптимальное расположение сборного стакана в рекорде 4_120. Исправил, но проверить не на чем. Пожалуйста, у кого есть программа, посчитать Score:
Код:
#######################
####   ###  ###########
####        ###########
##### ####  ###########
#   #  ### #####.######
#      ### #####.######
## ##  ### #####.######
## ####### #####.######
#  ##   #        ######
#       #   ####  #@  #
#  ### ##########  $$ #
#####  #   ###  #$#   #
#####      ###    $ ###
#####  ## ####  #######
########  ##### #######
########         ######
########  ####   ######
#######################


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

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

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение07.07.2015, 21:46 


21/06/15
11
Действительно,
3638 -> 3644
1631 -> 1637

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


22/03/08

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

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

Цитата:
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.

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

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


20/01/10
765
Нижний Новгород
lepetrandr спасибо!

Посмотрел рекорд Wes Sampson для 3_80. В нем за пределами особой области идет цикл с 5 узлами. Если эту область применить для 3_160 то, вроде, число узлов нужно увеличить до 15, что я и сделал:
Код:
######################
####    #  ###########
####  #  $ ###########
####  ### $ ##########
#####.###    #########
#   #. ###$  #########
#      ###@###########
## ## .### ##  #######
## ######      #######
#  #   ##   #  #######
#      ###### ##  ####
#  ## ######      ####
####  #   ##   #  ####
####      ###### ##  #
####  ## ######      #
#######  #   ##   #  #
#######      ###### ##
#######  ## ####### ##
########### ####### ##
########### ####### ##
########### ####### ##
########### ####### ##
########### ####### ##
########### ####### ##
########### ####### ##
##########  ####### ##
##########           #
##########  ######   #
######################
Опять нужно считать Score. Моя древняя программа была сделана для минимизации перемещения ящиков и врет при минимизации числа ходов :-( . Петр, если нетрудно, проверьте этот вариант. Надеюсь на 5328 :D .

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

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

(Оффтоп)

Код:
###############################
####    #  ####################
####  #  $ ####################
####  ### $ ###################
#####.###    ##################
#   #. ###$  ##################
#      ###@####################
## ## .### ##  ################
## ######      ################
#  #   ##   #  ################
#      ###### ##  #############
#  ## ######      #############
####  #   ##   #  #############
####      ###### ##  ##########
####  ## ######      ##########
#######  #   ##   #  ##########
#######      ###### ##  #######
#######  ## ######      #######
##########  #   ##   #  #######
##########      ###### ##  ####
##########  ## ######      ####
#############  #   ##   #  ####
#############      ###### ##  #
#############  ## ######      #
################# ######   #  #
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################# ########## ##
################  ########## ##
################              #
################  #########   #
###############################
Надеюсь на 11648.

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


20/01/10
765
Нижний Новгород
На форуме 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$, да и то требуют проверки :D

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение08.07.2015, 12:26 


21/06/15
11
5171 -> 5248
11341 -> 11488

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

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


20/01/10
765
Нижний Новгород
lepetrandr в сообщении #1034630 писал(а):
Что-то вы ничего не упомянули про уровни с 9 и 10 ящиками - паттерн, который там используется, дает уже экспоненциальный рост от B.

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

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

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


20/01/10
765
Нижний Новгород
Код:
#######
##  ###
## . ##
##$. ##
## .$##
##$. ##
## .$##
##$. ##
## .$##
##  * #
#@$.  #
# $ * #
##  ###
#######
10_39 Score=2193?

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

(Оффтоп)

Код:
#######
###  ##
## . ##
## .$##
##$. ##
## .$##
##$. ##
## .$##
##$. ##
## .$##
##  * #
#@$.  #
# $ * #
##  ###
#######
Score=3575?

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

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



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

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


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

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