Перейти к содержимому

Мастер тогызкумалака

Хорошая новость! Наконец-то появилась программа для смартфонов и планшетов (под управлением Android), играющая в древнюю казахскую национальную игру тогызкумалак на уровне лучших мастеров спорта.

Программа «Мастер тогызкумалака» будет интересной и полезной для всех любителей интеллектуальной игры, которой насчитывается около 4 тысяч лет. В приложении предусмотрены различные уровни сложности от начинающего до мастера.
Эта программа также станет незаменимым помощником для профессиональных спортсменов и тренеров, поскольку с ее помощью можно анализировать различные позиции и готовиться к турнирам.

Другие возможности:
— дебютная библиотека;
— база партий мастеров (около 1000 партий);
— тестирование знаний;
— зал славы;
— подробная статистика и динамика выступлений.

Ссылка на PlayMarket.

Машина решает этюды

Около тридцати лет назад издательство «Жалын» выпустило книгу «Тогыз кумалак». Книгу написал Абилда Акшураев, и это была, пожалуй, первая серьезная попытка дать теоретическое описание основных принципов игры тогызкумалак. Помимо того, что в книге содержались созданные автором этюды и сыгранные в турнирах партии, она также включала в себя позиционные и тактические приемы, комбинации, была дана классификация дебютов. Кроме того, Акшураевым была проведена связь между игрой и математикой (подсчет ходов в концовке игры, влияние туздыка в той или иной лунке на количество оставшихся ходов, количество кумалаков, гарантированно набираемых даже при проигранном атсырау, и т.д.)

В главе «Этюды» приводится восемь этюдов, составленных автором книги, предлагается их решить, но решение в книге не приводится (по крайней мере, в издании 1983-го года, которое имеется у меня).

На программе «Тогызкумалак 2011» были протестированы все восемь этюдов, и она их решила. Задачи потребовали разное количество времени, поскольку для тех или иных задач потребовалась разная глубина перебора.

Машина решает этюды

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

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

Этюд 1. Ход белых, выигрыш.

72

2

2

78

1

x

1

3

2

1

 

Этюд 2. Ход белых, ничья.

76

1

x

2

77

x

4

1

1

 

Этюд 3. Ход белых, выигрыш.

55

2

3

2

5

1

9

66

x

2

3

4

8

2

 

Этюд 4. Ход белых, выигрыш.

73

1

2

74

x

3

3

3

3

 

Этюд 5. Ход белых, выигрыш.

66

2

1

7

2

76

3

3

2

 

Этюд 6. Ход белых, выигрыш.

71

1

2

72

6

x

5

3

2

 

Этюд 7. Ход белых, ничья.

68

2

3

x

2

74

x

5

4

1

2

1

 

Этюд 8. Ход белых, выигрыш.

61

2

2

x

4

4

3

2

74

4

3

2

1

x

 

Картинка взята с сайта http://www.etsy.com

Формат для записи партий тогызкумалак (Toguz Kumalak File Format Specification)

Вашему вниманию предоставляется разработанный Ернаром Шамбаевым формат TGK (Toguz Kumalak File Format Specification) для записи и хранения партий. Он частично основан на общепринятой форме записи партий, а также на формате записи шахматных партий PGN, ставший популярным благодаря удобству и наглядности. Формат удовлетворяет двум основным требованиям: 1) легок для записи и чтения людьми; 2) легок для разбора и генерации компьютерными программами. Будущим разработчикам программ для тогызкумалак рекомендуется придерживаться этой формы записи партий. В дальнейшем в блоге будет использоваться именно этот формат.

Каждая TGK-партия состоит из двух частей, разделенных пустой строкой: 1) метаданных, которые содержат информацию о партии в целом (кто играл белыми, кто играл черными, когда состоялась партия, где она состоялась, как завершилась и т.д.), и 2) собственно самой партии (в алгебраической нотации).

I. Метаданные

Первая часть партии заключает в себе список пар тегов, семь из которые обязательны.

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

Пример: [White «Тогызкумалак 2011»].

Если строковая лексема неизвестна, то в качестве значения должен указываться знак вопроса.

