Перейти к содержанию

3.6 Грубая сила машины: отделяем правду от вымысла (второе отступление)

Материал из Охота на электроовец: Большая Книга Искусственного Интеллекта

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

Первая книга Царств 17:4-7

При изучении деталей проектов ChipTest, Deep Thought и их наследника Deep Blue первое, что бросается в глаза, — разительный контраст между публичным восприятием этих проектов и их действительным содержанием. В массовом сознании прочно закрепилось представление о проектах Сюя как о дорогостоящих монструозных машинах, очень глупых, но очень быстрых, подавляющих соперников «грубой силой».

Это представление в массовом сознании часто переносят на вообще все шахматные программы. Многие из наших соотечественников, интересовавшихся в детстве и юности шахматами, черпали представления о шахматном программировании из книг и статей Ботвинника, обладавшего в шахматной среде серьёзным авторитетом. Отстаивая собственные идеи, Михаил Моисеевич называл программы своих идейных соперников «полнопереборными». Рассуждая об успехах Deep Thought, которые не мог игнорировать, он не обошёлся без характерной для него колкости: «Здесь мы имеем не искусственный интеллект, а мы имеем очень работоспособного идиота»[1].

В действительности шахматные программы никогда не были «полнопереборными», даже бумажная машина Тьюринга при достижении лимита по глубине перебора рассматривала далее лишь форсированные ходы, а значит, спекулятивным образом отбрасывала часть возможных вариантов. Появление альфа-бета-отсечений, эвристики пустого хода, хеш-таблицы перестановок, множества других алгоритмов отсечения и продления перебора постепенно делало шахматные программы всё более селективными и всё дальше уводило их от «полного перебора». Слова Ботвинника, на мой взгляд, были примером когнитивного искажения, известного под названием «соломенное чучело». Возможно, вы и сами не раз наблюдали, как в споре один из участников искажает точку зрения оппонента, подменяя её похожей, но более слабой или абсурдной — таким образом создавая вымышленный образ оппонента, который и называют «соломенным чучелом». Спорщик затем «доблестно побивает» чучело, стремясь убедить зрителей в том, что была опровергнута точка зрения оппонента.

Представим на мгновение, что Deep Blue действительно был бы программой, перебирающей все возможные варианты. Взяв из шахматного учебника задачу с матом в шесть ходов, которая под силу практически любому перворазряднику, прикинем, сколько потребовалось бы времени Deep Blue, чтобы решить её методом полного перебора. В среднестатистической шахматной позиции возможно примерно 35 различных ходов. Чтобы с гарантией найти мат в один ход, нужно рассмотреть 35 возможных альтернатив, мат в два хода (т. е. в три полухода) — уже 353 = 42 875 вариантов и так далее. При глубине в 11 полуходов, необходимой для гарантированного нахождения мата в шесть ходов, машине потребовалось бы перебрать 96 549 157 373 046 875 позиций, на что при скорости перебора в 200 млн позиций в секунду понадобилось бы около 15 лет. А ведь отдельные комбинации шахматных мастеров простираются на 10–15 ходов! Если бы Deep Blue действительно был «работоспособным идиотом» такого рода, то вряд ли мог бы соревноваться даже с любителями.

Наверняка многие из вас слышали притчу о зёрнах и шахматной доске. В одной из её версий изобретатель шахмат (в некоторых источниках — Лахур Сесса или Сисса бен Дахир, древнеиндийский мудрец) в награду за своё изобретение просил правителя выдать ему зёрна пшеницы, положив одно зерно на первую клетку шахматной доски, два на вторую, четыре на третью, восемь на четвёртую и так далее. Правитель в ответ сначала смеётся над изобретателем, попросившим столь скудный приз за блестящее изобретение, а затем оказывается потрясён после того, как придворные казначеи сообщают, что общее количество зёрен во много раз превышает все запасы правителя. В итоге в различных версиях окончания притчи изобретателя либо производят в высокопоставленные советники, либо казнят[2]. Примерные подсчёты показывают, что масса зерна должна была составить около 1,2 трлн тонн, что примерно в 1500 раз больше мирового производства зерна в 2017 г.[3]

