Original: http://wilson.engr.wisc.edu/boxes/method/

Девід Уілсон

Дивлячись на кожну можливу послідовність ходів, створюється n! час для аналізу. Моя програма замість цього дивиться на кожну можливу позицію, що дає час для аналізу. Незважаючи на те, що 2ⁿ швидко стає великим, це ніде не так велике, як n!.

Робота у зворотному напрямку

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

Аналіз виконується у зворотному напрямку від позиції, коли всі лінії заповнені. Цим положенням присвоюється значення, вказане в першому рядку файлу даних (зазвичай нуль). Потім програма обробляє позиції з однією меншою лінією. Коли це зроблено, вона обробляє позиції іншою лінією менше. Зрештою він повертається до вихідної позиції.

Для кожної такої позиції програма враховує всі можливі ходи і зберігає рахунок з найкращим результатом для гравця на ходу.

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

Пошук позицій із заданою кількістю рядків

Позиція представлена ​​двійковим числом з одним бітом (двійковим розрядом), призначеним кожному рядку. Біт дорівнює 0, якщо лінія присутній і 1, якщо лінія відсутня. (Я змінив звичайну угоду, щоб полегшити перевірку нових полів.)

Я розділяю лінії на групи. Кожна група ліній представлена ​​послідовними бітами в двійковому номері позиції. Ці біти можуть бути скопійовані і поміщені в окремий номер, що представляє стан ліній всередині групи. Наприклад, для гри 3х3 є 24 сукупних рядків. Програма використовує дві групи рядків по 12 рядків. Для кожного можливого рахунку рядків для групи (від 0 до 12) програма створює список чисел, що представляють групу з цим числом рядків. Потім, щоб знайти позиції з набором n рядків, я об’єдную все першу групу зі станом i рядків, встановлених з другим станом групи, з набором n ліній, де i змінюється по всіх можливих значеннях, які не призводять до неможливого числа рядків групи. Наприклад, щоб знайти всі позиції з 15 лініями в грі 3х3, програма поєднує всі перші групи з трьома лініями з усіма станами другої групи з 12 лініями (є тільки одна з них), потім всі перші групи станів з 4 рядками з всі другі групи складаються з 11 рядків,…, і, нарешті, всі перші групи станів з 12 лініями (знову, тільки один можливий) з усіма станами другої групи з 3 рядками.

Пошук нових полів

Кожному рядку присвоюється номер індексу, що відповідає його біту в двійковому номері позиції. Програма має два набори значень віконних тестів, на які посилається номер індексу нового рядка. Один встановлює перевірку на нове вікно вище або ліворуч від нового рядка. Інший перевіряє на поле нижче або праворуч від нового рядка. Ці значення використовуються для перевірки наявності інших 3 ліній. Біти, що відповідають цим трьом рядкам, встановлюються рівними 1; всі інші біти встановлені на 0. Тест виконується з використанням логічної операції “і” між двійковим номером позиції і значенням тесту. Операція “і” для кожної бітової позиції виробляє 1, якщо встановлені відповідні біти в обох значеннях; 0 інакше. Оскільки двійкове число позиції має біти, встановлені в 0, якщо лінія присутній, то “і” цього і значення тесту дають нульовий результат тоді і тільки тоді, коли три лінії вже присутні.

Якщо поле не існує, оскільки рядок знаходиться на краю, тестове значення має всі біти, тим самим перевіряючи наявність всіх ліній. Оскільки тест виконується до того, як новий рядок поміщений у двійкове число позиції, існує щонайменше одна лінія не встановлена, і тест з цим значенням скаже, що немає нового вікна.

Використання груп із багатьох рядків