В каждой партии обязательно должны присутствовать семь тегов: White, Black, Result, Date, Event, Round, Site. Порядок их в файле произволен.

1. White

Тег предназначен для указания имени игрока, играющего белыми.

Пример: [White «Кабиев»]

2. Black

Тег предназначен для указания имени игрока, играющего черными.

Пример: [Black «Отебаев»]

3. Result

Тег предназначен для указания результата партии. Должен принимать одно из четырех значений:

а) «1-0» (белые выиграли);
б) «0-1» (черные выиграли);
в) «1/2-1/2» (партия завершилась вничью);
г) «*» (игра продолжается или результат неизвестен).

4. Date

Тег предназначен для обозначения даты начала партии.

Пример: [Date «2011»] или [Date «2011.10.21»] (в формате «ГГГГ.ММ.ДД»)

5. Event

Тег предназначен для обозначения турнира или матча.

Пример: [Event «Чемпионат Казахстана»]

6. Round

Тег предназначен для обозначения раунда или тура соревнования, в котором проводится партия.

Пример: [Round «9»]

7. Site

Тег предназначен для обозначения города или страны, в которой проводится партия.

Пример: [Site «Павлодар»]

II. Запись партии

Запись партии состоит из набора строк, каждая из которых содержит номер хода, ход белых и ход черных. Первое число задает номер хода, затем следует точка, за ней должен следовать пробел, затем ход белых, снова пробел и ход черных (если он был сделан).

Пример: 1. 76 98

Если ход привел к взятию туздыка, он должен обязательно сопровождаться символом «x».

Пример: 23. 93x 98x

Дополнительные (но необязательные) теги:

Count — для обозначения количества кумалаков в казанах в момент окончания партии
Пример: [Count «82-80»]

Comment — для кратких комментариев к партии
TimeControl — для описания контроля времени
WhiteElo и BlackElo — для обозначения рейтинга игроков
WhiteTitle и BlackTitle — для обозначения званий игроков

Пример партии, записанной в формате TGK:

[White «Кабиев»]
[Black «Отебаев»]
[Result «1-0»]
[Date «2011»]
[Event «Чемпионат Казахстана»]
[Round «9»]
[Site «Павлодар»]
[Comment «Выиграв эту партию, Кабиев стал новым чемпионом РК»]

1. 76 98
2. 66 87
3. 12 76
4. 25 35
5. 38 48
6. 42 24
7. 72 61
8. 34 17
9. 12 23
10. 89 12
11. 34 38
12. 47 48
13. 89 45
14. 78 23
15. 89 34
16. 62 12
17. 89 34
18. 78 45
19. 89 45
20. 67 23
21. 78 34
22. 45 23
23. 93x 98x
24. 35 12
25. 91 24
26. 12 85
27. 91 91
28. 13 61
29. 67 89
30. 23 92
31. 12 89
32. 91 78
33. 49 13
34. 91 24
35. 69 56
36. 56 12
37. 39 49
38. 47 71
39. 34 58
40. 69 45
41. 79 26
42. 95 13
43. 91

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Размышления о создании сильной программы (поиск истины)

Диана Кенина однажды сказала, что тогызкумалак для нее — это жизнь. Для меня тогызкумалак — это постоянный, непрекращающийся поиск истины, взлеты и падения, открытия и разочарования, своего рода научно-исследовательская работа.

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

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

Одна из проблем — это недостаток литературы по теории игры тогызкумалак (дебютные монографии, например, вообще отсутствуют, очень мало книг по стратегии игры) и практически полное отсутствие литературы по программированию игр семейства манкала (поэтому приходится изобретать свои эвристики, затрачивая массу времени). Можно найти немного информации по программированию родственной игры — калаха (см. журнал «Наука и жизнь» за 1971-й год), но калах слишком прост в сравнении с тогызкумалаком. Как ни странно, в наше время проще написать сильную шахматную программу, потому что шахматному программированию около 50 лет и на эту тему существует масса статей, материалов и накопленного опыта.

