Калах - Kalah
Калах | |
---|---|
Ранги | Два |
Посев | Один круг |
Область, край | Соединенные Штаты , Соединенное Королевство |
Калах , также называемая Калаха , является копией древней игровой манкалы, зарегистрированной в Соединенных Штатах Уильямом Джулиусом Чэмпионом- младшим в 1940 году. Эту игру иногда также называют «Калахари», возможно, по ложной этимологии из пустыни Калахари в Намибии .
Как наиболее популярный и коммерчески доступный вариант манкалы на Западе, Кала также иногда называют Варри или Авари , хотя эти имена более правильно относятся к игре Oware .
Для большинства вариантов Кала - это решенная игра, в которой выигрывает первый игрок, если оба игрока играют идеально. Правило пирог может быть использовано , чтобы сбалансировать преимущество первого-игрок.
Пример поворота
Игрок начинает посев из подсвеченного домика.
Последнее семя попадает в магазин, поэтому игрок получает дополнительный ход.
Последнее семя падает в пустой дом на стороне игрока. Игрок собирает выделенные семена как из своего дома, так и из дома, противоположного оппоненту, и перемещает их в магазин.
В игре есть доска Калаха и ряд семян или жетонов. На доске по 6 ямок, называемых домиками, с каждой стороны; и большая яма, называемая конечной зоной, на каждом конце. Цель игры - захватить больше семян, чем противник.
- В начале игры в каждый дом кладется по четыре семени. Это традиционный метод.
- Каждый игрок контролирует шесть домов и их семена на стороне игрока. Счет игрока - это количество семян в магазине справа от него.
- Игроки по очереди сеют семена. В свой ход игрок убирает все семена из одного из домов под его контролем. Двигаясь против часовой стрелки, игрок по очереди бросает по одному семени в каждый дом, включая собственный магазин игрока, но не его оппонента.
- Если последнее посеянное семя попадает в пустой дом, принадлежащий игроку, а противоположный дом содержит семена, последнее и противоположные семена захватываются и помещаются в магазин игрока.
- Если последнее посеянное семя попадает в магазин игрока, игрок получает дополнительный ход. Нет ограничений на количество ходов, которые игрок может сделать в свой ход.
- Когда у одного из игроков больше нет семян ни в одном из домов, игра заканчивается. Другой игрок перемещает все оставшиеся семена в свой магазин, и игрок с наибольшим количеством семян в его магазине побеждает.
Игра может закончиться ничьей.
Вариации
- Игра может начинаться с количеством семян в каждом доме, отличным от четырех. Для описания этих вариаций была разработана номенклатура: Kalah ( h , s ), где h обозначает количество домов с каждой стороны, а s обозначает количество семян, которые начинаются в каждом доме. В широком смысле, чем больше семян, тем сложнее становится игра. Калах с тремя, четырьмя, пятью и шестью посевами был решен, причем первый игрок всегда выигрывает с идеальной игрой. Таким образом, некоторые веб-сайты внедрили игру с правилом пирога, чтобы сделать ее честной.
- Альтернативное правило предполагает, что игроки сеют по часовой стрелке, при этом за один ход нужно посеять больше камней, чтобы добраться до магазина.
- Вариант «Пустой захват»: если последнее посеянное семя попадает в пустой дом, принадлежащий игроку, даже если противоположный дом пуст, последнее семя захватывается и помещается в магазин игрока.
- Альтернативное правило не учитывает оставшиеся семена как часть счета соперника в конце игры.
Компьютерный анализ Калаха
Марк Роулингс написал компьютерную программу для всестороннего анализа как «стандартной» версии Калаха, так и версии «пустого захвата», которая является основным вариантом. Анализ стал возможным благодаря созданию самой большой базы данных по эндшпилю, когда-либо созданной для Калаха. Они включают в себя идеальный результат игры по всем 38 902 940 896 позициям с 34 или меньшим количеством семян. В 2015 году впервые в истории каждый из начальных ходов для стандартной версии Кала (6,4) и Кала (6,5) был количественно определен: Кала (6,4) - доказанная победа на 8 для первый игрок и Калах (6,5) - это доказанная победа с разницей в 10 для первого игрока. Кроме того, Калах (6,6) со стандартными правилами доказал свою победу как минимум на 4. Дальнейший анализ Калах (6,6) со стандартными правилами продолжается.
Что касается версии «пустой захват», Джеффри Ирвинг и Джерун Донкерс (2000) доказали, что Калах (6,4) - это победа на 10 для первого игрока с идеальной игрой, а Кала (6,5) - на 12 для первый игрок с безупречной игрой. Андерс Карстенсен (2011) доказал, что Калах (6,6) стал победой для первого игрока. Марк Роулингс (2015) расширил эти результаты «пустого захвата», полностью определив начальные шаги для Калаха (6,4), Калаха (6,5) и Калаха (6,6). Проведя поисковые запросы в общей сложности 106 дней и используя более 55 триллионов узлов, он доказал, что Калах (6,6) - это выигрыш в 2 раза для первого игрока с идеальной игрой. Это был неожиданный результат, учитывая, что варианты «4-посевной» и «5-посевной» дают выигрыш на 10 и 12 соответственно. Калах (6,6) является чрезвычайно глубоким и сложным по сравнению с вариантами с 4 и 5 начальными числами, которые теперь можно решить за доли секунды и менее чем за минуту соответственно.
Базы данных эндшпиля, созданные Марком Роулингсом, были загружены в оперативную память во время инициализации программы (загрузка занимает 17 минут). Таким образом, программа могла работать на компьютере с 32 ГБ ОЗУ, базы данных с 30 и 33 начальными значениями не загружались.
Endgame database counts: seeds position count cumulative count ------------------------------------------- 2-25 1,851,010,435 1,851,010,435 26 854,652,330 2,705,662,765 27 1,202,919,536 3,908,582,301 28 1,675,581,372 5,584,163,673 29 2,311,244,928 7,895,408,601 30 3,158,812,704 11,054,221,305 31 4,279,807,392 15,334,028,697 32 5,751,132,555 21,085,161,252 33 7,668,335,248 28,753,496,500 34 10,149,444,396 38,902,940,896 -------------------------------------------
В следующих разделах бункеры пронумерованы, как показано, с зазором против часовой стрелки. Юг перемещается из ящиков с 1 по 6, а север перемещается из ящиков с 8 по 13. Ячейка 14 - это магазин Севера, а ячейка 7 - это магазин Юга.
<--- North ------------------------ 13 12 11 10 9 8 14 7 1 2 3 4 5 6 ------------------------ South --->
Калах (6,4)
Исходное положение с 4 семенами в каждом бункере:
<--- North ------------------------ 4 4 4 4 4 4 0 0 4 4 4 4 4 4 ------------------------ South --->
В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала идет Юг) как для стандартных правил, так и для варианта «пустой захват». Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 3 приводят к «повторному ходу». Глубина поиска продолжалась до конца игры.
Standard Rules: move result perfect play continuation ------------------------------------------------------- 1 lose by 14 10 13 3 9 13 12 1 13 11 5 13 2 lose by 10 10 13 5 9 13 8 4 10 13 8 5 3-1 lose by 6 10 11 2 13 1 12 1 13 9 4 12 3-2 tie 10 13 5 9 13 8 3 11 1 13 10 3-4 win by 2 10 9 13 2 1 12 3 5 8 12 13 3-5 win by 4 9 10 2 5 12 1 2 11 2 13 5 3-6 win by 8 9 8 2 12 6 5 11 6 1 6 5 4 lose by 2 10 12 2 4 13 1 5 9 13 12 13 5 lose by 8 10 9 11 2 5 10 1 8 4 12 5 6 win by 4 9 12 2 6 1 11 4 10 6 5 13 -------------------------------------------------------
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1 lose by 14 10 13 4 9 13 11 2 13 8 13 10 2 lose by 8 10 13 5 9 13 8 4 10 13 9 5 3-1 lose by 8 10 11 4 9 12 2 10 5 11 12 9 3-2 lose by 2 10 13 5 9 13 8 3 11 5 13 10 3-4 win by 2 10 9 13 2 1 12 3 5 8 12 13 3-5 win by 4 9 11 2 4 8 12 5 13 5 11 4 3-6 win by 10 9 8 4 11 6 2 6 4 9 5 13 4 lose by 2 10 12 2 5 9 8 12 9 4 10 11 5 lose by 6 10 9 11 4 8 13 5 6 4 12 6 6 win by 4 9 12 2 6 1 11 4 10 6 5 13 -------------------------------------------------------
Калах (6,5)
Starting position with 5 seeds in each bin:
<--- North ------------------------ 5 5 5 5 5 5 0 0 5 5 5 5 5 5 ------------------------ South --->
В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала идет Юг) как для стандартных правил, так и для варианта «пустой захват». Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 2 приводят к «повторному ходу». Глубина поиска продолжалась до конца игры.
Standard Rules: move result perfect play continuation ------------------------------------------------------- 1 lose by 10 9 11 4 8 13 2 9 6 3 11 13 2-1 lose by 4 9 10 2 12 1 11 3 12 8 11 1 2-3 win by 10 10 1 6 9 5 13 6 2 8 4 13 2-4 win by 10 8 11 1 6 9 2 13 11 4 12 6 2-5 win by 8 8 10 1 6 9 5 13 12 2 13 11 2-6 tie 8 11 1 6 3 11 6 5 12 6 8 3 win by 2 9 8 12 1 4 11 2 12 10 4 3 4 win by 2 8 11 1 5 12 3 10 5 2 11 6 5 win by 2 8 12 1 4 9 2 12 4 9 3 11 6 tie 8 12 1 6 4 10 6 2 11 4 3 -------------------------------------------------------
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1 lose by 10 9 12 6 8 12 11 2 8 6 5 12 2-1 lose by 6 9 10 2 12 4 8 9 3 10 11 3 2-3 win by 12 8 10 1 6 10 5 13 9 6 4 11 2-4 win by 8 8 9 1 6 11 4 13 10 4 13 9 2-5 win by 8 8 10 1 6 9 5 13 12 3 13 6 2-6 lose by 2 8 11 1 6 5 9 6 3 11 12 5 3 win by 2 9 8 12 1 4 11 2 10 4 5 10 4 tie 8 11 1 5 12 3 9 5 2 11 3 5 tie 8 10 1 4 12 5 11 2 9 4 13 6 tie 8 12 1 6 4 9 6 2 12 6 5 -------------------------------------------------------
Калах (6,6)
Исходное положение с 6 семенами в каждом бункере:
<--- North ------------------------ 6 6 6 6 6 6 0 0 6 6 6 6 6 6 ------------------------ South --->
В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала идет Юг) для варианта «пустой захват» и текущее состояние результатов для стандартного варианта. Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 1 приводят к «повторному ходу». Глубина поиска варианта «пустой захват» продолжалась до конца игры.
"Standard" Variant: (Results are still being computed by Mark Rawlings.) move result ------------------------------------------------------- 1-2 proven win, by at least 2 1-3 proven win, by at least 4 1-4 1-5 1-6 proven loss, by at least 2 2 trending towards a win 3 4 5 6 proven loss, by at least 2 ------------------------------------------------------- The remaining moves (1-4, 1-5, 3, 4, and 5) are probable ties based on very deep searches, however, the result has not yet been proven.
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1-2 win by 2 10 3 12 4 8 6 10 11 6 3... 1-3 win by 2 11 1 8 2 10 6 8 3 11 5... 1-4 tie 10 3 12 5 10 3 9 1 12 3... 1-5 tie 9 4 8 3 10 2 10 4 1 9... 1-6 tie 10 4 9 6 3 11 6 8 2 10... 2 win by 2 12 4 10 1 12 8 1 11 3 9... 3 tie 10 5 12 4 11 1 12 8 4 3... 4 tie 10 3 11 1 9 5 11 2 10 8... 5 tie 10 3 11 4 12 2 11 4 10 5... 6 loss by 2 10 3 8 6 4 13 1 10 13 8... -------------------------------------------------------
Разбивка более чем 55 триллионов узлов, которые искали, чтобы решить вариант Калаха с «пустым захватом» (6,6):
move time (sec) nodes searched ---------------------------------------- 1-2 305,791 2,214,209,715,560 1-3 403,744 2,872,262,354,066 1-4 401,349 2,335,350,353,288 1-5 317,795 1,886,991,523,192 1-6 392,923 2,313,607,567,702 2 1,692,886 9,910,945,999,186 3 1,296,141 7,398,319,653,760 4 1,411,091 9,623,816,064,478 5 1,607,514 9,318,824,643,697 6 1,354,845 7,824,794,014,305 ---------------------------------------- total 9,184,079 55,699,121,889,234
Математический анализ
Как упоминалось выше, если последнее посеянное игроком семя попадает в магазин этого игрока, игрок получает дополнительный ход. Умный игрок может воспользоваться этим правилом, чтобы связать воедино много-много дополнительных ходов. Таким образом, некоторые конфигурации ряда доски могут быть очищены за один ход, то есть игрок может захватить все камни в своем ряду, как показано справа. Самая длинная из возможных цепочек на стандартной доске Кала из шести ям длится семнадцать ходов. На обычной доске с n- ярусами образцы семян, которые можно очистить таким образом за один ход, были объектом математического исследования. Можно доказать, что для всех n существует один и только один шаблон, который можно очистить ровно за n ходов, или, что эквивалентно, один и только один шаблон, который можно очистить, состоящий ровно из n начальных чисел .
Эти шаблоны требуют произвольно длинных рядов ямок и n увеличений. Например, справа можно увидеть, что для уникального шаблона с 5 семенами требуется только 3 ямки, а для шаблона с 17 семенами требуется 6 ямок. Связь между необходимым количеством ямок и количеством семян можно описать следующим образом. Пусть s (n) обозначает минимальное количество семян, для очистки которых требуется n ямок. Тогда где символ обозначает асимптотическую эквивалентность , то есть , или , что эквивалентно, .
Смотрите также
Рекомендации
- ^ Решение Kalah Джеффри Ирвингом, Джеруном Донкерсом и Джосом Уитервейком.
- ^ Решение (6,6) -Калаха Андерсом Карстенсеном.
- ^ a b Broline, Duane M .; Лоеб, Дэниел Э. (1995-02-08). «Комбинаторика игр типа манкала: Ayo, Tchoukaitlon и 1 / π». arXiv : math / 9502225 .