Після того, як ісландський аналіз пройшов всього за півгодини, я зрозумів, що час обчислень не буде проблемою для аналізу гри 3х5. Ісландська гра має 30 відкритих рядків, а гра 3×5 має 38 відкритих рядків, що ускладнює 256 (28) разів. 256 разів півгодини – 128 годин або близько 5 днів. Оскільки я міг налаштувати програму для запуску там, де він зупинився після переривання або перезавантаження, ці 5 днів можна було легко здійснити протягом ночі та у вихідні дні. Отже, проблемою стало з’ясування того, як зробити її зручною на моїй машині з 256 Мб оперативної пам’яті і 16 Гб вільного місця на диску.

Спочатку це не здавалося можливим. Зберігання аналізу займе 238 байт або 256 ГБ дискового простору. Простір, необхідний в оперативній пам’яті під час розрахунку значення для позицій з 19 рядками, при цьому посилаючись на результати для позицій з 20 лініями, буде 56 ГБ, а більше ніж моя чверть ГБ оперативної пам’яті.

Припускаючи, що лінії були розділені на дві групи по 19 рядків кожен, я міг би мати в ОЗУ тільки значення, що відповідають заданому числу рядків для кожної з двох груп. Наприклад, при виконанні позицій з 19 лініями, я міг би оцінювати позиції з 9 рядками в першій групі і 10 рядками у другій групі. Я називаю ці позиції 9/19 10/19. Для обчислення цих значень я маю звертатися до двох наборів позицій з 20 лініями: 10/19 10/19 і 9/19 11/19. Мені не потрібні були обидва ці 20 наборів рядків в пам’яті одночасно; вони можуть бути використані поодинці, зберігаючи найкращі оцінки з урахуванням нових рядків у першій групі для всіх позицій 9/19 10/19, а потім бачити, чи може бути досягнуто поліпшення в балах з новою лінією у другому групи. Два буфери займуть лише 16 ГБ.

Потім я зрозумів, що можу розбити лінії на більш ніж дві групи. Використовуючи 6 груп, я міг би скоротити обсяг оперативної пам’яті, який містив лише 426 Мб. Подальший розріз з використанням симетрії (див. Нижче) зробив його придатним. Звичайно, щоб знайти, наприклад, бали за позиції 4/8 3/6 3/6 3/6 3/6 3/6, програма повинна була прочитати в шести різних наборах з 20 рядками – кожен що має ще одну лінію в одній з шести груп.

Симетрія

Гра 3×5 симетрична по вертикалі і по горизонталі, так що, користуючись симетрії, я міг би розділити вимоги до простору на 4 (на насправді, на 3 в моїй остаточної реалізації). Пол Стівенс повідомив  про помилку в тесті для симетрії по діагоналі на квадратної дошці.

Щоб розрахувати бали за позицію, програма дивиться на попередньо розраховані оцінки позицій, що випливають з додавання ще однієї лінії. Проте додавання рядка може призвести до позиції, яка повинна бути симетрично перетворена перед тим, як її можна знайти. Щоб переконатися, що бал за позицію, що є результатом симетричного перетворення, одразу доступний, необхідно, щоб перетворення відобразило будь-які рядки в одну і ту ж групу. Таким чином, кількість рядків у кожній групі залишається незмінною після перетворення.

Перш ніж програма призначає рядки групам, вона спочатку шукає рядки, які пов’язані один з одним симетричним перетворенням. У грі 3×5 є сім наборів з 4 ліній і п’яти наборів з 2 ліній, які пов’язані між собою. Потім програма призначає групи рядків. Для гри 3х5 з 256 Мб оперативної пам’яті виходить шість груп (кожен з двома наборами ліній) розмірів 8 6 6 6 6 6.

Щоб визначити, чи повинна бути позиція симетрично перетворена, програма дивиться на рядки тільки в першій групі. Під час фази установки програма сканує всі можливі конфігурації рядків у першій групі рядків. До кожної конфігурації застосовуються вертикальні відображення, горизонтальне відображення і відображення через перетворення походження. Якщо одне з цих перетворень призводить до числа для стану рядків у групі, що є чисельно меншим, ніж число для початкових рядків, то (1) конфігурація НЕ включена в пов’язаний список конфігурацій з задане число рядків і (2) збережено інформацію про те, яке симетричне перетворення необхідно використовувати для отримання позиції, оцінка якої була розрахована – тобто, як дістатися до відповідної конфігурації з найменшим числовим значенням для стан його ліній.

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