В игре тогызкумалак присутствует уникальный элемент — это туздык. Честно говоря, трудно подыскать аналог туздыка в других логических играх. Любой программист, решающий описываемую задачу, вынужден дать туздыку количественную оценку, а с этим не так все просто. Если в шахматах давным-давно известна ценность каждой фигуры (пешка — одна единица, конь и слон — по три, ладья — пять единиц, ферзь — девять, хотя на самом деле эти величины имеют немного другие значения, но это не так важно), то как определить ценность туздыка? Ни один игрок (будь он опытный любитель либо чемпион мира) не сможет дать вам точный ответ на этот вопрос, а если и даст, то со множеством оговорок, допущений и исключений. Ценность туздыка зависит от того, где он расположен, в какой стадии он установлен, зависит от взаимного расположения туздыков и т.д. Туздык не имеет точного математического эквивалента, а при создании программ желательно иметь строгие числовые значения, а не расплывчатые рассуждения. Формализация человеческого мышления — нетривиальная задача и неслучайно написание программ, играющих в логические игры, относят к одному из разделов искусственного интеллекта.

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

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

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Статистика по дебютам

Есть игры, исход которых заранее известен (крестики-нолики при точной игре с обеих сторон заканчиваются вничью, калах выигран за белых). С другими играми дело обстоит не так просто.

Рассмотрим начальную позицию игры тогызкумалак. В чью она пользу? Точный, математически обоснованный ответ на этот вопрос не сможет даст никто. Как уже было сказано в моей статье «Машина играет в тогызкумалак», дерево игры растет экспоненциально и для того, чтобы придти к терминальным позициям, у нас не хватит ни времени, ни компьютерных мощностей.

А что же говорит статистика?
Проведенный мной на основе 937 партий анализ (рассматривались партии, сыгранные в последнее время сильнейшими игроками в чемпионатах Казахстана, Азии, кубках РК, кубках Федераций РК и т.д.) показал, что у белых есть небольшое преимущество.

1. 21: 57 партий из 937 (6,08 %), Побед: 27, Поражений: 30, Ничьих: 0.

1. 32: 8 партий из 937 (0,85 %), Побед: 5, Поражений: 3, Ничьих: 0.

1. 43: 133 партии из 937 (14,19 %), Побед: 76, Поражений: 50, Ничьих: 7.

1. 54: 12 партий из 937 (1,28 %), Побед: 6, Поражений: 5, Ничьих: 1.

1. 65: 20 партий из 937 (2,13 %), Побед: 8, Поражений: 12, Ничьих: 0.

1. 76: 662 партии из 937 (70,65 %), Побед: 343, Поражений: 273, Ничьих: 46.

1. 87: 44 партии из 937 (4,70 %), Побед: 17, Поражений: 26, Ничьих: 1.

1. 98: 1 партия из 937 (0,11 %), Побед: 0, Поражений: 1, Ничьих: 0.

Подавляющее большинство партий (70 процентов) игралось дебютом 1. 76.

Наилучшие шансы у белых, когда они начинают партию ходами 1. 43 либо 1. 76.

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Мини-партии в тогызкумалаке (или «По следам дебютных катастроф»)

В шахматах есть такое понятие — «кооперативный мат». Одна из сторон делает все возможное, чтобы как можно быстрее проиграть. Например, самая короткая шахматная партия может иметь такой вид: 1. g4 e5 2. f3 Фh4x.

А за сколько ходов можно проиграть в тогызкумалаке? Если очень постараться, то игра может закончиться уже на 6-м ходу.

Мной была написана небольшая программа, которая показала, что число максимально коротких партий в тогызкумалаке равняется 1391. Три самые короткие партии начинаются с хода 1. 54, девять партий начинается с хода 1. 87, девятнадцать партий — с хода 1. 76 и львиная доля партий (1360 или 97,77%) начинается с хода 1. 98. Парадоксально, ведь ход 1. 98 считается в дебюте одним из неудачнейших, однако при неверной игре со стороны черных он таит массу ловушек.

Ниже приведены партии-миниатюры на каждый дебют:

1. 54 11
2. 32 55x
3. 89 35
4. 78 47
5. 67 51
6. 46

1. 76 11
2. 65 77x
3. 89 13
4. 44 78
5. 33 82
6. 82

1. 87 11
2. 65 67
3. 78 13
4. 44 12
5. 33 67
6. 22