Теперь представьте себе ту же самую задачу с зёрнами, в которой на каждое следующее поле выкладывается не в два раза, а в 35 раз больше зёрен, чем на предыдущее. Клод Шеннон в своё время попытался прикинуть нижнюю границу числа возможных шахматных партий. Предположив, что один ход, составленный из двух полуходов, предоставляет порядка 1000 = 103 альтернатив, при средней продолжительности партии в 40 ходов Шеннон получил оценку в 10120 различных партий[4]. Это число сегодня называют «числом Шеннона». Позже голландский информатик Виктор Аллис уточнил эту оценку[5], увеличив её на три порядка — до 10123. Для сравнения: число атомов в наблюдаемой части Вселенной составляет порядка 1080, то есть в 1043 раз меньше[6]. Правда, различных позиций в шахматах существенно меньше: около 4,5 × 1046 (современная оценка сверху)[7], а значит, если бы мы научились хранить в одном атоме кремния информацию о том, является ли шахматная позиция выигранной, проигранной или ничейной, то нам бы потребовалось примерно два квинтиллиона тонн кремния, чтобы сохранить сильное решение шахматной игры. В принципе, это не так много, порядка 3% массы Луны. Возможно, наши далёкие потомки когда-нибудь воплотят в жизнь подобный проект ради забавы — конечно, если будут обладать соответствующим чувством юмора. Пока же ни о каком «полном переборе» говорить не приходится.

Для иллюстрации работы современных шахматных программ я проделал небольшой эксперимент. Взяв одну из позиций последней партии второго матча Каспарова с Deep Blue, я заставил свою программу анализировать эту позицию в течение часа. За это время программа успела просмотреть примерно 2 млрд позиций, и самый длинный вариант, изученный ею в процессе анализа, простирался от стартовой позиции на 62 полухода. Это означает, что в игровом дереве глубиной в 62 полухода на один изученный вариант приходилось примерно 3 × 1086 отброшенных. И это не предел: современные программы, использующие нейронные сети при построении игровых деревьев, такие как Leela Chess Zero, могут довольствоваться деревьями размером ещё в 100–1000 раз меньше[8] при том же или более высоком уровне игры.

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

Миф о «полнопереборных» программах породил и другие заблуждения, в плену которых иногда оказываются даже специалисты в области искусственного интеллекта. Например, существует мнение, что над созданием шахматных программ работают крупные коллективы наёмных программистов. Если для того, чтобы обыграть чемпиона мира, потребовалось создать уникальный суперкомпьютер, то сегодня в компьютерных шахматах осталось место только для гигантских корпораций, способных «задавить» проблему исключительно финансами и человеческим мясом, бросаемым на амбразуру шахматного программирования. Поэтому появление новых технологий в этой сфере грозит массовыми увольнениями и всеобщим потрясением основ[9]. В действительности, за редким исключением, шахматные программы сегодня — результаты усилий одиночек, для которых их детища являются обычно хобби-проектами. На вершинах рейтингов шахматных программ красуются программы с открытым исходным кодом, такие как Stockfish (и его модификации) и Leela Chess Zero, создаваемые усилиями энтузиастов. Deep Blue вырос из аспирантского проекта Сюя Deep Thought, весь бюджет которого составил 5000 долларов (не считая расходов на производство шахматного чипа, оплаченных за счёт средств образовательной программы)[10]. Да, IBM позволила себе на несколько лет выделить под шахматный проект несколько специалистов и даже нанять несколько шахматных профессионалов в помощь команде, но даже здесь речь не шла об огромном коллективе. Развитие технологий, позволяющих частично заменить человеческую экспертизу моделями, являющимися продуктами машинного обучения, приводит не к уменьшению, а скорее к увеличению количества людей, вовлечённых в шахматное программирование, так как с появлением новых моделей возрастает интерес к испытанию их возможностей.

