Сколько зерен на шахматной доске в штуках
Перейти к содержимому

Сколько зерен на шахматной доске в штуках

  • автор:

Сколько будет зёрен на шахматной доске, если класть на каждую следующую клетку вдвое больше штук, начиная с 1?

Задача о зёрнах на шахматной доске — математическая задача, в которой вычисляется, сколько будет зёрен на шахматной доске, если класть на каждую следующую клетку доски вдвое больше зёрен, чем на предыдущую, начиная с одного.

Как правило, задача решается для стандартной 64-клеточной доски; при удвоении количества зёрен на каждой последующей клетке сумма зёрен на всех 64 клетках составляет 18 446 744 073 709 551 615.

Задача и её вариации используются для демонстрации высокой скорости роста экспоненциальных последовательностей.

Согласно одной из легенд, мудрец по имени Сисса показал своё изобретение правителю страны, тому так понравилась игра, что он дал изобретателю право самому выбрать награду. Мудрец попросил у короля за первую клетку шахматной доски заплатить ему 1 зерно пшеницы, за вторую — 2, за третью — 4 и так далее, удваивая количество зёрен на каждой следующей клетке. Правитель, не разбиравшийся в математике, быстро согласился, даже несколько обидевшись на столь невысокую оценку изобретения, и приказал казначею подсчитать и выдать изобретателю нужное количество зерна. Однако, когда неделю спустя казначей всё ещё не смог подсчитать, сколько нужно зёрен, правитель спросил, в чём причина такой задержки. Казначей показал ему расчёты и сказал, что расплатиться невозможно, разве только осушить моря и океаны и засеять всё пространство пшеницей. Общая масса пшеницы на шахматной доске составила 1200 миллиардов тонн или 1,2 триллиона тонн.

Подсчитали ли в настоящее время количесвто зерен из древней легенды?

Объявил индийский царь, что если кто-то выиграет у него в шахматы, того он вознаградит. Пришел крестьянин и поставил условие, что на первой клеточке будет пшеничное зернышко, на второй два зернышка, на третьей 4 и так дальше в математической прогрессии. Сколько получается зерен на 64 клеточке и сколько это в тоннах?

Дополнен 16 лет назад
Эльдар, а написать произношение данного чилса можешь?
Лучший ответ

Решение. Последовательность чисел, которая показывает, сколько зёрен должен был заплатить царь за каждую из 64 клеток шахматной доски, является геометрической прогрессией с первым членом b1=1 и знаменателем q=2. Чтобы найти количество зёрен, нам надо найти сумму

Воспользуемся формулой (4) и получим

Это очень большое число. Если его посчитать, то получится 18446744073709551615 (восемнадцать квинтиллионов четыреста сорок шесть квадриллионов семьсот сорок четыре триллиона семьдесят три миллиарда семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот пятнадцать !) К сожалению, при вычислении такого числа нельзя воспользоваться ни микрокалькулятором, ни персональным компьютером, так как это число содержит 20 цифр, а МК, например, даёт только восемь первых точных цифр, ПК — шестнадцать.
на всей Земле не хватило зерна , чтобы расплатиться за изобретение шахмат

Остальные ответы

Элементарная камбинаторика
64!=1,2688693218588416410343338933516e+89 — всего зерен на доске
А на последней клеточке
64!-63! — 1,249043238704797240393172426268e+89

ЗЫ Нет! одна целая двести сорок девять тысячных умноженная на десять в восемьдесят девятой степени!

Геометрическая прогрессия 2 в 64 степени, посчитать легко вес, если знать средний вес одного зернышка! Там примерно получется несколько десятков миллионов тонн

Ничего подобного, на компьютере это число рассчитать можно: есть специальные математические программы, в которых отсутствует ограничение на число цифр, например, Maple.

Всего на шахматной доске получается зерен 2^64-1, вроде Николай Ионкин правильно посчитал. На последней клеточке будет 2^63 зёрен, то есть 9223372036854775808 штук. Если зёрнышко весит 1 грамм, то это 9 триллионов тонн.

Сколько зёрен поместится на шахматной доске? ⁠ ⁠

По легенде один мудрец принёс арабскому правителю новую игру, шахматы. Игра очень понравилась правителю. Тот спросил: сколько ты хочешь за неё, назови любую вещь.
Мудрец сказал, я хочу столько зёрен, сколько получится, если на первую клеточку положить одно зерно, на вторую два, на третью в два раза больше и так до конца доски.
Правитель удивился, что мудрец просит так мало. Но тот настаивал.
Правитель дал приказ своим казначеям посчитать сколько зёрен надо отсыпать мудрецу. Но вскоре казначеи сказали, что столько зёрен нет во всём царстве.
А мудрец заявил, что игра бесценна и правителю нечем за неё заплатить.
С детства я хотел посчитать, сколько же зёрен там должно было быть.
Но всё сбивался на 25 клетке. А теперь в Экселе я посчитал за минуту.
Выходит 18 446 744 073 709 600 000 зёрен. Что при весе пшеничного зёрнышка 0,065 грамм даёт 1 199 038 364 791 тонн зерна.
Всего же в мире производится 2,287 миллиарда тонн зерна в год. Всех зерновых культур. То есть, весь мир смог бы расплатиться за шахматы за 524 года. При условии, что он (мир) ничего бы не ел.

