2014 dxdy logo

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

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





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


20/01/10
764
Нижний Новгород
Сегодня получил письмо от Gil Dogon

(Оффтоп)

Код:
Hello.

My name is Gil Dogon, and I am sending you this mail, because I hope you are designing Sokoban levels, or interested in their design (Some other designers I know of are BCC'd).

I would like to announce, the opening of a new contest site. This contest is called "Sokoban Levels Design Contest", and is intended to further the art and science of small and medium Sokoban level designs. It is based on an automated solver, and levels are measured simply by the move length of the optimal solution (so admittedly it is more science than art ...).  If you are interested also in  Sokoban programming,  or just have too much spare time, and yearning to attack a new challenge please visit my site and join the contest at:
http://sokoban-gild.com
Мне кажется, что это может заинтересовать форумчан. Подробности конкурса здесь. Необходимо разработать программу для генерации уровней старинной игры "Сокобан".

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


24/11/10
48
Gil Dogon дает скачать код на языке С для своего сольвера. Но увы этот код для UNIX. Может кто-нибудь из форумчан-програмистов возьмется переделать этот код для Виндоус? Сама задачка интересная :-)

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


20/10/12
299
Поставьте Cygwin и компилируйте свою программу под Виндами.
По моему, без Cygwin-а и Far-a там вообще работать невозможно.

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение03.04.2015, 08:00 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Vitaly12 в сообщении #999548 писал(а):
Gil Dogon дает скачать код на языке С для своего сольвера. Но увы этот код для UNIX

А также он указывает как нужно изменить код чтобы он компилировался для Windows.
Gil Dogon писал(а):
If you want to build the program on Windows . . . just undef (comment) the HAS_CLZ

То есть нужно всего лишь закомментировать вторую строку программы.
Используется синтаксис C
/*#define HAS_CLZ*/

Не проверял сработает ли это.

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


24/11/10
48
Цитата:
То есть нужно всего лишь закомментировать вторую строку программы.
Используется синтаксис C
/*#define HAS_CLZ*/

Не проверял сработает ли это.