Ещё одно связанное с мифом о «полнопереборных» программах заблуждение заключается в том, что весь прогресс, достигнутый в шахматном программировании за последние годы, являет собой результат роста вычислительной мощности компьютеров. Получается, если игра программ неизменно основана на полном переборе, то единственный способ её усилить — это ускорить этот перебор, задействовав более современное оборудование. Сила игры современных программ действительно хорошо коррелирует с ростом вычислительной мощности машин, однако наличие корреляции не говорит о наличии связи. Точно так же сила игры шахматных программ неплохо коррелирует с ростом числа фотографий котиков, накопленных человечеством, но из этого вовсе не следует, что программы становятся сильнее под влиянием всевозрастающего объёма милоты и няшности. Чтобы опровергнуть это заблуждение, достаточно сравнить силу игры старых и новых шахматных программ на одном и том же оборудовании. Deep Fritz 10, выигравший в 2006 г. матч у Владимира Крамника, на сайте CCRL сегодня имеет рейтинг 2829 пунктов Эло, лидер же рейтинга движок Stockfish 14 — 3543 пункта[11]. Разница в 714 пунктов означает, что в матче из пятидесяти партий между этими двумя программами на одинаковом оборудовании Fritz будет в среднем проигрывать со счётом 49 : 1. Весь этот прогресс был достигнут целиком и полностью за счёт совершенствования алгоритмов, лежащих в основе шахматных программ. Если же говорить об оборудовании, современным средним персональным компьютерам ещё далеко до скорости перебора, продемонстрированной Deep Blue в 1997 г. (например, компьютер, оснащённый процессором Intel i9-10885H с тактовой частотой 2,4 ГГц и 16 логическими ядрами, позволяет классической версии Stockfish просматривать в середине игры около 10 млн позиций в секунду, что всё ещё в десятки раз меньше, чем соответствующий показатель Deep Blue).

Забавно, что многие люди, будучи загипнотизированными магией миллионов позиций в секунду, просматриваемых программами, упускают из виду тот факт, что анализ шахматной позиции человеческим мозгом — это процесс, вовлекающий огромное количество не осознаваемых до конца человеком вычислений, производимых этим уникальным «биологическим компьютером». Люди действительно умеют эффективно оценивать шахматные позиции и обходиться изучением небольшого поддерева игры, но это достигается за счёт скоординированной работы гигантского ансамбля нервных клеток. Давайте попробуем примерно оценить возможности «биологической машины», заключённой в черепной коробке. Действительно ли «грубая сила» [brute force] сегодня на стороне наших рукотворных систем?

Среднестатистический человеческий мозг состоит из примерно 86 млрд нервных клеток — нейронов[12]. Соединения нейронов называются синапсами, их количество в человеческом мозге меняется в течение жизни человека и в пике составляет порядка одного квадриллиона (1015)[13], [14]. Каждый синапс представляет собой сложный электрохимический механизм, который может содержать порядка тысячи переключателей молекулярного размера[15]. В месте контакта между нейронами содержится крошечный зазор, который называют синаптической щелью. В этот зазор могут проникать молекулы веществ, называемых нейромедиаторами. В зависимости от набора молекул, оказавшихся в синаптической щели, меняются параметры передачи электрических сигналов между нейронами. Вообще говоря, для достаточно точного моделирования массива из 30 000 синапсов сегодня требуется от 30 до 400 Мб памяти, что даёт нам оценку примерно от 8400 до 112 000 битов на синапс[16], но мы возьмём консервативную оценку в тысячу транзисторов на синапс. К сожалению, мы не знаем, с какой точностью нужно моделировать синапсы нейронов, чтобы построенная из таких нейронов сеть смогла эффективно воспроизводить наблюдаемые у людей психические феномены. Как метко выразился ещё Тьюринг: «Нас не интересует, что мозг имеет консистенцию холодной каши», то есть нас интересуют не свойства субстрата, а вычислительные возможности биологической «машины». Последними экспериментами установлено, что для достижения 99% точности при моделировании поведения биологического нейрона на миллисекундном масштабе необходимо около тысячи искусственных нейронов, и хотя обычно реализация одного синапса искусственного нейрона требует более чем одного транзистора, мы можем хотя бы приблизительно оценить «производительность» отдельного биологического синапса[17], [18], [19]. Умножив квадриллион синапсов на тысячу транзисторов, получим «транзисторный эквивалент» мозга, равный одному квинтиллиону (1018) условных транзисторов.