1. 98 11
2. 87 24
3. 76 13
4. 33 25
5. 55 34
6. 94

Полный список самых коротких партий можно посмотреть здесь:
http://www.toguzkumalak.idhost.kz/games.txt

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Машина играет в тогызкумалак (дерево игры)

«Машина играет в шахматы» — так называется книга авторов «Каиссы» (советской шахматной программы), из которой можно почерпнуть много полезного.

Нынче никого не удивишь программами, которые играют в интеллектуальные игры. Программы «думают» (анализируют текущую позицию), делают ходы (принимают решения) и способны сыграть целую партию, как и человек. И если в игре го их успехи пока не особо впечатляют (в силу специфики игры, но это особая история, заслуживающая отдельного блога), то в шахматах и шашках лучшие программы уже превосходят сильнейших гроссмейстеров.

Согласно теории игр (есть такой подраздел в математике), тогызкумалак (как и шахматы, как и го) относится к играм с полной информацией. Основные принципы написания программ для таких игр сформулировал еще в середине прошлого века Клод Шеннон, создатель теории информации.

Если вкратце, то программа для выбора хода (принятия решения) строит дерево игры, где корень — это исходная позиция, ветви — это возможные ходы, а листья — это позиции, возникшие в результате сделанных ходов (на самом деле, программа строит не дерево, а граф, но это несущественно).

У непосвященного человека может возникнуть вопрос, а возможно ли таким образом просчитать тогызкумалак до конца и на основе сделанного расчета играть идеально и безошибочно?

После первого хода белых может возникнуть 9 позиций, после ответного хода черных — 73 позиции. Программисты измеряют продолжительность партии в полуходах, поэтому будем придерживаться этой традиции. После трех полуходов имеем 613 возможных позиций, после четырех полуходов — 5 199.

Дерево игры растет экспоненциально, но пока не выглядит слишком страшным. Однако что будет дальше? После пяти полуходов — 43 184, после шести — 360 035, после семи — 3 003 052 (больше трех миллионов), после восьми — 25 166 174, после девяти — 210 521 787, после десяти — 1 766 804 407 (счет пошел уже на миллиарды), после одиннадцати — 14 811 651 049.

Таким образом, после 11 полуходов (то есть только после шести ходов белых и пяти ходов черных) возникает 15 миллиардов позиций. Это 15 миллиардов возможных партий! Если бы население всего Казахстана (16 миллионов человек), забросив все свои дела, расставили доски и воспроизвели все возможные партии после 11 полуходов, затрачивая на партию по полторы минуты, то это заняло бы почти сутки. И это всего лишь дебют, самое начало партии!

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

По моему мнению, тогызкумалак — это идеальная игра из семейства манкала. Очень удачно выбрано число лунок — 9. Если их число делать меньше (6, как в калахе), то запустив программу на несколько лет, можно получить окончательный результат игры при оптимальной игре обеих сторон. В том случае, если увеличить количество лунок, то игра приобретает затяжной характер и может продолжаться чрезмерно долго. Кстати, по этой же причине шахматы остаются в своем классическом варианте (8 на 8), несмотря на многочисленные попытки модернизировать эту игру. Даже Капабланка в свое время предлагал добавить дополнительные фигуры и увеличить размер доски, но позже понял, что это заметно удлиняет партию и перестает делать шахматы столь интересными.

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Introduction

Приветствую всех!

Меня зовут Ернар Шамбаев.

С самого раннего детства меня увлекали логические и математические игры: шахматы, шашки, калах, отелло, го, а книга Якова Перельмана «Занимательная арифметика» была моей настольной книгой. В восьмом классе я перешел в математическую школу (гимназию), которая мне много дала. Оканчивая Павлодарский государственный университет, я узнал про казахскую национальную игру тогызкумалак и загорелся ею. Захотелось написать программу, которая бы играла в эту игру и побеждала человеческий разум. К тому времени у меня был не очень большой опыт написания приложений, поэтому программа получилась слабенькая, глубина перебора была небольшая, а оценочная функция примитивная.

Я оставил тогызкумалак на долгое время, появились другие проекты и задачи, но наверное, я чувствовал, что рано или поздно я вернусь к этой удивительной игре.