Квантовий Морріс

          Коло танцюючих звивався, як жива істота. Але серед них було вільне місце і воно рухалося. Вона знала, це місце для неї. Міс Тенета заборонила їй. Але коли вона це говорила? І потім, куди їй зрозуміти. Що вона взагалі розуміє? Коли вона танцювала в останній раз? Танець був у крові Тіффані, він манив її. Шести танцюючих недостатньо! 
          … Танцюристи не зводили з неї очей, а вона підстрибувала й кружляла між ними, кожен раз опиняючись там, де нікого не було.  

           сер Террі Пратчетт "Зимових справ майстер"
 

Незважаючи на всю свою неказистость, "Крестики-нолики" є наріжним каменем світу настільних ігор. Принцип "N в ряд" настільки простий і природний, що був винайдений незалежно відразу кількома стародавніми народами. В Китаї і Японії він ліг в основу таких ігор як "Рендзю" і "Хасами Сеги", в стародавній Європі — породив "Мельницу" — прародительку "Алькуэрка" і, зрештою, усього розмаїття сучасних шашок.

У своєму початковому вигляді, «Хрестики-нулики» не здаються грою скільки-небудь цікавою. У самому справі, безпрограшна стратегія, для кожного з гравців, в цій грі, абсолютно очевидна, а перемогти, при правильній грі, абсолютно неможливо. Подібна гра може привернути до себе молодших школярів, але ніяк не серйозних гравців. Втім, є кілька способів все виправити…

Причому тут кіт?