Ни одна созданная до настоящего времени интегральная микросхема не может похвастаться таким количеством транзисторов. Действующий рекорд среди серийных микропроцессоров принадлежит GPU (graphics processing unit, графический процессор, в просторечии «видеокарта») от Nvidia под названием H100 — он содержит 80 млрд транзисторов [20] (8,00 × 1010) [21], самая большая серийная программируемая вентильная матрица (FPGA) — Xilinx Virtex UltraScale+ VU19P — состоит из 32 млрд транзисторов [22] (3,2 × 1010).

Впрочем, электроника имеет серьёзное преимущество в скорости. Продолжительность нервных импульсов в мозге составляет примерно 1–2 мс[23], и данные современной нейрофизиологии не позволяют нам утверждать, что рабочая частота мозга может превышать порог в 1 кГц, в то время как электронике доступны частоты, приближающиеся к 9 ГГц. Впрочем, самый «шустрый» процессор AMD FX-8150, работающий на частоте 8,81 ГГц, содержит всего 1,2 млрд транзисторов, в то время как частота H100 составляет скромные 1590 МГц по умолчанию и 1,98 ГГц при разгоне. Вентильная матрица Virtex UltraScale+ VU19P и вовсе предназначена для работы на частоте около 900 МГц (если исходить из величины Maximum frequency of a global clock tree[24] в документации[25]). Перемножив частоту каждого устройства на количество транзисторов, получим теоретический предел производительности в битах в секунду. Для мозга он, по нашим подсчётам, составляет порядка 1021 бит/с, а для микропроцессоров — не более 1,58 × 1020 бит/с. Таким образом, даже при крайне консервативной оценке вычислительной мощности отдельного синапса мы видим, что мозг превосходит микропроцессоры по своей «брутто-производительности» примерно на один десятичный порядок.