Ну, и для зануд сколько именно будет зёрен на каждой клетке:
1
2
4
8
16
32
64
128
256
512
1 024
2 048
4 096
8 192
16 384
32 768
65 536
131 072
262 144
524 288
1 048 576
2 097 152
4 194 304
8 388 608
16 777 216
33 554 432
67 108 864
134 217 728
268 435 456
536 870 912
1 073 741 824
2 147 483 648
4 294 967 296
8 589 934 592
17 179 869 184
34 359 738 368
68 719 476 736
137 438 953 472
274 877 906 944
549 755 813 888
1 099 511 627 776
2 199 023 255 552
4 398 046 511 104
8 796 093 022 208
17 592 186 044 416
35 184 372 088 832
70 368 744 177 664
140 737 488 355 328
281 474 976 710 656
562 949 953 421 312
1 125 899 906 842 620
2 251 799 813 685 250
4 503 599 627 370 500
9 007 199 254 740 990
18 014 398 509 482 000
36 028 797 018 964 000
72 057 594 037 927 900
144 115 188 075 856 000
288 230 376 151 712 000
576 460 752 303 423 000
1 152 921 504 606 850 000
2 305 843 009 213 690 000
4 611 686 018 427 390 000
9 223 372 036 854 780 000

1 год назад
Нужно было дать задание мудрецу самому посчитать эти зерна и забрать необходимое количество.
раскрыть ветку
1 год назад

— Закрыть гештальт!
— Но в расчетах не точность!
— Открыть гештальт!

— В коментах все пересчитали правильно!
— Закрыть гештальт!

раскрыть ветку
1 год назад

даёт 1 199 038 364 791 тонн зерна.
Всего же в мире производится 2,287 миллиарда тонн зерна в год.
Блять, кто вот тебя так учил размерности писать? Почему не указать в одинаковых числах?
1199038364791 это сколько миллиардов? Как вот это на глаз перевести. Но а про ошибки в математике уже написали

раскрыть ветку
1 год назад

> А мудрец заявил, что игра бесценна и правителю нечем за неё заплатить

Да вообще как нефиг делать.

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

раскрыть ветку
1 год назад

Вы всё зерна считаете как те казначеи, а арабский правитель забрал бы шахматы, шибко умному мудрецу снес бы голову и посадил на кол за такую наглость.

раскрыть ветку
Похожие посты
1 год назад

Крестики-нолики, шашки и шахматы: немного об играх в математике⁠ ⁠

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Вы вечно проигрываете в крестики-нолики? Устали от бесконечных издевок окружающих? Чувствуете себя неполноценным членом общества? Тогда вы обратились по адресу! Сегодня у вас есть уникальная возможность пройти наш обучающий курс по беспроигрышной стратегии, который стартует уже сегодня! Присоединяйтесь сейчас и получите скидку 10% по промокоду НЕУДАЧНОЕ_ВСТУПЛЕНИЕ!

❯ 1. Беспроигрышная стратегия в крестики-нолики (или как впасть в состояние «ничейной смерти»)

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

Итак, как не проигрывать, если вы ходите первыми (напомню, что в нашем консервативном мире крестики доминируют).

1 ход: всегда в центр;
2 ход: в угол, который дальше всего от предыдущего хода ноликов;
3 ход: защита от попыток нолика чет выстроить или, что вероятнее, – снова ход в угол;
4 ход: тут у вас в наличии либо уже имеются две выигрышные линии, и вы гасите его, либо нолик прикрыл тылы, и исход – ничья.

Если вы играете за нолики, то при «идеальном» сопернике (который ходит всегда верно) у вас есть лишь возможность обороняться и выйти вничью, например:

1 ход: в любой угол;
2 ход: а дальше только пытаться помешать крестикам замутить тройничок, ведь больше вы ни на что не способны в силу своей submissive сущности.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Автор потерял нужную картинку из инета, не судите строго

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

Смотрите, корень нашего дерева – пустое поле 3х3. Первый игрок имеет возможность сделать ход на одну из девяти позиций – рисуем дереву девять веток с разными позициями крестиков (там внизу есть картинка). На следующем ходе у каждой ветки с крестиком есть восемь свободных мест для ноликов, то есть каждой ветке рисуем по восемь новых, где в различных комбинациях на поле две клетки заняты крестиком и ноликом. Итого имеем 9х8 – 72 ветки. Следуя такой логике, на дальнейшем шаге у дерева появится по 7 ответвлений, так как свободно только 7 клеток для крестика, количество теперь веток стало 9х8х7=504. Конечное число решений – листиков нашего дерева – равно 9! (все же знают, что это не девять с восклицанием, а факториал? – 9х8х7х6х5х4х3х2х1) или 362880. Теперь достаточно вбить компьютеру все эти исходы и запрограммировать выбирать только выигрышные.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Первые ветви дерева решений

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

Ну вот, дерево подстригли, причесали – теперь полное количество его узлов сократилось до 256158, и программа всегда будет выигрывать или заканчивать партию вничью за секунды.

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

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

Вот, например, с шашками дела обстоят интереснее: кроме большого поля у них и правила на порядок сложнее, так что при подсчетах оказывается, что листьев у дерева решений около 5х10^20. Это пять и рядом двадцать нулей. Думаете, это мало? Оно и понятно, у нас мозг просто не способен представить число такого порядка, но для сравнения: чтобы выстроить цепочку от Земли до Марса из бусинок размером с атом потребуется как раз 5,5х10^20 бусинок. Очевидно, что число это офигеть какое большое, и пятидесяти компьютерам не просто так потребовалось почти 20 лет (двадцать лет, Карл!), чтобы полностью рассчитать все возможные исходы шашек и выстроить их дерево решений.

Сие знаменательное событие произошло в 2007 году благодаря команде канадских исследователей во главе с Джонатаном Шеффером, и с этого момента шашки официально вошли в список полностью решенных игр. Если оба соперника не совершают ошибок, то партия всегда заканчивается ничьей. Тут нужно учесть, что речь идет об английских шашках – чекерс; в них назад бьет только дамка.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Статья Шеффера и его коллег в журнале Science

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

Сейчас на меня наверняка налетят шахматные снобы, утверждающие, что приличные люди вообще не играют в шашки. И действительно, а как обстоят дела у шахмат?

❯ 2. Компьютеры, которые играют в игры

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

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

