• 11357
  • 6
  • 3
Нравится блог?
Подписывайтесь!

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

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

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

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

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

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

После первого хода белых может возникнуть 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), несмотря на многочисленные попытки модернизировать эту игру. Даже Капабланка в свое время предлагал добавить дополнительные фигуры и увеличить размер доски, но позже понял, что это заметно удлиняет партию и перестает делать шахматы столь интересными.

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

Ернар Шамбаев Yernartogyz
Win or lose, sink or swim, One thing is certain we`ll never give in!
28 октября 2011, 22:06
1263

Загрузка...
Loading...

Комментарии

Оставьте свой комментарий

Спасибо за открытие блога в Yvision.kz! Чтобы убедиться в отсутствии спама, все комментарии новых пользователей проходят премодерацию. Соблюдение правил нашей блог-платформы ускорит ваш переход в категорию надежных пользователей, не нуждающихся в премодерации. Обязательно прочтите наши правила по указанной ссылке: Правила

Также можно нажать Ctrl+Enter

Популярные посты

СМИ – ассистент провокаторов? Как гости из соседних стран сеют раздор в Казахстане

СМИ – ассистент провокаторов? Как гости из соседних стран сеют раздор в Казахстане

Инцидент с пьяным киргизским гостем на борту Air Astana, наверное, остался бы только во внутренних сводках авиакомпании, если бы г-н Доган, не поднял громкий крик о государственном языке.
openqazaqstan
17 авг. 2017 / 14:43
  • 12268
  • 178
Дайте Байбеку сломать и переделать город. Он хочет шагнуть вверх, а не бабло украсть

Дайте Байбеку сломать и переделать город. Он хочет шагнуть вверх, а не бабло украсть

Я в тогдашней Алма-Ате родился, вырос. В школу начал ходить пешком. Весь центр опползал. Все эти знаковые места помню как ещё не знаковые места. Никаких этих ностальгических страданий у меня нет.
Aidan_Karibzhanov
21 авг. 2017 / 16:25
  • 7496
  • 34
Подземная Акмечеть Бекет-Ата в Атырауской области – одно из самых сакральных мест

Подземная Акмечеть Бекет-Ата в Атырауской области – одно из самых сакральных мест

Его отцом был Мырзагул, матерью Жания, оба глубоко верующие. По рассказам, Бекет-Ата обладал богатырской силой, что в том числе помогало выбивать мечети в крепких скалах.
theYakov
21 авг. 2017 / 17:21
  • 3441
  • 3
Имеющий уши да услышит. Латиница касается только казахского языка

Имеющий уши да услышит. Латиница касается только казахского языка

Президент Назарбаев наконец-то разъяснил для всех, кто ещё не понял, очевидный вопрос, который всем в Казахстане очевиден. Елбасы повторил: на латиницу мы переводим казахский язык, и это не означает отказ от русского языка.
openqazaqstan
18 авг. 2017 / 16:23
  • 3576
  • 52
Байбек замахнулся на то, о чём давным-давно писали и говорили – «город для людей»

Байбек замахнулся на то, о чём давным-давно писали и говорили – «город для людей»

Какой «золотой квадрат»? Вам действительно это место кажется лучшим?! Вот когда Байбеку удастся воплотить в реальность скверы и парки, тогда я буду согласен называть старый центр золотым квадратом.
openqazaqstan
вчера / 16:53
  • 3183
  • 20
«Нас и здесь неплохо кормят», или почему я не собираюсь уезжать из Казахстана

«Нас и здесь неплохо кормят», или почему я не собираюсь уезжать из Казахстана

Я всегда теряюсь, когда слышу этот вопрос, потому что я так и не сумел выразить причину одной фразой. Давайте рассмотрим популярные варианты, и я объясню, что именно мне в них не нравится.
convoluted
21 авг. 2017 / 12:29
Надо научиться видеть скрытые экономические процессы за вспышкой национального гнева

Надо научиться видеть скрытые экономические процессы за вспышкой национального гнева

При полном отсутствии бюджетного жилищного строительства, целые аулы оседают в ветхих домишках, сквозь заборы которых насмешливо возвышаются башни "коктемов", "риц карлтонов" и "есентаев".
niyazov
19 авг. 2017 / 11:16
  • 2620
  • 68
Казахский язык выбирает алфавит, который считает необходимым. Дело не в латинице

Казахский язык выбирает алфавит, который считает необходимым. Дело не в латинице

У русскоязычных казахов два варианта, один - срочно отдавать детей в казахские школы, если видят их будущее в стране. Русскоязычным неказахам ещё меньше выбора. Надо становиться казахами.
Aidan_Karibzhanov
22 авг. 2017 / 18:08
  • 2463
  • 60
В Кокшетау строят два парка для молодёжи. Будут учтены интересы и любителей спорта

В Кокшетау строят два парка для молодёжи. Будут учтены интересы и любителей спорта

Общая площадь парка составляет 25 гектаров. На территории предусмотрено устройство прогулочных дорожек, площадок для установки аттракционов и павильонов различного назначения, цветников.
zhasakmola
17 авг. 2017 / 17:13
  • 2221
  • 1