Ох, было бы все так просто... :-(

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение03.04.2015, 14:12 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Не сработало?

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


24/11/10
48
whitefox в сообщении #999664 писал(а):
Не сработало?


Выше писали про Cygwin. Я не слышал про это раньше и погуглил в Википедии:
"Cygwin is a Unix-like environment and command-line interface for Microsoft Windows. Cygwin provides native integration of Windows-based applications, data, ..."

Может с этим и сработает, но начинать устанавливать и изучать новый environment для одной единственной компиляции (а что с этим сработает тоже не факт) мне как-то не очень...

 Профиль  
                  
 
 Re: Солверы для игры Сокобан. Конкурс.
Сообщение04.04.2015, 11:43 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Вот решил посмотреть какие изменения нужно внести в исходный код, чтобы он скомпилировался под Windows.

Помимо макроса, указанного Gil Dogon, нужно закомментировать ещё парочку —
ASCII_ANIMATE и MEASURE_TIME.

Также нужно добавить директиву #include <ctype.h> и в двух местах заменить имя функции snprintf на sprintf_s.

А так как я пользуюсь компилятором Visual C++, то мне пришлось:
  1. изменить расширение исходного файла с .c на .cpp;
  2. указать тип возвращаемого значения int для функций my_bitind и main;
  3. указать тип возвращаемого значения void для функций level_init и level_reset;
  4. изменить тип возвращаемого значения с int на void для функции generate_deadlocks;
  5. изменить тип возвращаемого значения с void* на void для функции hash_clear;
  6. добавить явное приведение указателя типа void* к типу char*
    Используется синтаксис C++
    char *sstring=(char*)MALLOC(nmoves+1);
    /* . . . */
    a->ptr=a->area=(char*)MALLOC(size);
     
  7. добавить прототип функции
    Используется синтаксис C++
    int instate(uint32_t *s,int loc);


После этого программа успешно скомпилировалась, при этом компилятор выдал кучу предупреждений:
Код:
scorer.cpp(296): warning C4018: >: несоответствие типов со знаком и без знака
scorer.cpp(416): warning C4244: инициализация: преобразование "uint64_t" в "uint32_t", возможна потеря данных
scorer.cpp(417): warning C4244: return: преобразование "uint64_t" в "uint32_t", возможна потеря данных
scorer.cpp(481): warning C4996: 'strtok': This function or variable may be unsafe. Consider using strtok_s instead.
scorer.cpp(484): warning C4996: 'strncpy': This function or variable may be unsafe. Consider using strncpy_s instead.
scorer.cpp(487): warning C4996: 'strncpy': This function or variable may be unsafe. Consider using strncpy_s instead.
scorer.cpp(490): warning C4996: 'strtok': This function or variable may be unsafe. Consider using strtok_s instead.
scorer.cpp(493): warning C4996: 'strtok': This function or variable may be unsafe. Consider using strtok_s instead.
scorer.cpp(750): warning C4101: i: неиспользованная локальная переменная
scorer.cpp(819): warning C4101: i: неиспользованная локальная переменная
scorer.cpp(876): warning C4101: j: неиспользованная локальная переменная
scorer.cpp(955): warning C4101: j: неиспользованная локальная переменная
scorer.cpp(999): warning C4101: loc: неиспользованная локальная переменная
scorer.cpp(1098): warning C4101: i: неиспользованная локальная переменная
scorer.cpp(1264): warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead.


Кого это раздражает, сможет легко сделать необходимые изменения, но и без них программа должна работать. Впрочем, её работоспособность не проверял.

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


24/11/10
48
Цитата:
Кого это раздражает, сможет легко сделать необходимые изменения, но и без них программа должна работать. Впрочем, её работоспособность не проверял.


Сделал необходимые изменения (suppress warnings :-) ) и программа заработала! Снимаю перед вами шляпу :wink:

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


20/01/10
764
Нижний Новгород
Дам давно забытые ссылки, может пригодятся для въезжания в тему.
Генератор и солвер
Подробнее об svbgen

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


01/06/12
755
Adelaide, Australia
Эх если бы у меня был нормальный солвер для Java. JSoko слишком медленный, а другие ещё хуже. У Gil солвер отличный по скорости, но я плохо понимаю ANSI-C и поэтому не могу как следует к нему подключиться. На даный момент сделал простой генератор в Java, генерирую уровни и каждый сохраняю в отдельный файл, а потом проверяю их все солвером Gil, и другой Java программой нахожу лучшие результаты. Слишком это всё мучительно...

Кстати очень нравится задачка с одной коробкой. Нашёл неплохую "комнату" которую можно повторять бесконечно. При этом количество ходов растёт экспоненциально. Если в уровне L пустых клеток и мы добавляем такую комнату с n клетками то количество ходов вырастает примерно на (L+n). Очень красиво! Тем не менее никак не могу догнать результаты лидеров. Мой лучший результат для L=128 составляет 1172 ходов. Если не секрет, насколько я далеко от лучшего результата?

По моим расчётам для L=1024 можно найти более 100,000 ходов, но я не пробовал.

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


24/11/10
48
Цитата:
У Gil солвер отличный по скорости, но я плохо понимаю ANSI-C и поэтому не могу как следует к нему подключиться.


Лучше всего переделать Gil солвер в .DLL file и вызывать его из вашей программы. Это, конечно, если вы пишете на С++ или С# :-) Про другие языки не знаю...

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


24/11/10
48
Цитата:
При этом количество ходов растёт экспоненциально. Если в уровне L пустых клеток и мы добавляем такую комнату с n клетками то количество ходов вырастает примерно на (L+n).


Не понял. Разве это экспоненциально? :?

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


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

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


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

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

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



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

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


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

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