Итак, по сравнению с великими и ужасными шахматами, шашки (а тем более, крестики-нолики) покажутся развлечением для малышей. Напомню, что для английских шашек количество различных вариантов партий равняется 5х10^20, и полностью просчитать их смогли только спустя 18 лет после начала работы программы.

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

Напрашивается очевидный вопрос: раз шашки рассчитали, то и шахматы сможем, разве нет? Ждали же 18 лет, подождем и еще. Всё равно простым смертным нет дела до этих математических извращений, и в каком-нибудь 2040 году, листая ленту девятым кибер-пальцем, мы смахнем новость про найденное решение для шахмат.

К сожалению, пока что это утопия. И дело не в том, что математики поняли, что страдают какой-то фигней, проблема заключается в сложности самой игры: одних только позиций фигур на доске существует около 10^46, а уникальных партий – не меньше 10^120.

Десять в сто двадцатой степени. Это много. Так много, что у нас даже нет аналогии, чтобы показать весь ужас этого гигантского числа, его попросту не существует в физическом мире. Чтобы вы понимали, количество атомов в известной нам части Вселенной примерно равно 10^80, а количество оригинальных партий в шахматах больше этой цифры в 10^40 раз. Причем в начале игры все выглядит довольно безобидно: у белых есть всего двадцать ходов – 16 пешками и четыре конями — но с каждым сделанным шагом количество возможных комбинаций на доске очень быстро растет. Так, например, после первого хода каждого из соперников, на поле существует 400 различных позиций для следующего шага, после второго – 72084, после третьего – больше 9 миллионов, после четвертого – более 288 миллиардов. Такое число соразмерно с количеством звезд в нашей галактике, а ведь это всего лишь самое начало партии.

Однако не просто так было сказано, что теория игр без шахмат – как самолёт без двигателя. После окончания Второй мировой еще на заре эпохи машинных вычислений шахматы стали своеобразным эталоном для проверки различных идей в этой области. Клод Шеннон *кстати, именно в честь него число 10^120 называется числом Шеннона*, один из основателей раздела об искусственном интеллекте, говорил, что не видит практической ценности в вычислении всех возможных шахматных партий, но сама эта мысль побуждает исследователей двигаться вперед и развивать технологии до тех пор, пока они не найдут решение.

Первую программу для игры в шахматы написал еще в 1952 году Дитрих Принц (коллега Алана Тьюринга) на компьютере Ferranti Mark. Правда, тут не стоит обольщаться, этот компьютер, лишь отдалённо напоминающий наши современные устройства, был таким слабеньким, что объем его оперативной памяти мог содержать программу только по типу «мат в два хода». Она была рассчитана лишь для последних двух ходов, но начало шахматной эпопеи было положено.

В 1956 году компьютер MANIAC-1 *милое название* сыграл три партии в облегченные шахматы (на поле 6х6 и без слонов) – сам с собой, против сильного игрока и против новичка. Несмотря на то, что опытный шахматист в начале игры решил отказаться от ферзя, программа все равно ему проиграла *какой неумелый маньяк*, но вот последнего – слабого соперника компьютер смог победить. Это была первая победа машины над человеком.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Название MANIAC, кстати, — это аббревиатура: Mathematical Analyzer Numerical Integrator and Automatic Computer. «… Компания Metropolis выбрала имя MANIAC в надежде остановить поток глупых аббревиатур для названий машин»

После изобретения в 1971 году первого микропроцессора, у ученых появилась возможность задействовать более мощные компьютеры, а значит, сохранять в памяти машины еще больше победных комбинаций. В 1974 году был организован первый чемпионат по шахматам среди программ, в 1978 году машина обыграла международного мастера по шахматам, а в 1981-м Cray Blitz стал первым компьютером, получившим рейтинг мастера.

Но несмотря на то, что с появления первого компьютера, играющего в шахматы, прошло уже много времени, алгоритм программы оставался на уровне решения крестиков-ноликов: легендарный суперкомпьютер Deep Blue от компании IBM использовал типовой метод поиска по шахматному дереву— минимаксный алгоритм с альфа-бета-отсечениями. Преимущество того или иного компьютера заключалось лишь в мощности процессора и количестве загруженных в него победных ходов живых шахматистов.

Кстати, легендарным Deep Blue стал 11 мая 1997 года, когда выиграл матч из шести партий у чемпиона мира Гарри Каспарова. Интересно, что за восемь лет до этого в Нью-Йорке Каспаров победил более слабого предшественника Deep Blue под названием Deep Thought. Тогда он высказал такую мысль: «Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу». Что ж, ему явно пришлось пересмотреть свои взгляды.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Матч 1997 года, который стал предметом документального фильма «Человек против машины»

Окончательно и бесповоротно человечество проиграло железякам в 2005-м: в этот год представитель нашей расы в последний раз смог одержать верх над программой. Сегодня рейтинг живых шахматистов настолько отстал от их железных соперников, что человеку больше никогда не выиграть партию с машиной. На начало сентября 2022 года наивысший шахматный рейтинг человека составляет 2861, а программы 3535.

Чувствуете, как повеяло киберпанком? Но несмотря на такие потрясающие успехи компьютеров, сама игра так и остается нерешенной: нам неизвестно, как закончилась бы идеально просчитанная партия, где обе программы знают последствия каждого хода вплоть до конца игры. Ученые лишь предполагают (но до сих пор не могут доказать), что белые обладают преимуществом первого хода, так как в идеальной игре черные могут только реагировать на создаваемые ими угрозы. Некоторую надежду в этой области вселяет активное развитие квантовых компьютеров, которые могут вести поиск одновременно по нескольким ветвям дерева решений, но тем не менее какого-то революционного алгоритма для самого поиска мы не имеем, и идеальной стратегии для чайников не существует.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

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

❯ 3. Go play Go (Последний бой людей)