Конечно, сравнение это является сугубо приблизительным и основано на ряде серьёзных допущений. И всё-таки оно даёт представление о «грубой силе» человеческого мозга. Ещё более печальным для электроники сравнение становится после оценки энергоэффективности вычислений. Мозг, несмотря на свою фантастическую производительность, потребляет всего около 20 Вт, в то время как энергопотребление самых быстрых процессоров доходит до 400 Вт.

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

  1. ↑ Осень шахматиста. Михаил Ботвинник (1990) // https://www.youtube.com/watch?v=IQZqN0b6Op0
  2. ↑ Tahan M. (1993). The Man Who Counted: A Collection of Mathematical Adventures. New York: W. W. Norton & Co., pp. 113—115 // https://books.google.ru/books?id=WMv_2aSlXOoC&pg=PA113
  3. ↑ Crops (2017) / FAOSTAT. Retrieved 2019-08-18. Countries - Select All; Regions - World + (Total); Elements - Production Quantity; Items - Wheat; Years – 2017 // http://www.fao.org/faostat/en/#data/QC/
  4. ↑ Shannon C. E. (1950). Programming a Computer for Playing Chess / Philosophical Magazine, Ser. 7, Vol. 41, No. 314 // https://vision.unipv.it/IA1/aa2009-2010/ProgrammingaComputerforPlayingChess.pdf
  5. ↑ Allis V. (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph. D. Thesis, University of Limburg, Maastricht, The Netherlands // http://fragrieu.free.fr/SearchingForSolutions.pdf
  6. ↑ Saul E. (2013). The Coded Universe: The Path to Eternity. Red Lead Press // https://books.google.ru/books?id=E22mj8ImiKwC
  7. ↑ Tromp J. (2010). John's Chess Playground // https://tromp.github.io/chess/chess.html
  8. ↑ Bob23 (2018). GUIDE: Setting up Leela on a Chess GUI / Lc0 blog // http://blog.lczero.org/2018/09/guide-setting-up-leela-on-chess-gui.html
  9. ↑ Левенчук А. (2015). Интеллект-стек // https://youtu.be/1mL2DL6ZBSw?t=965
  10. ↑ Hsu F. (2004). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press // https://books.google.ru/books?id=WOk9DwAAQBAJ
  11. ↑ CCRL 40/40 Downloads and Statistics: Complete rating list, retrieved 2022-01-27 // https://ccrl.chessdom.com/ccrl/4040/rating_list_all.html
  12. ↑ Azevedo F. A., Carvalho L. R., Grinberg L. T., Farfel J. M., Ferretti R. E., Leite R. E. P., Filho W. J., Lent R., Herculano-Houzel S. (2009). Equal numbers of neuronal and nonneuronal cells make the human brain an isometrically scaled-up primate brain / Journal of Comparative Neurology. Vol. 513(5), pp. 532—541 // https://www.ncbi.nlm.nih.gov/pubmed/19226510/
  13. ↑ Dresbach T., Qualmann B., Kessels M. M., Garner C. C., Gundelfinger E. D. (2001). The presynaptic cytomatrix of brain synapses / Cellular and Molecular Life Sciences, Vol. 58, pp. 94—116 // https://doi.org/10.1007/PL00000781
  14. ↑ Donald C. Cooper (2014). Introduction to Neuroscience. CU Neuroscience Series // https://books.google.ru/books?id=jXnkai44PxYC
  15. ↑ Goldman B. (2010). New imaging method developed at Stanford reveals stunning details of brain connections // https://med.stanford.edu/news/all-news/2010/11/new-imaging-method-developed-at-stanford-reveals-stunning-details-of-brain-connections.html
  16. ↑ Hu E. Y., Yu G., Song D., Bouteiller C. J., Berger W. T. (2018). Modeling Nonlinear Synaptic Dynamics: A Laguerre-Volterra Network Framework for Improved Computational Efficiency in Large Scale Simulations. Conference proceedings: Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual Conference, 64 (2), pp. 6129—6132 // http://europepmc.org/articles/PMC6462142
  17. ↑ Beniaguev D., Segev I., London M. (2021). Single cortical neurons as deep artificial neural networks / Neuron, Vol. 109, Iss. 17, pp. 2727—2739.e3 // https://doi.org/10.1016/j.neuron.2021.07.002
  18. ↑ Whitten A. (2021). How Computationally Complex Is a Single Neuron? / Quanta Magazine, September 2, 2021 // https://www.quantamagazine.org/how-computationally-complex-is-a-single-neuron-20210902
  19. ↑ Уиттен Э. (2021). Насколько сложной должна быть компьютерная модель одного нейрона? / Пер. с англ. Горлова А // https://22century.ru/popular-science-publications/a-single-neuron-is-very-complex
  20. ↑ NVIDIA H100 SXM5 80 GB (2023). / TechPowerUp // https://www.techpowerup.com/gpu-specs/h100-sxm5-80-gb.c3900
  21. ↑ * Скорее всего, этот показатель будет немного улучшен с выходом GPU семейства Hopper-Next от Nvidia в 2024 году.
  22. ↑ Creating Tomorrow’s Next-Generation Technologies Today // https://forums.xilinx.com/t5/Xilinx-Xclusive-Blog/Creating-Tomorrow-s-Next-Generation-Technologies-Today/ba-p/1156382
  23. ↑ Gerstner W., Kistler W. (2002). Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge University Press // https://books.google.ru/books?id=Rs4oc7HfxIUC
  24. ↑ ** Максимальная частота глобального иерархического дерева тактовых импульсов; сеть распределения тактовых импульсов (или дерево тактовых импульсов, когда эта сеть формирует дерево) — часть электрической схемы, которая распределяет сигнал(ы) тактовых импульсов (т. е. импульсов, предназначенных для синхронизации различных процессов в схеме) от общего источника до всех элементов, которые в них нуждаются.
  25. ↑ Virtex UltraScale+ FPGA Data Sheet: DC and AC Switching Characteristics // https://www.xilinx.com/support/documentation/data_sheets/ds923-virtex-ultrascale-plus.pdf

‎

Loading comments...
Источник — http://wiki.markoff.science/index.php?title=3.6_Грубая_сила_машины:_отделяем_правду_от_вымысла_(второе_отступление)&oldid=1135