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

[dimkadimon]

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

Wes Sampson постепенно движется к 50. Циклические уровни ставят меня в тупик. Пробный заброс 6-35 при Score=90 дал всего 0.15. Неужели нужно получить Score=600?

Для меня циклические проще обычных, потому что там меньше вариантов и можно больше перебрать. Количество вариантов для обычного уровня: choose(L,B) позиций коробок, choose(L,B) позиций окончаний, (L-B) позиций мужика. Количество вариантов для циклического уровня: choose(L,B) позиций коробок и окончаний, (L-B) позиций мужика. Значит экономия choose(L,B).

Для 6-35 я на втором месте, но результат всего 378. Циклические результаты у меня обычно на 5%-40% отстают от обычных.

-- 01.05.2015, 10:08 --

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

Осталось 2 месяца до конца конкурса. Похоже, что основная борьба еще впереди.
Текущая ситуация несколько странная для проводимых конкурсов. И участников мало, и активность слабая. Даже dimkadimon перестал посылать новые варианты.

Я думаю многие не ввели все результаты (кроме Wes). Я задачу пока оставил, потому что делаю TopCoder Open Marathon Round 1. Не уверен что найду мотивацию к ней вернуться пока не найду хороший солвер в моем языке (Java) или научусь "взламывать" солвер Gil.

[svb]

Утром 2 мая Wes улучшил свой же рекорд - его счет не изменился, но у других счет уменьшился. А вот в каком уровне, не очень понятно.

[svb]

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

Я думаю многие не ввели все результаты (кроме Wes). Я задачу пока оставил, потому что делаю TopCoder Open Marathon Round 1. Не уверен что найду мотивацию к ней вернуться пока не найду хороший солвер в моем языке (Java) или научусь "взламывать" солвер Gil.

А вы уверены, что дело в солвере? Wes сегодня снова улучшил рекорд. Сначала я хотел переписать свою программу - старая была ориентирована на получение минимальных перемещений ящиков и плохо работает для получения минимального числа ходов. Так и не сделал этого, пользуюсь старой, плохо написанной, только для оценки. Циклы из узлов являются, как мне кажется, главными для размышлений при больших L. Пока пользовался простейшим узлом, но существуют и более сложные конфигурации и для их анализа солвер мало что дает.

[svb]

Остался 1 месяц. Активность невысокая, но рекорды улучшаются почти каждый день.

1   49.21   Wes Sampson   Springfield   USA   May 30 11:57:56 2015
2   35.59   Lezhankin Petr   Ufa   Russia   May 30 19:24:07 2015
3   35.47   Alex Chernov   Penza   Russia   May 31 10:40:50 2015
4   33.85   Tom Sirgedas   Okemos Michigan   USA   May 29 04:47:23 2015
5   26.80   Yang Chao   Guangzhou   China   May 1 00:25:30 2015

[svb]

Произошла смена лидера:

1   47.29   Lezhankin Petr   Ufa   Russia   Jun 18 14:35:02 2015
2   47.21   Wes Sampson   Springfield   USA   May 30 11:57:56 2015
3   34.64   Alex Chernov   Penza   Russia   Jun 11 18:26:53 2015
4   33.09   Tom Sirgedas   Okemos Michigan   USA   May 29 04:47:23 2015
5   26.17   Yang Chao   Guangzhou   China   May 1 00:25:30 2015 

[Nataly-Mak]

Ого! В тройке лидеров двое россиян. Молодцы!
Алексея Чернова (alexBlack) знаю давно.
Lezhankin Petr форумчанин?

[lepetrandr]

Всем привет! Теперь тоже форумчанин :) до этого контеста никогда в сокобан не играл, друг ссылочку скинул )

[whitefox]

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

Всем привет! Теперь тоже форумчанин :) до этого контеста никогда в сокобан не играл, друг ссылочку скинул )

И сразу в лидеры?
Круто

[lepetrandr]

whitefox в сообщении #1029367 писал(а):

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

Всем привет! Теперь тоже форумчанин :) до этого контеста никогда в сокобан не играл, друг ссылочку скинул )

И сразу в лидеры?
Круто

Честно говоря, планировал остановиться на второй строчке. Но потом... стал один за другим обходить максимумы лидера, набрал множество таких и отправил разом ( чтобы не было понятно где и на сколько превышены бывшие максимумы ), ну и вышло вполне недурно.

[Vitaly12]

Цитата:

ну и вышло вполне недурно.

Из чистого любопытства: Это у вас такой крутой алгоритм или все же очень мощный компьютер?

[lepetrandr]

Если кратко, то и то, и другое. Над алгоритмом тоже пришлось попотеть, чтобы ускорить в сотни раз и значительно сокращать пространство перебора. А используется в среднем всего 10-15 потоков. Для подобных соревнований число весьма скромное, на мой взгляд. Многие максимумы находились однопоточным кодом (разные подходы).

[whitefox]

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

А используется в среднем всего 10-15 потоков.

У прежнего лидера компьютер мощнее.

[Nataly-Mak]

А меня svb приглашал вручную решать задачу, как любителя ручных решений.
Ну, меня идеальные квадраты полонили безраздельно, никаких отвлечений не позволяют

Эх, мне бы чуть помощнее компьютер

[lepetrandr]

whitefox в сообщении #1029531 писал(а):

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

А используется в среднем всего 10-15 потоков.

У прежнего лидера компьютер мощнее.

Интересно, а сколько у него ядер/оперативки?

[svb]

Nataly-Mak в сообщении #1029532 писал(а):

А меня svb приглашал вручную решать задачу, как любителя ручных решений.

Подтверждаю. Я так и не добрался до написания программы - отложил на потом.