Коли мова заходить про поліпшення «Хрестиків-нуликів», перше, що приходить в голову — збільшення розмірів (або розмірності) ігрового простору. Дійсно, гра на дошці 3x3x3 вже не настільки тривіальна, а серед безлічі різновидів гри на великій дошці є дисципліни вважаються професійними (правда, в цьому випадку, мова йде про вибудовування п'яти фігур в ряд). Існують і менш очевидні можливості поліпшення гри. Так, задіявши в якості одного з ігрових факторів гравітацію, ми отримаємо дуже цікаву гру "Чотири в ряд", а проста зміна умови перемоги (гравець, вимушено побудував ряд з трьох фігур — програє) дає нам «Losing Tic-Tac-Toe», перемогти в якій зовсім не просто.

У 2006 році, Allan Goff придумав ще один спосіб радикального поліпшення гри. Зробив він це не просто так, а з метою ілюстрації таких складних понять квантової механіки як «суперпозиція», «заплутаність» і «згортка». У запропонованому ним варіанті гри, кожен гравець, замість того щоб поставити свій хрестик або нулик, робить два полухода в різні позиції ігрового поля. Додана на дошку фігура рівноймовірно присутня в двох позиціях одночасно. В індексах зберігається інформація про черговість ходів гравців, в подальшому використовується при вирішенні виникаючих колізій.


До тих пір, поки присутні фігури на дошці лише у формі полуходов, ми не можемо сказати точно, який з позицій кожна з них знаходиться. Можливо, це не найбільш вдала метафора квантової механіки, оскільки в рамках цієї моделі кожна фігура може бути «розмазана» не більш ніж по двох можливих розташувань (також можливі деякі складнощі з визначенням переможця, про які я скажу нижче). У 2010 році J. N. Leaw і S. A. Cheong запропонували більш складний варіант гри, в якому кожен хід являє собою вектор в девятимерном гільбертовому просторі. Короткий опис можна подивитися тут.

Зрозуміло, ідея «розмазування» ходів не новаТак наприклад, в Refusal Chess (Fred Galvin, 1958), кожен гравець пропонував два можливих ходу, а його опонент вибирав один хід із запропонованих. Виключення робилося лише для позицій з єдиним можливим дозволеним ходом. Подібним чином ігровий процес побудований в "Ambiguous Chess" (Fabrice Liardet, 2005). У цього різновиду гри, гравець позначає поле на яке збирається сходити (воно може бути включена ворожої фігурою), а його супротивник вибирає фігуру, здатну виконати цей хід:


У будь-якому випадку, концепція здалася мені цікавою. Настільні ігри, в основі своїй, прості. Фігури стають на дошку, переміщуються, перетворюються, забирають інші фігури — все це дуже легко реалізувати. Але зустрічаються «родзинки», складність яких буквально «зашкалює». Шахах, це концепції шаха і мата, Шашках — «правило більшості», Го — взаємний вплив фігур. Концепції «суперпозиції» і пов'язаної з нею «заплутаності» — одна з таких «родзинок».

Распутываем заплутаності

Якби справа обмежувалася одними лише полуходами, «Квантових хрестики-ноликах» не було б нічого цікавого. Для перемоги необхідно забезпечити стовідсоткову присутність фігур на заданих позиціях! Яким чином полуходы перетворюються в повноцінні фігури? Настав час в цьому розібратися. Якщо заповнювати дошку полуходами досить довго, рано чи пізно виникне ситуація, подібна до наступного:


Виникла колізія, свого роду парадокс — протиріччя у вихідних даних. В кінцевому підсумку, розташування кожної фігури має бути точно визначено. Всі полуходы повинні бути «згорнуті», але існують дві принципово різні можливості такої «згортки». В одному з цих випадків, гра закінчується.


Гравець, який замкнув цикл взаємозалежностей винен у виникненні «парадоксу». З цієї причини, вибір варіанту згортки надається його опонентові. В нашому випадку, був замкнутий цикл «хрестиками». Це означає, що «ноликам» вдасться уникнути поразки. Вони просто оберуть «з двох можливих світів» той, в якому «хрестики» ще не перемогли. Але можливі ситуації, в яких від вибору варіанту згортки вже нічого не залежить:


Що тут не вибирай, кінцевий підсумок для «нуликів» однаковий — вони програли. Можлива і вироджене ситуація. Будь-який з гравців може зробити два полухода в одну і ту ж область дошки. Це найкоротша з можливих колізій. Оскільки вона передбачає вибір з двох абсолютно однакових варіантів, така послідовність полуходов фактично дорівнює повному ходу в це поле:


Зверніть увагу на те, як хід «хрестиків» витісняється з обраного поля. Кожна комірка дошки може містити результат не більш ніж одного повного ходу. Таке «витіснення» може поширюватись далі, по ланцюжку (насправді, по дереву). На мій погляд, подібні ходи знаходяться десь на межі фолу. Вони дуже сильні. Такий «детермінований» хід рівносильний звичайному ходу в «Хрестики-ноликах» і, крім того, дозволяє «витіснити» супротивника з обраної позиції. У більшій частині варіантів своєї реалізації «Квантових хрестиків-нуликів» (6 з 10) я заборонив виконання «детермінованих» ходів.



Як це все працює?Цей код — втілення нічних кошмарів. Я тричі переписував його! Тепер він працює. Я не дуже добре розумію, оскільки, на даний момент, він, в основному, складається з латочок. Сам процес налагодження Axiom-додатків непростий. Якщо в коді є помилка — він падає. В більшості випадків. Але якщо все працює — це зовсім не означає, що помилок немає. Просто самі помилки стають вигадливіше. І так, без рекурсії справа не обійшлося.

: in-collision? ( -- ? )
FALSE 0 BEGIN
DUP curr-size @ < IF
DUP pos[] @ here = IF
2DROP TRUE 0
TRUE
ELSE
1+ FALSE
ENDIF
ELSE
TRUE
ENDIF
UNTIL DROP
;

: pair-found? ( -- ? )
FALSE 0 BEGIN
DUP empty-at? NOT OVER piece-type-piece at-type = AND IF
DUP here <> IF
DUP 0 pos[] @ = IF
collision-size @ 0= IF
curr-size @
collision-size !
ENDIF
DROP ALL
ELSE
DUP to
here curr-size @ pos[] !
curr-size ++
2DROP TRUE ALL
ENDIF
ENDIF
ENDIF
1+ DUP ALL >=
UNTIL DROP
;

: not-prev? ( -- ? )
curr-size @ 0> IF
curr-size @ 1 - pos[] @ here <>
ELSE
TRUE
ENDIF
;

: try-pos ( -- )
DROP down
BEGIN here
my-empty? NOT not-prev? AND IF
here curr-size @ pos[] !
curr-size ++
pair-found? curr-size @ TOTAL < AND IF
RECURSE
curr-size --
ENDIF
curr-size --
ENDIF
to NOT up my-empty? OR collision-size @ 0> OR
UNTIL
;

: check-collision ( -- )
find-mark
try-pos
collision-size @ 
DUP 2 > verify
curr-size !
from to
in-collision? verify
;

Як би там ні було, це серце всього проекту. Найскладнішим виявилося саме визначення факту наявності колізії, а також пошук всіх фігур входять до неї. Процес «розплутування» можна починати тільки з цих фігур. І поки є колізія, а вона може бути тільки одна, не можна дозволяти ніякі інші ходи крім «розплутування». В іншому випадку, є шанс остаточно все заплутати. Це не складно. Допомагають пріоритети. Якщо є хоча б один пріоритетний хід, ніякі інші ходи виконуватися не можуть. Це не самий універсальний механізм, але він працює:

{move-priorities
{move-priority} high-priority
{move-priority} normal-priority
{move-priority} low-priority
move-priorities}

{moves p-drop
{move} select-piece {move-type} high-priority
{move} drop-half {move-type} normal-priority
{move} drop-piece {move-type} normal-priority
{move} Pass {move-type} low-priority
moves}

{pieces
{piece} M {drops} p-drop
{piece} x1
{piece} o1
{piece} x2
{piece} o2
{piece} x3
{piece} o3
{piece} x4
{piece} o4
{piece} x5
{piece} X1 1 {value}
{piece} O1 1 {value}
{piece} X2 2 {value}
{piece} O2 2 {value}
{piece} X3 3 {value}
{piece} O3 3 {value}
{piece} X4 4 {value}
{piece} O4 4 {value}
{piece} X5 5 {value}
pieces}

Решта проста. Навіть коректне виконання згортки не настільки складно. Грег придумав спеціальні функції для роботи з кільцевим буфером, але я, до свого сорому, так жодного разу ними не скористався. Старий добрий трюк з додаванням в кінець масиву, за яким йдуть ітерації, все ще працює:

: add-position ( -- )
0 BEGIN
DUP here <> OVER empty-at? AND IF NOT
DUP piece-type-piece at-type = not OVER-in-position? AND curr-size @ ALL < AND IF
DUP curr-size @ pos[] !
curr-size ++
ENDIF
ENDIF
1+ DUP ALL >=
UNTIL DROP
;

: mark-all ( player -- )
marked-player !
here curr-pos !
DROP down
mr verify marked-player @ mark create-player-piece-type
DROP down
BEGIN
empty? NOT here curr-pos @ <> AND piece-type mark > AND IF
add-position
ENDIF
marked-player @ mark create-player-piece-type
NOT up
UNTIL
;

: untangle ( -- )
0 BEGIN
DUP curr-size @ < IF
DUP pos[] @
to player piece-type OVER mark-all
DROP down
bg verify
DIM + create-player-piece-type
1+ FALSE
ELSE
TRUE
ENDIF
UNTIL DROP
;

Залишився ще один не розглянутий питання. Гра закінчується, коли одному з гравців вдається побудувати лінію з хрестиків або нуликів (звичайно, в звичайних «Хрестики-ноликах» таке відбувається вкрай рідко), але в нашому божевільному квантовому світі хрестики і нулики можуть побудувати свої лінії одночасно! Кого вважати переможцем?


Allan Goff пропонує знову задіяти індекси, що використовуються для нумерації ходів. Для кожної побудованої лінії повинен бути знайдений максимальний індекс. Той, у кого цей індекс виявився менше, перемагає. Оскільки, в своїй роботі він використовує наскрізну нумерацію ходів (X1, O2, X3,...), при наявності лінії, переможець буде завжди. Легко помітити, що я використовую іншу схему нумерації і, в моєму випадку, знову виходить нічия.

Що змусило мене відійти від канонів? Два міркування. По-перше, наскрізна схема нумерації дає дуже серйозну перевагу першому гравцеві. На мій погляд, ігровий баланс набагато важливіше гіпотетичної можливості отримання нічиєю (серйозно, в «Квантових хрестики-ноликах», нічия — рідкісна ситуація). Що ще важливіше, наскрізна нумерація (і пов'язана з нею методика визначення переможця) є абсолютно неприйнятною для «Квантового Морріса», мова про яких піде нижче. Там, у кожного з гравців, всього за три фігури.

Танцюють всі!

Танець Морріса — найдавніший англійський звичай, пов'язаний з ритуалами родючості. Бажаючим перейнятися духом цього дійства з задоволенням рекомендую «Зимових справ майстри» за авторством Террі Пратчетта. Про сам танець там розказано побіжно, але зате від душі! В рамках нашої розповіді, більш важлива зв'язок цього звичаю з цілим семейством настільних ігор, неймовірно популярним у середньовічній Європі. Молодша гра сімейства ("Танець трьох чоловіків") — ще один спосіб «покращення» хрестиків-нуликів. Фактично, це сполучна ланка між ними та більш пізніми іграми з рухомими фігурами, такими як "Лисиця і гуси" або "Алькуэрк".

В основі гри лежить дуже проста ідея: якщо не вдалося побудувати ряд відразу, то все ще можна перемогти, рухаючи вже викладені фішки по черзі! Щоб було куди рухатися, кожен гравець використовує всього за три фігури (цього достатньо для побудови лінії). У старших іграх сімейства, таких як "Танець дев'яти чоловіків", гравець, який побудував ряд («млин»), має право безповоротно «змолоти» будь-яку фігуру супротивника, вже поставлене на дошку. У нашому випадку, оскільки фігур з кожної сторони всього по три, втрата будь-якої з них означає безумовне поразку. Двох фігур недостатньо для побудови ряду!

Звідси до «Квантового Морріса» всього один крок! Хоча проблема «нічийної смерті» вже не стоїть «Квантових хрестики-ноликах» настільки гостро, сама гра залишається занадто швидкоплинною. Обмеження кількості фігур до трьох (з кожної сторони) і їх переміщення після виставлення на дошку, допоможуть «розтягнути» гру, додавши в неї видовищності і несподіванки.



Легко помітити, що переміщуються лише малі «півпостаті». Також можливо «розщеплення» повної фігури на дві півпостаті, з переміщенням однієї з них на іншу позицію. Велику фігуру переміщати можна. Як і в «Квантових хрестики-ноликах», існує можливість «детермінованих» ходів. Крім «скидання» двох полуходов в одну клітинку, ми можемо «злити» півпостаті, переміщаючи одну з них до іншого. Я як і раніше вважаю такі ходи надміру сильними і забороняю їх у частині варіантів гри.

Зриваємо покровиРозглянемо один з попередніх скріншотів, використовуючи злегка змінений набір графічних ресурсів. Все таємне негайно стає явним:


Ці темно-зелені кружечки — допоміжні фігури, невидимі при нормальній роботі програми. Для чого вони? Почнемо з осередку містить два кружечка. Допоміжна фігура, розташована у правому нижньому куті — маркер. Їм відзначається область дошки, в якій виконувався останній хід. З цієї позиції можна починати пошук колізії. Якщо колізія є, одна з областей, що входять у неї обов'язково буде позначена. В принципі, можна було б обійтися і без них, але мені не хотілося ускладнювати і без того складний алгоритм пошуку колізій. Очевидно, що цю комірку можна використовувати абсолютно безпечно. Кожна область дошки може містити не більше восьми малих фігур.

Кружечок по центру — більш цікавий об'єкт. Справа в тому, що малі фігури додаються в клітинки дошки по порядку, а не в те місце куди виконується скидання (drop) фігури через користувальницький інтерфейс. Відповідно, і скидається не сама постать, а допоміжний невидимий маркер. Чому він не видаляється? Гра використовує дві дошки (grid), накладені одна поверх іншої. 9x9 зберігаються малі фігури, а в 3x3 — великі. Якщо я буду видаляти скида маркер, то зруйную зображення на укрупненої дошці. На відео помітно, що зображення все одно руйнується (при розщепленні великих фігур), але цей ефект короткочасний. Крім того, з ним я нічого вдіяти не можу.

Забавніше всього призначення дев'яти кружечків, розташованих в одній області з великою фігурою. Тут ми знову маємо справу з витратами користувальницького інтерфейсу. Клітинки дошки 9x9 розташовані поверх великої сітки і практично повністю перекривають її фігури. У грі Морріса, фігури необхідно рухати. У тому числі і великі (при цьому відбувається розщеплення). Але для того, щоб посунути фігуру, необхідно мати можливість зачепити її мишею, а для фігур на сітці 3x3 зробити це досить проблематично (навіть якщо над ними немає жодних фігур). Довелося додати «рукоятки», смикаючи за які можна розщеплювати великі фігури.

«Квантові хрестики-нулики» є, можливо не ідеальною, але вельми вдалою ілюстрацією ідей квантової механіки. Ця гра привертає до себе увагу. Вона використовується при проведенні змагань з програмування, питання на цю тему періодично з'являються на StackExchange. В даний час, не складає труднощів знайти її програмну реалізацію. Вона розроблена як для Чоловічий так і для iOS. Особливо нетерплячі можуть грати безпосередньо через Web-інтерфейс. Одними лише «Хрестиками-нуликами» набір «квантових» ігор не обмежується. В якості бонусу, можу порекомендувати ще і цю гру.

Всіх з п'ятницею, Панове!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.