Збереження дискового простору

Очки для позицій з заданим числом рядків у кожній групі зберігаються в одному файлі диска. Наприклад, оцінки для позицій 4/8 3/6 4/6 2/6 3/6 3/6 зберігаються у файлі:  \Boxes\3×5\19\4\3\4\2\3.bin

Зворотні риски розділяють імена вкладених папок. 3×5 – назва гри, що аналізується. 19 – загальна кількість рядків у позиції. Решта назв папок і назви файлів походять з числа рядків у групах. Кількість рядків в останній групі не використовується, оскільки вона фіксується іншими номерами. .Bin означає, що це двійковий файл – його вміст не можна переглядати безпосередньо. Вкладені папки використовуються, оскільки Windows обробляє папки з великою кількістю файлів дуже повільно.

Симетричні перетворення скорочують необхідний дисковий простір від 256 Гб до 85 ГБ. Однак не потрібно зберігати всі результати аналізу. Як тільки програма була виконана з позиціями 19 рядків, результати для позицій з 20 рядками можна було видалити. За наявності всього 16 Гб вільного місця на диску програма зберігає результати для позицій з 15 або менше рядків. Це призводить до “відкриття книги” для гри 3х5.

Проте, збереження лише результатів для 20 позицій рядків і 19 позицій на лінії все ще займає 22 ГБ. Це вирішується видаленням частин файлів позиції 20 рядків, оскільки вони більше не потрібні для подальшого розрахунку балів за 19 позицій рядків. Коли програма проходить всі можливі комбінації ліній для груп, які додають до 19 рядків, кількість перших груп не зменшується. Таким чином, після того, як кількість першої групи рядків переміститься від 0 до 1, можна видалити всі файли, що починаються з \Boxes\3×5\20\0\. З цією зміною аналіз відповідає 16 ГБ.

Ланцюги

На даний момент, програма все ще недостатньо для вирішення 5×5 проблеми в главі 12 Гри в крапки-та-поля за Елвіном Берлікампом (AK Петерс, 2000). Якщо комп’ютери продовжують подвоювати свою потужність кожні 18 місяців, ми повинні мати можливість аналізувати всю гру 5×5 у 2034 році, оскільки вона має ще 22 лінії, ніж гра 3х5, яка була проаналізована в 2001 році. 36 відкритих рядків, де позиція не має симетрії, і 14 Гб дискового простору. Це означало, що тільки 5×5 позиції з 24 або більше рядків (з 60) можуть бути вирішені. Жоден з проблем, пов’язаних з розділом 12, не мав таких багато рядків.

Ланцюг – це рядок з одного або декількох коробок з двома сторонами. Я зробив припущення, що як тільки один з гравців зайняв лінію в ланцюжку, принаймні одна з кращих ліній відтворення включає всі інші лінії в ланцюжок, що заповнюється одним гравцем або іншим, перед тим, як заповнити будь-які рядки. Кожен набір ланцюгових ліній представлений однією “псевдолінією”. Положення в програмі має лише один біт, який говорить про те, чи був цілий ланцюжок повністю заповнений або все ще повний. Наприклад, тут позиція для завдання 12.18 (перед переміщенням пунктирною лінією):

+     +     +  .  +     +     +
            |  .  |
            |  .  |
            |  .  |
+     +  .  +  .  +     +     +
      |  .  |  .
      |  .  |  ....
      |  .  |
+     +  .  +-----+-----+-----+
      |  .  |
      |  .  |  ..........
      |  .  |  .
+     +  .  +  .  +-----+  .  +
            |           |  .
            |     ....  |  ....
            |        .  |
+     +     +  .  +  .  +-----+
            |  .
            |  ....
            |
