Распечатать запись Распечатать запись

Candy Crush Saga и P=NP проблема

Предупреждение. Эта статья ни в коем случае не является рекламой игры Candy Crush! Прежде чем начать играть в нее, посмотрите ролик о ней здесь: Candy Crush Saga is evil

4 года назад группа математиков из Королевского колледжа в Лондоне решила атаковать одну из наиболее интересных проблем современной математики и за решение которой можно заработать миллион долларов (и, вероятно, медаль Филдса — по крайней мере, тем членам группы, которым нет еще 40 лет).

Всего лишь 2 года назад была запущена бета-версия приложения, которое могло бы помочь им решить поставленную задачу. И, как подтвердил сегодня Международный математический союз, кажется, их работа начинает приносить свои плоды.

12 ноября исполнился год, как на рынок вышла одна из самых захватывающих игр последних десятилетий. Это игра, в которую можно играть на всех платформах, игра, во многом напоминающая знаменитый тетрис. Я имею в виду Candy Crush Saga.

Что общего имеет эта игра с Королевским колледжем Лондона? Очень просто. Как называется компания, которая выпустила эту игру? Да, в самом деле: KING (король). И это неслучайно.

Это неслучайно, так как Candy Crush Saga является, по сути, приложением, о котором говорилось в начале статьи. То есть это то самое приложение, созданное группой KING из Королевского колледжа Лондона, чтобы попытаться опровергнуть равенство P=NP.

Первоначальная идея была, как это было и в случае тетриса в 90-х, — создать игру, которая была бы из класса NP, а затем доказать, что невозможно создать для нее стратегию, которая обеспечивала бы выигрыш за алгоритмически полиномиальное время.

Все было просто: бета-версию игры распространили среди студентов Королевского колледжа, чтобы установить, действительно ли игра достаточно трудна. Но процесс вышел из-под контроля, и вскоре игра приобрела известность, распространившуюся далеко за границы кампуса.

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

Сегодня, хотя и в неожиданной форме, проект начинает приносить свои плоды. Благодаря сложному программному обеспечению удалось создать трехкомпонентную систему, которая для любого заданного уровня Candy Crush и фиксированного \varepsilon>0 дает возможность создать новый уровень сложности на \varepsilon/3 выше.

Эта программа не применима к конкретным уровням, но на самом деле процедура выполняется параллельно (и благодаря процессорам Intel Quantum нового поколения) на всех уровнях одного “мира’’ с целью получения нового диапазона уровней.

Путь решения данной задачи несколько необычен, но не нов. На самом деле, он основан на идее коллективного сотрудничества через терминал, придуманный для проекта SETI — SETI at HOME.

Точнее, каждый раз, когда каждый из нас играет на каком-то уровне Candy Crush, в действительности он отправляет информацию о стратегии (сознательной или неосознанной), которую он применяет в игре. В связи с этим первым результатом является то, что кривая сложности игры не является непрерывной, присутствуют конечные скачки, произвольно локализованные во времени.

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

Согласно заявлению, появившемся в письме года Международного математического союза, в нескольких журналах лежат на рецензии научные статьи (всего их 5) об игре, эти журналы Acta Mathematica Sinica, Journal of the Pan-American Mathematical Society и Comptes Rende-Vouz de la Academia de Ciencias de París.

Успех игры доказывает недавний выпуск ее обновления, в котором игроки оказываются в ином мире Мечты.

Проект “Сова’’ (как его называют специалисты), на самом деле является новой попыткой доказать гипотезу Римана. Если вы посмотрите, на новых уровнях важно поддерживать баланс между двумя цветами, так чтобы ни один не использовался больше, чем другой. Это связано с известным свойством универсальности дзета-функции Римана и мешает ее нетривиальным нулям располагаться произвольным образом.

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

Итак, уважаемые читатели, если когда-либо ваша жена или ваш лучший друг скажет вам, что вы не уделяете им достаточного внимания, а играете весь день в Candy Crush, с сегодняшнего дня вы можете с гордостью сказать, что

игра Candy Crush оказывает помощь в продвижении математических исследований.

Источник: http://eliatron.blogspot.ru/2013/12/candy-PNP.html

Оставьте свой отзыв

Добавить изображение