Оказалось – человек так отстал от своих железных собратьев, что больше никогда не сможет одержать над ними верх. Но что, если бы существовала игра, где люди могли бы проявлять свои сильные стороны, не присущие машинам? Где победа зависит не только от строгих логических расчетов, но и от силы воображения и хитрости?

Как вы уже поняли, такая игра есть: мы наконец-то добрались до го. Го – китайская стратегия – является самой древней настольной игрой, сохраняющей свои правила практически неизменными вот уже 2500 лет. До ХХ века игра была распространена только в Азии, но на сегодняшний день она входит в пять дисциплин Всемирных интеллектуальных игр и является самой распространенной настолкой по числу участников (c поправочкой на плотность населения Востока).

В Китае го образно называют «разговором рук» *italian_moment*, что подчеркивает особое отношение к игре как к искусству. Это неудивительно, ведь ее правила невероятно сложны, так что напоминают не соревнование, а своеобразный диалог, и у разных мастеров есть даже свои собственные стили, по которым их узнают – как стиль писателя или манера художника.

Чтобы сыграть в классическую версию го вам понадобятся: доска в клетку 19х19 (называется гобан) – 1 шт, белые игральные камни – 180 шт., черные игральные камни – 181 шт., кошка-жена – 1 шт. (если есть больше, поделитесь?). Цель игры — отгородить на доске камнями своего цвета бо́льшую территорию, чем противник. Как видно, здесь нет черных и белых клеток на поле, камни можно ставить на любые пересечения линий, нет и разграничения игральных фигур – все они равноценны друг другу. Собственно, именно эта простота и порождает дьявольски сложные тактику и стратегию.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Напомню, тактика – локальное противоборство в какой-то части поля. Стратегия – общее положение сил в игре. Если в шахматах вы лишились дорогой фигуры, ваши шансы на победу обычно заметно уменьшаются, то есть тактика очень сильно влияет на стратегию. В го и поле больше, и фишек огромное количество – поэтому хитрости и поддавки здесь вполне могут стать более близким путем к победе, чем прямая и открытая политика завоевания.

Обычный метод перебора, которым пользуются компьютеры для выбора выигрышной стратегии в шахматах, здесь просто не уместен. Во-первых, дерево решений го необычайно огромно – на начальной позиции существует 55 вариантов ходов (в шахматах – 20), и «растет» оно быстрее – после первых двух ходов соперников существует уже около 16 миллиардов позиций для следующего (в шахматах – меньше ста тысяч). А во-вторых, го – игра, в которой очень важен опыт.

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

Но вот настал 2016 год и программа AlphaGo, разработанная корпорацией Google, в прямом эфире победила мирового мастера с девятым даном – Ли Седоля. Это стало возможно благодаря новому подходу обучения, который кардинально отличается от обучения шахматных компьютеров. Помните, что Deep Blue использовал обычный метод перебора дерева решений просто с кучей оптимизаций и на самом деле кроме мощных процессоров и больших объемов памяти он недалеко ушел от железяк 60-х.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

AlphaGo – революционная программа, в ней нет базы данных с удачными ходами чемпионов или оценочного алгоритма, лишь самые базовые правила, которым учат новичков. Всему остальному она научилась сама, проигрывая тысячи партий с собой. В основе компьютера лежит нейронная сеть, моделирующая работу органического мозга. Главное новшество AlphaGo заключается в использовании глубинного обучения — метода, успешно применявшегося для распознавания образов (например, для поиска картинок в Google Images). Но как ни парадоксально именно из-за этого разработчики не знают, каким конкретным образом программа оценивает ситуацию в игре: система настолько сложна, что анализировать все уровни обработки информации в целом не представляется возможным.

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

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

Сколько будет зерён на шахматной доске, если класть на каждую следующую клетку вдвое больше штук, начиная с 1? ⁠ ⁠

Хотя детали описания задачи в разных источниках отличаются, суть остаётся неизменной. Согласно одной из легенд, дравид велалар по имени Сисса показал своё изобретение правителю страны, тому так понравилась игра, что он дал изобретателю право самому выбрать награду. Мудрец попросил у короля за первую клетку шахматной доски заплатить ему одно зерно пшеницы, за вторую — два, за третью — четыре и так далее, удваивая количество зёрен на каждой следующей клетке. Правитель, не разбиравшийся в математике, быстро согласился, даже несколько обидевшись на столь невысокую оценку изобретения, и приказал казначею подсчитать и выдать изобретателю нужное количество зерна. Однако, когда неделю спустя казначей всё ещё не смог подсчитать, сколько нужно зёрен, правитель спросил, в чём причина такой задержки. Казначей показал ему расчёты и сказал, что расплатиться невозможно, разве только осушить моря и океаны и засеять всё пространство пшеницей.