+     +     +-----+     +     +

Точки позначають ланцюжки, кожна з яких представлена ​​єдиною псевдолінією. З 60 ліній, 15 заповнені, 30 порожні, 15 – у 6 ланцюгах. Позиції, які можуть виникнути з цієї початкової позиції, представлені 36 бітами – 30 для порожніх рядків і 6 для 6 ланцюгів. Таким чином, ця позиція ледве знаходиться в межах поточних можливостей програми.

У багатьох позиціях, що випливають з даної вихідної позиції, початкові ланцюги стануть частиною довгих ланцюгів. У цій ситуації програма не змінює схему подання позицій. Псевдолінії продовжують представляти лише початкові ланцюги. Це пояснюється тим, що представлення позиції використовується як “адреса” для доступу до раніше обчислених балів.

Оцінюючи, чи перехід на початковий ланцюжок є гарною ідеєю для гравця на ходу, програма має доступ до чистого рахунку з найкращою грою для майбутніх ящиків для гравця на ходу після заповнення всього початкового ланцюга. Потім програма повинна перевірити коробки навколо ланцюга, щоб побачити, який гравець матиме перший шанс взяти ящики в ланцюжку, щоб побачити, якщо цей гравець отримає користь від жертви, щоб уникнути приведення в рух після того, як ланцюжок заповнений , і перевірити, чи ланцюжок був розширений або навіть виконаний частиною петлі.

Якщо початкова ланцюг має тристоронню коробку з обох боків відразу за ланцюгом, то гравець на ходу може переміщатися в ланцюг з захопленням і має можливість брати коробки в ланцюжку. В іншому випадку, це інший гравець, який має опцію в ланцюжку. Я буду називати людину з можливістю брати ящики в ланцюжку, “ланцюгового гравця”.

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

Штраф останнього руху

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

• При виконанні аналізу в двох різних штрафів за рахунок переїзду не може змінюватися більш ніж на плюс або мінус різниця в покараннях.
• Для послідовних цілочисельних штрафів, один аналіз результатів в усі парній целочисленной оцінці і інші результати у всіх непарних балах.
• Таким чином, для послідовних цілих штрафів, оцінки завжди змінюється на +1 або -1… максимально можливої.
• Таким чином, ви можете отримати рахунок для будь-якого дрібного страти інтерполяції між оцінками за сусідні цілі штрафи.

Дурнуваті рухи

Остаточна версія програми включає в себе аналіз несамовитого руху. На виході, рахунок зафіксовано суфіксом v, якщо гравець A повинен зробити наступний дурний хід або ^ якщо гравець B повинен. Якщо жоден з гравців не повинен робити дурний хід, суфікс не використовується. Під час аналізу два біти байта, використовуваного для утримання рахунку, використовуються для утримання дурного стану переміщення. Це залишає всього 6 біт для балів. Таким чином, можна зберегти тільки оцінки від -32 до +31. Це робить дурний ход аналізу версії програми ненадійним на дошках більше 5 на 6. Тому я зберігаю доступну версію, яка не робить дурний крок аналізу для використання з більшими платами.

Щоб знайти дурня рухається в розумний час комп’ютера, програма робить дурний бонус перевірки, коли можна захопити ящик. Якщо коробка на іншій стороні лінії, що розглядається, має точно дві інші сторони вже заповнені, програма робить висновок, що попередній хід противника був дурним.

Куточки

Вільям Фрейзер писав: “Чи враховуєте ви, що [ab] і [ba] посилаються на еквівалентні посилання? Отже (якщо ви покладете вісім кутових посилань на останню 8-ма групами), ви можете зберегти лише 3^4 = 81 Записи замість 2^8 = 256. Це було б повністю незалежним від обертання/відображення. Це знижує споживання диска на 75% і використання пам’яті в середньому на 75%.”

Я реалізував цю пропозицію, що дозволило проаналізувати гру 4х4.

David Wilson/[email protected]