MakarovSuites
Українська
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Зв’язок і ліцензії

Math

Нім і двійкова сума

Купи каменів, а під ними їхній двійковий запис. Розряд із непарним числом одиниць горить червоним; коли червоних немає, той, чий хід, уже програв. Правило перевірено розбором усієї гри.

Нім і двійкова сума — Зображення з програми
Зображення з програми

Що відбувається

Бери скільки завгодно каменів з ОДНІЄЇ купи; програє той, кому брати нічого. Під купами картка малює їхній двійковий запис, стовпчик на купу, і розряд із непарним числом одиниць горить червоним. Твердження Бутона: позиція програшна для того, чий хід, рівно тоді, коли червоних розрядів немає — коли двійкова сума дорівнює нулю. Вірити на слово не пропонують: кожну позицію простору станів розмічено розбором гри до кінця, і мітки звірено з правилом на 729, 2197, 4096 і 7776 позиціях — жодного розходження. Щоб залишити супернику нуль, треба погасити червоні стовпці, а зробити це може тільки купа, у якої в старшому червоному розряді стоїть одиниця. Таких куп непарна кількість — інакше розряд не був би червоним, — тож виграшних ходів один або три і ніколи два: за трьома купами 1092 позиції мають один хід, 148 мають три, і жодна не має двох. Увімкни мізер, де той, хто взяв останній камінь, програє, і те саме правило ламається: розібране дерево суперечить йому саме на позиціях з одиночних каменів.

Рівняння модуля
Рівняння
купи каменів, хід забирає довільну кількість з ОДНІЄЇ купи, а гравець, якому нічого брати, програє
правило Бутона: позиція програшна для гравця, який ходить, рівно тоді, коли двійкова сума (виключне АБО) розмірів куп дорівнює нулю
картка цього не цитує - вона позначає КОЖНУ позицію, розв'язуючи гру до кінця, і порівнює: 729, 2197, 4096 і 7776 позицій, жодної розбіжності
виграшні ходи є купами з (h виключне АБО s) < h, і їх кількість ЗАВЖДИ НЕПАРНА - одна або три, ніколи не дві:
для трьох куп до 10 розподіл такий: 0 ходів у 91 позиції, 1 хід у 1092, 3 ходи у 148, а 2 ходи ні в одній
причина не випадкова: хід до нульової суми робить купа, що несе одиницю в старшому встановленому біті суми, і таких куп непарна кількість, інакше цей біт був би нульовим
програшні позиції пораховано точно: k куп з розмірами 0..2^b−1 містять 2^(b(k−1)) таких позицій - 64 для трьох куп по 0..7
МІЗЕР є іншою грою, і це правило там НЕПРАВИЛЬНЕ: розв'язання дерева розходиться з виключним АБО рівно на 2^k позиціях, і всі вони складаються з одиночних каменів
правило мізеру: поки якась купа містить більше одного каменя, грайте як зазвичай; коли кожна купа містить по одному, позиція програшна для гравця, що ходить, рівно тоді, коли їх кількість НЕПАРНА
(1,1,1) виграшна для гравця, що ходить, у звичайній грі та програшна в мізері; (1,1) навпаки; (2,1,1) виграшна в обох
типовий розклад 7-5-3 має двійкову суму 1 і рівно три виграшні ходи: до 6-5-3, до 7-4-3 та до 7-5-2

Інші експерименти

До каталогу
Дерево гри та альфа-бета — Зображення з програми

Math

Дерево гри та альфа-бета

Дерево гри, у якому кожен блок заввишки зі своє значення: MAX-вершина рівно з найвищу з дітей, MIN-вершина — з найнижчу. Мінімакс читає кожен листок; альфа-бета пропускає те, що не може змінити відповідь, і скільки пропустить — залежить від порядку ходів.

Код Гаффмана — Зображення з програми

Math

Код Гаффмана

Черга частот перетворюється на дерево префіксного коду. Виберіть літеру, щоб побачити її біти; проходьте злиття покроково.

Рюкзак: жадібність проти таблиці — Зображення з програми

Math

Рюкзак: жадібність проти таблиці

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