Из истории проекта Sudoku ... (Интервью с руководителем проекта)

Специально для BOINC.RU на несколько вопросов ответил I-Chen Wu, руководитель проекта Sudoku@vtaiwan  (апрель 2014 г.

Также приводятся комментарии и пояснения, которые дал Олег Заикин (Nauchnik).

 

 

1.Почему вы решили сделать проект добровольных распределенных вычислений для решения задачи судоку? 

 В 2009 году один из студентов нашей команды, по имени Ю-Лонг Хуанг (Yu-Long Huang), сделал первую (в нашей команде) попытку по исследованию задачи о минимальном числе подсказок в игре Судоку, и написал магистерскую диссертацию по этому вопросу [1]. Для генерации большего числа вариантов головоломки, он использовал очень простой метод: удалял некоторые подсказки наугад, а затем добавлял новые подсказки. К сожалению, этот метод не смог генерировать корректные головоломки с более чем 17 подсказками (или 16 подсказками в случае, если они существуют), по сравнению с содержащимися в коллекции Ройла (Royle)[2]. 

Примечание: на тот момент известны были судоку с 17 подсказками и они были в коллекции [2]. Сгенерированы новым методом были только такие же судоку, какие и были известны до этого. Тогда еще не знали, что судоку с 16 подсказками не существует, поэтому Ю-Лонг пытался найти и их тоже.

После работы Хуанга, Хун-Сюань Лин (Hung-Hsuan Lin, Stanley), аспирант нашей команды в то время (получил ученую степень Ph.D. в 2013 году), продолжал исследовать этот вопрос. Во-первых, мы классифицировали все головоломки по значениям (I, J), где I это минимальное количество подсказок среди всех сеток 3x9 (или 9x3) (три блока Судоку 3x3 в строке (или в столбце)), и J указывает минимальное количество подсказок среди всех сеток 9x3 (или 3x9).

Примечание: имеется в виду, что разные судоку с одинаковыми значениями (I,J) попадали в один класс, т.е. были в каком-то смысле «подобны».

Затем мы использовали некоторые теоретические методы [3], чтобы доказать, что не существует никаких головоломок из следующих классов (2,2), (2,3), (2,4), (2,5), (3,3). Также Лин использовал программы, чтобы доказать, что не существует головоломок из классов (3,4) и (3,5), и это было опубликовано в [3].

 Однако мы скоро поняли, что крайне сложно (почти невозможно) проверить головоломки из классов (4,4), (4,5), (5,5). После анализа метода, предложенного Мак Гуайром (McGuire), в программе Checker ("Шашки"), мы обнаружили некоторые возможности для его улучшения, поэтому мы решили приложить усилия к повышению его результативности. Кроме того, так как 5,4 миллиардов (более точно 5 472 730 538) достаточно полных сеток могут быть проверены с помощью этого метода независимо друг от друга, то он хорошо подходит для параллельного вычислительного эксперимента, и особенно для добровольного вычислительного проекта на базе BOINC. Так как у нас не было постоянной поддержки вычислительными мощностями, мы решили использовать проект BOINC чтобы помочь нашему проекту Судоку.

 

 2. С какими трудностями Вы столкнулись при создании проекта? 

 В этом проекте, мы столкнулись со следующими проблемами:

 a.    Серверы должны быть в состоянии обрабатывать нестабильные запросы от клиентов. По нашему опыту, затраты на проверки для некоторых из 5,4 млрд. сеток оказались гораздо меньше, чем для других. Таким образом, когда более простые варианты были проверены, запросы от клиентов существенно возросли, и, следовательно, сделали загрузку сервера выше и сервер иногда зависал.

b.    Серверы должны создавать резервную копию всех данных тщательно и постоянно. При запуске нашего проекта в октябре 2010 года, мы столкнулись  с крахом системы в феврале 2011 года, и потеряли часть пользовательских профилей, которые были восстановлены с большим трудом.

c.     Мы должны были поддерживать наши приложения Судоку для различных версий и для разных платформ, таких как Windows, Linux, Mac и т.д. Так как имеющаяся у нас вычислительная среда не включает в себя все различные платформы и членам нашей команды не хватает опыта работы на  некоторых платформах, для нас оказалось сложным быстро отладить эти проблемы и отвечать на некоторые сообщения об ошибках в кратчайшие сроки. Так как большинство членов нашей команды были студентами, нам было трудно оказывать профессиональную поддержку волонтеров.

 

 3. Знали ли Вы, что во время Вашей работы над проектом, проблема судоку была решена в Ирландии на кластере? Вы можете сказать, что-то об этом?

 Да, мы знали, что Мак Гуайр (McQuire) утверждал [4], что решил проблему с "отсутствием головоломок с 16-ю подсказками" в январе 2012 года. Алгоритм Мак Гуайра использовал метод неизбежных наборов высокой степени (higher-degree unavoidable sets), в то время как в нашем подходе используется улучшенный алгоритм DMUS на базе усеченных деревьев (DMUS to prune subtrees). По оценке Мак Гуайра в (McGuire и др.., 2012), скорость вычисления их нового алгоритма быстрее нашего в 2 и более раз.

Конечно, было жалко, что мы не стали первой командой, решившей эту задачу. Однако мы все же решили продолжить наш BOINC-проект [5] для решения проблемы Судоку, так как все еще было важно подтвердить полученный результат. Так как сложность решения проблемы Судоку чрезвычайно высока, повторное решение проблемы проектом означало бы, что проблема действительно решена, подтверждая, что нет никаких ошибок в программе в проекте. Альтернативное решение в независимом проекте с использованием другого метода твердо подтвердило бы результат. Точно так же, как электричество поддерживается двумя электростанциями для безотказной работы электросети, результат, подтвержденный двумя независимыми проектами, значительно уменьшает вероятность присутствия ошибок. 

 

 4. Проекту помогали тысячи пользователей. Этих вычислительных мощностей было достаточно? Или вы хотели бы большего количества участников?

Конечно, вычислительной мощности не хватало. Если бы у нас было в 2 или 3 раза больше добровольной вычислительной мощности, мы могли бы решить эту проблему гораздо раньше. Однако, поскольку мы не были знакомы с BOINC, мы не знали, как рекламировать наш проект. Если будет еще несколько проектов BOINC, мы будем уделять больше внимания этому вопросу.

 

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

 Согласен со всем сказанным, как раз об этом я говорил в предыдущем ответе.

 

6. Есть ли у Вас планы по организации нового добровольного проекта распределенных вычислений? 

После окончания этого проекта, мы планируем организовать другие проекты BOINC или добровольные вычислительные проекты, например, Go@vtaiwan, который направлен на решение положений игры Го (Go) размерностью 7x7 или 9x9. Игра Го является популярной и очень сложной восточной игрой. В игре Го комбинаторное дерево для размерности 7х7 имеет около 1047 ветвей, и находится между результатами программ Checker (“шашки») (1031, решена в 2007 году) и Othello (1058, еще не решена). Таким образом, мы считаем, что игра Го 7x7 станет следующим кандидатом для исследования. На самом деле, игра Го чрезвычайно трудна и сложна для решения, и не только своей сложностью дерева игры, но и из-за его особенностей, которые делают распараллеливание вычислительного процесса достаточно сложным. Например, «правило ko» делает задачу хорошего распараллеливания в BOINC значительно более трудной.

Примечание: Тут имеется в виду, что все варианты игры – это дерево решений размерности примерно1047. Если можно их все перебрать (как для шашек), то можно найти оптимальную последовательность ходов для любой позиции.

 

Материалы, упомянутые в интервью:

[1] Yu-Long Huang, "The study of Minimum Sudoku", Master Thesis (in Chinese), Department of Computer Science, National Chiao Tung University, Feb 2009.

[2] Royle, G. (2009). Minimum sudoku. http://people.csse.uwa.edu.au/gordon/sudokumin.php.

[3] Hung-Hsuan Lin, I-Chen Wu, Ting-Han Wei, "On Specific 17-clue Sudoku Puzzles", ICGA Journal (SCI), Vol. 36(3), pp. 131-138, September 2013.

[4] McGuire, G., Tugemann, B., and Civario, G.. There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, http://www.math.ie/McGuire_V1.pdf, January 2012.

[5] Lin, H.-H. and Wu., I.-C. (2011). An Efficient Approach to Solving the Minimum Sudoku Problem, ICGA Journal, Vol. 34, No. 4, pp. 191-208.

 

 

 
 

Вернуться:я:  на сайт BOINC.RU