• 10679
  • 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
1206

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

Комментарии

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

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

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

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

Школа High Tech High – дети здесь самостоятельны так же, как и профессионалы в офисах

Школа High Tech High – дети здесь самостоятельны так же, как и профессионалы в офисах

Известный казахстанский бизнесмен становится первопроходцем и создает школу, о которой можно только мечтать. То, что мы, как взрослые, делаем в бизнесе, дети будут делать в этой школе.
Zhumanova
24 апр. 2017 / 16:29
  • 20964
  • 5
Кому в Казахстане жить хорошо? Почему мы остаёмся в топ-5 стран мира по числу самоубийств

Кому в Казахстане жить хорошо? Почему мы остаёмся в топ-5 стран мира по числу самоубийств

Всё ли так хорошо у жителей Казахстана? Почему-то наша страна сохраняет твёрдые позиции в первых строчках мировых рейтингов по числу самоубийств.
openqazaqstan
24 апр. 2017 / 16:54
  • 3865
  • 20
«Казпочта» отжигает. Редкий шанс вспомнить агрессивные советские очереди

«Казпочта» отжигает. Редкий шанс вспомнить агрессивные советские очереди

Люди старшего и среднего поколений помнят шумные, недобрые, грубо ругающиеся очереди советских лет. Увидеть, как это было, можно теперь разве что в каком-нибудь фильме. Хотя не только.
openqazaqstan
26 апр. 2017 / 16:14
  • 2638
  • 30
Юный алматинец покорил Первый канал на шоу Максима Галкина

Юный алматинец покорил Первый канал на шоу Максима Галкина

Житель Алматы по имени Марк Усачев недавно оказался на телепрограмме "Лучше всех", с успехом идущей на Первом канале России. 9-летний алматинец покорил публику своими недюжинными знаниями.
Seattle
24 апр. 2017 / 16:59
  • 2205
  • 2
Инстаграм – это «рынок девушек» и он круче любой базы данных

Инстаграм – это «рынок девушек» и он круче любой базы данных

Для меня Инстаграм – это рынок. Почему? Ничего не изменилось, девушки все так же бьются в попытках наиболее выгодно себя продать, посредством привлечения внимания.
Annette_Scherer
24 апр. 2017 / 22:35
  • 2116
  • 5
Президент велел делиться. Почему бы казахстанским миллиардерам не послушаться?

Президент велел делиться. Почему бы казахстанским миллиардерам не послушаться?

Президент Назарбаев призвал крупных бизнесменов делиться с народом, следуя примеру своих коллег из развитых стран. В Казахстане, действительно, сегодня много богатых людей.
openqazaqstan
вчера / 14:09
  • 1957
  • 25
Преподаватели и ЭКСПО: «Пока газеты пишут одно, нас заставляют покупать билеты на выставку»

Преподаватели и ЭКСПО: «Пока газеты пишут одно, нас заставляют покупать билеты на выставку»

Чтобы вы знали, чем занимаются в сфере образования - педагоги являются основой массовок. Какое отношение к учителям со стороны государства, такого же уровня и качество образования.
SaukovV
26 апр. 2017 / 16:05
  • 1990
  • 15
Жуткие истории о рабстве – такие вещи творятся в стране, принимающей «ЭКСПО»

Жуткие истории о рабстве – такие вещи творятся в стране, принимающей «ЭКСПО»

Мы живём, возможно, уже совсем в другом обществе, а не в том, к которому привыкли. Не первый год Казахстан периодически потрясают жуткие истории о рабстве.
openqazaqstan
26 апр. 2017 / 9:39
  • 1864
  • 19
15 фильмов, которые можно пересматривать бесконечно по версии проекта Popcorn

15 фильмов, которые можно пересматривать бесконечно по версии проекта Popcorn

Команда проекта Popcorn решила вспомнить и поделиться рядом картин, которые можно смотреть хоть до бесконечности, не теряя к ним интереса!
Seattle
вчера / 15:05
  • 1766
  • 47