Количество зерна примерно в 1800 раз превышает мировой урожай пшеницы за год (в 2008/09 аграрном году урожай составил 686 млн тонн, то есть превышает весь урожай пшеницы, собранный за всю историю человечества. Количество зёрен составляет примерно 0,0031 % числа Авогадро. В единицах массы: если принять, что одно зёрнышко пшеницы имеет массу 0,065 грамма (Troy grain тройское зерно: 1 gr = 0,06479891 гран), тогда общая масса пшеницы на шахматной доске составит 1200 миллиардов тонн или 1,2 триллиона тонн:

Сколько будет зерён на шахматной доске, если класть на каждую следующую клетку вдвое больше штук, начиная с 1? Шахматы, Пшеница, Зерна, Математика, Мудрость, Википедия, Занимательная арифметика

Как правило, задача решается для стандартной 64-клеточной доски; при удвоении количества зёрен на каждой последующей клетке сумма зёрен на всех 64 клетках определяется выражением:

Сколько будет зерён на шахматной доске, если класть на каждую следующую клетку вдвое больше штук, начиная с 1? Шахматы, Пшеница, Зерна, Математика, Мудрость, Википедия, Занимательная арифметика

что составляет 18 446 744 073 709 551 615.

Задача и её вариации используются для демонстрации высокой скорости роста экспоненциальных последовательностей.

3 года назад
Сумма зёрен 2 в 64й степени минус один. Что в последней строчке поста, я не понял
раскрыть ветку
3 года назад

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

раскрыть ветку
3 года назад

Копипаста из методички или книги, да ещё кривая.

3 года назад

Вот вы когда посты делаете. Вы хотя бы смотрите, что сделали? Тебе нормально, что из двух картинок обрезались обе? И ты все равно запостил?

Похожие посты
8 месяцев назад

Основная теорема арифметики – Алексей Савватеев | Лекции по математике | Научпоп⁠ ⁠

В чём заключается основная теорема арифметики и почему она так «громко» называется? Как она может быть доказана и какие интересные следствия из неё выводятся? Как она связана с простыми числами и методами шифрования?

Об этом в лекции по математике рассказывает Алексей Савватеев, математик и матэкономист, доктор физико-математических наук, член-корреспондент РАН, популяризатор математики среди детей и взрослых, научный руководитель Кавказского Математического Центра АГУ, профессор Московского физико-технического института, ведущий научный сотрудник ЦЭМИ РАН.

Показать полностью
1 год назад

Сколько зёрен поместится на шахматной доске?⁠ ⁠

По легенде один мудрец принёс арабскому правителю новую игру, шахматы. Игра очень понравилась правителю. Тот спросил: сколько ты хочешь за неё, назови любую вещь.
Мудрец сказал, я хочу столько зёрен, сколько получится, если на первую клеточку положить одно зерно, на вторую два, на третью в два раза больше и так до конца доски.
Правитель удивился, что мудрец просит так мало. Но тот настаивал.
Правитель дал приказ своим казначеям посчитать сколько зёрен надо отсыпать мудрецу. Но вскоре казначеи сказали, что столько зёрен нет во всём царстве.
А мудрец заявил, что игра бесценна и правителю нечем за неё заплатить.
С детства я хотел посчитать, сколько же зёрен там должно было быть.
Но всё сбивался на 25 клетке. А теперь в Экселе я посчитал за минуту.
Выходит 18 446 744 073 709 600 000 зёрен. Что при весе пшеничного зёрнышка 0,065 грамм даёт 1 199 038 364 791 тонн зерна.
Всего же в мире производится 2,287 миллиарда тонн зерна в год. Всех зерновых культур. То есть, весь мир смог бы расплатиться за шахматы за 524 года. При условии, что он (мир) ничего бы не ел.

Ну, и для зануд сколько именно будет зёрен на каждой клетке:
1
2
4
8
16
32
64
128
256
512
1 024
2 048
4 096
8 192
16 384
32 768
65 536
131 072
262 144
524 288
1 048 576
2 097 152
4 194 304
8 388 608
16 777 216
33 554 432
67 108 864
134 217 728
268 435 456
536 870 912
1 073 741 824
2 147 483 648
4 294 967 296
8 589 934 592
17 179 869 184
34 359 738 368
68 719 476 736
137 438 953 472
274 877 906 944
549 755 813 888
1 099 511 627 776
2 199 023 255 552
4 398 046 511 104
8 796 093 022 208
17 592 186 044 416
35 184 372 088 832
70 368 744 177 664
140 737 488 355 328
281 474 976 710 656
562 949 953 421 312
1 125 899 906 842 620
2 251 799 813 685 250
4 503 599 627 370 500
9 007 199 254 740 990
18 014 398 509 482 000
36 028 797 018 964 000
72 057 594 037 927 900
144 115 188 075 856 000
288 230 376 151 712 000
576 460 752 303 423 000
1 152 921 504 606 850 000
2 305 843 009 213 690 000
4 611 686 018 427 390 000
9 223 372 036 854 780 000

Показать полностью
1 год назад

Сеанс одновременной игры с гроссмейстером Зайцевым⁠ ⁠

Случилось то замечательное событие, когда наша семья переехала из коммунальной квартиры в рабочее общежитие. Плюсов было огромное количество. Во-первых, это была отдельная П-образная комната и после того, как отец повесил от серванта до стены гардину с занавеской, у нас с братом появилась пусть маленькая, но отдельная комната. Во-вторых, был огромный двор с качелями, каруселями, футбольным полем, в шаговой доступности детский сад и школа, но самое главное — это шахматный клуб “Молодежный”. Два рабочих общежития (для семейных и несемейных) были соединены между собой проходом и зданием, в котором располагались: кафе-столовая, библиотека, зал со столом для настольного тенниса, и, конечно, шахматный клуб. На выходе из несемейного общежития всегда сидела строгая вахтерша и блюла пропускной режим.

Изначально, я посещал шахматную школу во дворце пионеров в здании бывшей средней школы №1, это было далеко от общежития и было неудобно добираться. Отец на работе в ИВЦ познакомился с инженером-электронщиком Виктором Владимировичем, который был КМС по шахматам и тренировал ребят в “Молодежном”. У меня получилось проявить себя во дворце пионеров, плюс- просьба отца, и нас с братом взяли в секцию, которая считалась лучшей в нашем районе.

Это была не просто секция- настоящий шахматный клуб. Завсегдатаями клуба были мужики- шахматисты (в основном, работники ПО ВМУ), которые 2–3 раза в неделю устраивали шахматные баталии, и, даже пытались играть на деньги, но строгий заведующий дядя Саша, который выдавал фигуры и был человеком очень принципиальным, организованным и любящим всем порядок (говорили, что он до пенсии он занимал высокую руководящую должность), пресекал все коммерческие начинания на корню.

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

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

Сеанс одновременной игры проходил на 30 досках, и в нем приняли участие все наши ребята из секции, тренер, часть мужиков, заведующий клубом и ваш покорный слуга, бывший в то время 12 лет от роду. Это был классический сеанс игры до поражения, времени было более чем достаточно, и моя испанская партия перешла в фазу красивого эндшпиля с равенством фигур. Максимум, о чем я мог мечтать — это проиграть в ранге последних, ничья — это было недосягаемо, не говоря уже о победе. И то, что случилось- случилось. Более половины участников досрочно сдались, и я увидел на доске, что Зайцев отдает коня, фигура не защищена. Я погрузился в просчёт возможных комбинаций, которые приведут к моему поражению и после 40 минут раздумий взял коня. Оказывается, и гроссмейстеры не железные и они зевают. Зайцев, обойдя круг, подошел к нашей с ним партии, сняв очки, посмотрел на меня, и, не дожидаясь реплик и вопрос, сдался, как настоящий мастер- изящно и прямо, протянув мне руку и пожелав успехов в дальнейшем. На память он оставил свою запись на бланке, где я регистрировал ходы. Что творилось со мной — сложной описать, я был на седьмом небе, мужики столпились вокруг и один за другим предлагали сыграть, но у мня не было ни моральных ни физических сил. Кстати, мой тренер, Виктор Владимирович, добился ничьи, а все остальные игроки проиграли.

В жизни каждого человека бывают моменты, которые запоминаются навсегда. В моей жизни победа над гроссмейстером Зайцевым- тренером Карпова- один из них. Главное- сделать правильный вывод, ведь именно тогда я понял, что нет абсолютных и незыблемых людей, даже чемпионы проигрывают. Если ты чего-то хочешь- одного большого желания мало, надо трудиться, выкладываться на все 200%. Это то, о чем нам- молодым ребятам-шахматистам говорил Виктор Владимирович, ведь жизнь — это тоже игра, только просчитать ее подчас почти невозможно, однако, те яркие моменты и люди, ради которых потрачены годы работы, стоят того, чтобы жить.

Показать полностью
Поддержать
1 год назад

Любопытная история⁠ ⁠

Одним из самых знаменитых азиатских шахматистов в истории является филиппинский гроссмейстер Эугенио Торре.

Он побеждал в нескольких крупных международных соревнованиях, а однажды, на турнире в Маниле в 1976 году, выиграл у чемпиона мира Анатолия Карпова и тем самым пополнил собой ряды членов символического шахматного клуба Михаила Чигорина.

Также Эугенио Торре дружил с Робертом Фишером и помогал ему при подготовке к матчу 1992 года с Борисом Спасским в Югославии. Однако известен филиппинец Торре не только этим.

В международной шахматной среде Эугенио Торре знаменит тем, что является самым молчаливым и немногословным шахматистом. Этот удивительный молчун не только играет без звука, но ещё и категорически избегает общения с прессой.

Даже если кто-то из журналистов каким-то чудом и добивается встречи, то в ответ на свои вопросы получает исключительно односложные ответы: «да», «нет», «наверное».

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

Корреспонденту повезло – благодаря молодому напору и женскому обаянию ей удалось устроить интервью с филиппинцем.

Амбициозная и хитрая американка решила «взять быка за рога», «открыть карты» и поэтому начала беседу так: – Мистер Торре, не буду скрывать, что я поспорила со своими друзьями, что сумею вырвать у вас хоть один ответ, который будет содержать более двух слов. Прошу вас, произнесите хотя бы три слова!

Эугенио Торре внимательно выслушал наглую и напористую репортёршу и, после короткой паузы, ответил: – Вы проиграли.

Любопытная история Мысли, Шахматы, Игры, Спорт, История, Истории из жизни, Жизнь, Жизненно, Старость, Мудрость, Логика, Внутренний диалог, Философия

Показать полностью 1
1 год назад

Крестики-нолики, шашки и шахматы: немного об играх в математике⁠ ⁠

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Вы вечно проигрываете в крестики-нолики? Устали от бесконечных издевок окружающих? Чувствуете себя неполноценным членом общества? Тогда вы обратились по адресу! Сегодня у вас есть уникальная возможность пройти наш обучающий курс по беспроигрышной стратегии, который стартует уже сегодня! Присоединяйтесь сейчас и получите скидку 10% по промокоду НЕУДАЧНОЕ_ВСТУПЛЕНИЕ!

❯ 1. Беспроигрышная стратегия в крестики-нолики (или как впасть в состояние «ничейной смерти»)

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

Итак, как не проигрывать, если вы ходите первыми (напомню, что в нашем консервативном мире крестики доминируют).

1 ход: всегда в центр;
2 ход: в угол, который дальше всего от предыдущего хода ноликов;
3 ход: защита от попыток нолика чет выстроить или, что вероятнее, – снова ход в угол;
4 ход: тут у вас в наличии либо уже имеются две выигрышные линии, и вы гасите его, либо нолик прикрыл тылы, и исход – ничья.

Если вы играете за нолики, то при «идеальном» сопернике (который ходит всегда верно) у вас есть лишь возможность обороняться и выйти вничью, например:

1 ход: в любой угол;
2 ход: а дальше только пытаться помешать крестикам замутить тройничок, ведь больше вы ни на что не способны в силу своей submissive сущности.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Автор потерял нужную картинку из инета, не судите строго

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

Смотрите, корень нашего дерева – пустое поле 3х3. Первый игрок имеет возможность сделать ход на одну из девяти позиций – рисуем дереву девять веток с разными позициями крестиков (там внизу есть картинка). На следующем ходе у каждой ветки с крестиком есть восемь свободных мест для ноликов, то есть каждой ветке рисуем по восемь новых, где в различных комбинациях на поле две клетки заняты крестиком и ноликом. Итого имеем 9х8 – 72 ветки. Следуя такой логике, на дальнейшем шаге у дерева появится по 7 ответвлений, так как свободно только 7 клеток для крестика, количество теперь веток стало 9х8х7=504. Конечное число решений – листиков нашего дерева – равно 9! (все же знают, что это не девять с восклицанием, а факториал? – 9х8х7х6х5х4х3х2х1) или 362880. Теперь достаточно вбить компьютеру все эти исходы и запрограммировать выбирать только выигрышные.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Первые ветви дерева решений

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

Ну вот, дерево подстригли, причесали – теперь полное количество его узлов сократилось до 256158, и программа всегда будет выигрывать или заканчивать партию вничью за секунды.

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

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

Вот, например, с шашками дела обстоят интереснее: кроме большого поля у них и правила на порядок сложнее, так что при подсчетах оказывается, что листьев у дерева решений около 5х10^20. Это пять и рядом двадцать нулей. Думаете, это мало? Оно и понятно, у нас мозг просто не способен представить число такого порядка, но для сравнения: чтобы выстроить цепочку от Земли до Марса из бусинок размером с атом потребуется как раз 5,5х10^20 бусинок. Очевидно, что число это офигеть какое большое, и пятидесяти компьютерам не просто так потребовалось почти 20 лет (двадцать лет, Карл!), чтобы полностью рассчитать все возможные исходы шашек и выстроить их дерево решений.

Сие знаменательное событие произошло в 2007 году благодаря команде канадских исследователей во главе с Джонатаном Шеффером, и с этого момента шашки официально вошли в список полностью решенных игр. Если оба соперника не совершают ошибок, то партия всегда заканчивается ничьей. Тут нужно учесть, что речь идет об английских шашках – чекерс; в них назад бьет только дамка.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Статья Шеффера и его коллег в журнале Science

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

Сейчас на меня наверняка налетят шахматные снобы, утверждающие, что приличные люди вообще не играют в шашки. И действительно, а как обстоят дела у шахмат?

❯ 2. Компьютеры, которые играют в игры

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

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

Итак, по сравнению с великими и ужасными шахматами, шашки (а тем более, крестики-нолики) покажутся развлечением для малышей. Напомню, что для английских шашек количество различных вариантов партий равняется 5х10^20, и полностью просчитать их смогли только спустя 18 лет после начала работы программы.

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

Напрашивается очевидный вопрос: раз шашки рассчитали, то и шахматы сможем, разве нет? Ждали же 18 лет, подождем и еще. Всё равно простым смертным нет дела до этих математических извращений, и в каком-нибудь 2040 году, листая ленту девятым кибер-пальцем, мы смахнем новость про найденное решение для шахмат.

К сожалению, пока что это утопия. И дело не в том, что математики поняли, что страдают какой-то фигней, проблема заключается в сложности самой игры: одних только позиций фигур на доске существует около 10^46, а уникальных партий – не меньше 10^120.

Десять в сто двадцатой степени. Это много. Так много, что у нас даже нет аналогии, чтобы показать весь ужас этого гигантского числа, его попросту не существует в физическом мире. Чтобы вы понимали, количество атомов в известной нам части Вселенной примерно равно 10^80, а количество оригинальных партий в шахматах больше этой цифры в 10^40 раз. Причем в начале игры все выглядит довольно безобидно: у белых есть всего двадцать ходов – 16 пешками и четыре конями — но с каждым сделанным шагом количество возможных комбинаций на доске очень быстро растет. Так, например, после первого хода каждого из соперников, на поле существует 400 различных позиций для следующего шага, после второго – 72084, после третьего – больше 9 миллионов, после четвертого – более 288 миллиардов. Такое число соразмерно с количеством звезд в нашей галактике, а ведь это всего лишь самое начало партии.

Однако не просто так было сказано, что теория игр без шахмат – как самолёт без двигателя. После окончания Второй мировой еще на заре эпохи машинных вычислений шахматы стали своеобразным эталоном для проверки различных идей в этой области. Клод Шеннон *кстати, именно в честь него число 10^120 называется числом Шеннона*, один из основателей раздела об искусственном интеллекте, говорил, что не видит практической ценности в вычислении всех возможных шахматных партий, но сама эта мысль побуждает исследователей двигаться вперед и развивать технологии до тех пор, пока они не найдут решение.

Первую программу для игры в шахматы написал еще в 1952 году Дитрих Принц (коллега Алана Тьюринга) на компьютере Ferranti Mark. Правда, тут не стоит обольщаться, этот компьютер, лишь отдалённо напоминающий наши современные устройства, был таким слабеньким, что объем его оперативной памяти мог содержать программу только по типу «мат в два хода». Она была рассчитана лишь для последних двух ходов, но начало шахматной эпопеи было положено.

В 1956 году компьютер MANIAC-1 *милое название* сыграл три партии в облегченные шахматы (на поле 6х6 и без слонов) – сам с собой, против сильного игрока и против новичка. Несмотря на то, что опытный шахматист в начале игры решил отказаться от ферзя, программа все равно ему проиграла *какой неумелый маньяк*, но вот последнего – слабого соперника компьютер смог победить. Это была первая победа машины над человеком.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Название MANIAC, кстати, — это аббревиатура: Mathematical Analyzer Numerical Integrator and Automatic Computer. «… Компания Metropolis выбрала имя MANIAC в надежде остановить поток глупых аббревиатур для названий машин»

После изобретения в 1971 году первого микропроцессора, у ученых появилась возможность задействовать более мощные компьютеры, а значит, сохранять в памяти машины еще больше победных комбинаций. В 1974 году был организован первый чемпионат по шахматам среди программ, в 1978 году машина обыграла международного мастера по шахматам, а в 1981-м Cray Blitz стал первым компьютером, получившим рейтинг мастера.

Но несмотря на то, что с появления первого компьютера, играющего в шахматы, прошло уже много времени, алгоритм программы оставался на уровне решения крестиков-ноликов: легендарный суперкомпьютер Deep Blue от компании IBM использовал типовой метод поиска по шахматному дереву— минимаксный алгоритм с альфа-бета-отсечениями. Преимущество того или иного компьютера заключалось лишь в мощности процессора и количестве загруженных в него победных ходов живых шахматистов.

Кстати, легендарным Deep Blue стал 11 мая 1997 года, когда выиграл матч из шести партий у чемпиона мира Гарри Каспарова. Интересно, что за восемь лет до этого в Нью-Йорке Каспаров победил более слабого предшественника Deep Blue под названием Deep Thought. Тогда он высказал такую мысль: «Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу». Что ж, ему явно пришлось пересмотреть свои взгляды.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Матч 1997 года, который стал предметом документального фильма «Человек против машины»

Окончательно и бесповоротно человечество проиграло железякам в 2005-м: в этот год представитель нашей расы в последний раз смог одержать верх над программой. Сегодня рейтинг живых шахматистов настолько отстал от их железных соперников, что человеку больше никогда не выиграть партию с машиной. На начало сентября 2022 года наивысший шахматный рейтинг человека составляет 2861, а программы 3535.

Чувствуете, как повеяло киберпанком? Но несмотря на такие потрясающие успехи компьютеров, сама игра так и остается нерешенной: нам неизвестно, как закончилась бы идеально просчитанная партия, где обе программы знают последствия каждого хода вплоть до конца игры. Ученые лишь предполагают (но до сих пор не могут доказать), что белые обладают преимуществом первого хода, так как в идеальной игре черные могут только реагировать на создаваемые ими угрозы. Некоторую надежду в этой области вселяет активное развитие квантовых компьютеров, которые могут вести поиск одновременно по нескольким ветвям дерева решений, но тем не менее какого-то революционного алгоритма для самого поиска мы не имеем, и идеальной стратегии для чайников не существует.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

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

❯ 3. Go play Go (Последний бой людей)

Оказалось – человек так отстал от своих железных собратьев, что больше никогда не сможет одержать над ними верх. Но что, если бы существовала игра, где люди могли бы проявлять свои сильные стороны, не присущие машинам? Где победа зависит не только от строгих логических расчетов, но и от силы воображения и хитрости?

Как вы уже поняли, такая игра есть: мы наконец-то добрались до го. Го – китайская стратегия – является самой древней настольной игрой, сохраняющей свои правила практически неизменными вот уже 2500 лет. До ХХ века игра была распространена только в Азии, но на сегодняшний день она входит в пять дисциплин Всемирных интеллектуальных игр и является самой распространенной настолкой по числу участников (c поправочкой на плотность населения Востока).

В Китае го образно называют «разговором рук» *italian_moment*, что подчеркивает особое отношение к игре как к искусству. Это неудивительно, ведь ее правила невероятно сложны, так что напоминают не соревнование, а своеобразный диалог, и у разных мастеров есть даже свои собственные стили, по которым их узнают – как стиль писателя или манера художника.

Чтобы сыграть в классическую версию го вам понадобятся: доска в клетку 19х19 (называется гобан) – 1 шт, белые игральные камни – 180 шт., черные игральные камни – 181 шт., кошка-жена – 1 шт. (если есть больше, поделитесь?). Цель игры — отгородить на доске камнями своего цвета бо́льшую территорию, чем противник. Как видно, здесь нет черных и белых клеток на поле, камни можно ставить на любые пересечения линий, нет и разграничения игральных фигур – все они равноценны друг другу. Собственно, именно эта простота и порождает дьявольски сложные тактику и стратегию.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

Напомню, тактика – локальное противоборство в какой-то части поля. Стратегия – общее положение сил в игре. Если в шахматах вы лишились дорогой фигуры, ваши шансы на победу обычно заметно уменьшаются, то есть тактика очень сильно влияет на стратегию. В го и поле больше, и фишек огромное количество – поэтому хитрости и поддавки здесь вполне могут стать более близким путем к победе, чем прямая и открытая политика завоевания.

Обычный метод перебора, которым пользуются компьютеры для выбора выигрышной стратегии в шахматах, здесь просто не уместен. Во-первых, дерево решений го необычайно огромно – на начальной позиции существует 55 вариантов ходов (в шахматах – 20), и «растет» оно быстрее – после первых двух ходов соперников существует уже около 16 миллиардов позиций для следующего (в шахматах – меньше ста тысяч). А во-вторых, го – игра, в которой очень важен опыт.

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

Но вот настал 2016 год и программа AlphaGo, разработанная корпорацией Google, в прямом эфире победила мирового мастера с девятым даном – Ли Седоля. Это стало возможно благодаря новому подходу обучения, который кардинально отличается от обучения шахматных компьютеров. Помните, что Deep Blue использовал обычный метод перебора дерева решений просто с кучей оптимизаций и на самом деле кроме мощных процессоров и больших объемов памяти он недалеко ушел от железяк 60-х.

Крестики-нолики, шашки и шахматы: немного об играх в математике Игры, Математика, Шашки, Шахматы, Timeweb, IT, История, Познавательно, Крестики-нолики, Научпоп, Наука, Компьютер, Изобретения, Длиннопост

AlphaGo – революционная программа, в ней нет базы данных с удачными ходами чемпионов или оценочного алгоритма, лишь самые базовые правила, которым учат новичков. Всему остальному она научилась сама, проигрывая тысячи партий с собой. В основе компьютера лежит нейронная сеть, моделирующая работу органического мозга. Главное новшество AlphaGo заключается в использовании глубинного обучения — метода, успешно применявшегося для распознавания образов (например, для поиска картинок в Google Images). Но как ни парадоксально именно из-за этого разработчики не знают, каким конкретным образом программа оценивает ситуацию в игре: система настолько сложна, что анализировать все уровни обработки информации в целом не представляется возможным.

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *