Playing god at how AI has learned to win human Bashny.Net

In 16 games machines defeated man (17, if you take into account Lee Se-dol defeat in the second), but in the future they are waiting for an even more impressive achievements: the decision of the most stunning mathematical, physiological and biological problems, the victory over sickness and old age, the elimination of road accidents triumph in military conflicts, and more.

The world has changed before our eyes, but not all noticed it. When and how the program learned to play correctly? Is it always the loss of one man shows the defeat of all mankind? Will find whether artificial intelligence consciousness?

About the Author. B> This article is based on the lecture "Artificial Intelligence. History and Prospects ", held in the Moscow office of Mail.Ru Group Sergei Markov. Sergei Markov, machine learning is engaged in the "Savings Bank". In the banking sector build predictive models for business process management, based on sufficiently large training samples, which may include several hundreds of millions of cases. Among his hobbies Sergey indicates chess programming, AI games, minimax problem. SmarThink program, created by Sergei Markov, became the champion of Russia (2004) and the CIS (2005) among the chess programs (2004), and today is in the top 30 of the strongest programs in the world. Sergey also is the founder of the non-profit scientific and educational portal 22 Century.

How it all began


TechnoCore - the habitat of the plurality of artificial intelligence in the tetralogy "Songs of Hyperion" by Dan Simmons. One of the examples of strong AI visualization in science fiction.

From the very notion of AI occurred unpleasant story. Appearing originally in science among professionals working in the field of computer science, it quickly fell into the public environment and has undergone various changes. If you ask the man in the street today, that is the AI, the more likely you will hear from him is not the definition that is kept in mind by AI experts.

Before you begin a story, you need to decide exactly what we mean by artificial intelligence, and where is the boundary at which ends compute rscience region and adjacent areas begin.

AI in general - is the methods used to automate tasks that are traditionally considered to be the intellectual tasks, and for which a person uses his natural intelligence. By automating problem solved by man with the help of the brain, we thereby create AI. Another thing is that this AI is commonly referred to as application or, with some degree of contempt weak. Unpleasant caveat is that it is only available to mankind today kind of AI.

As for the strong AI, artificial general intelligence (AGI), certain developments there, but as long as we are in the very beginning. Strong AI - it is a system that can deal with any intellectual challenges. In fiction image is formed such as man, AI, able to solve any problem.



Because we are so widely used in computer science define artificial intelligence, from the formal point of view we find elements of the existence of the AI ​​even the ancient Greeks. We are talking about the famous Antikythera mechanism, which is one of the out-of-place artifact. This device is intended for astrophysical calculations. The picture above shows one of the surviving fragments and a modern reconstruction of the artifact. The mechanism comprises 37 bronze gears in a wooden case, on which were placed the arrow dials. Restore the position of the gears inside the coated mineral fragments managed by computerized tomography using X-rays.

By itself, the task of the account once considered intellectual - if one could well believe that it could be called intellectual

.

Accounts unit of John Napier's designed for rapid multiplication.

tasks of automated accounts among the first. Even before the first mechanical devices appeared crafts type neperovyh sticks. Scottish mathematician, one of the inventors of John Napier logarithms, create an account unit in 1617 Against the background of modern technology, it seems ridiculous: rolls of paper - in fact, the first logarithmic tables to perform certain operations. But to contemporaries it was about the same miracle as any AlphaGo for us. At one time there were even poets dedicate neperovym sticks (Napier's bones) verses. Say why you nosites with bones of ancestors, that's the very bone, which is really worth to be proud of.



Pascal's calculator - arithmetical machine, invented by the French scientist Blaise Pascal in 1642

Pascal, along with the German mathematician Wilhelm Schickard, who offered his own version of a computer in 1623, laid the foundations for the emergence of the majority of computing devices. We have survived a few cars, even when Pascal created life. This machine was able to add, divide, subtract and multiply.



full working copy machine, invented by the English mathematician Charles Babbage in 1822. The so-called difference engine is designed to automate calculations by approximating functions by polynomials and calculating finite differences.

About Charles Babbage had heard almost all computer scientists. Alas, Babbage was never able to create a working computer. For a long time did not cease controversy, works in principle he proposed difference engine. In the period from 1989 to 1991, the 200th anniversary of the birth of Charles Babbage, the surviving drawings and with minor modifications was collected working copy of the analytical engine. The modifications were necessary because of the "bugs" found in the drawings. Perhaps Babbage deliberately made some distortion fighting unlicensed pirate copying.

Analytical Engine - is the prototype of modern von Neumann machines. When IBM engineers built the first electronic machine, they used Babbage's blueprints. We used to speak of the Von Neumann architecture, that is, a machine with separate computing device with an input-output device, memory, etc. However, based on Babbage's ideas are.

In addition to machine code bebbidzhevoy machine operator applied conditional branch and loop statement. This machine is truly a great-grandfather of what then was able to make on the basis of electronics.



jacquard machine - shed forming mechanism of the loom for the production of large-figured tissues. Created in 1804 Allows you to separately manage each support filament or a small group of them.

Input-output devices, punch cards were still to Babbage - they were used in weaving machines zhakkardovskih to set the order of the yarns at the fabric manufacturing

. New time


TAB - electromechanical machine designed for automatic processing of numeric and alphabetic data stored on punch cards

. The first statistic is built tabulator American Herman Hollerith in 1890 to solve the problems associated with statistical calculations. The well-known inventor and maker of equipment for working with punch cards successfully participated in the competition organized by the US government to find means of automation of processing the results of the population census. For manual counting and analysis would take about 100 people working for 4-5 years just to compile and calculate the total sociological census figures.



Hollerith punch cards.

TAB - this is a very primitive summary table. Each card corresponds to the questionnaire, it caved in, the relevant account. Cards loaded in a tab, he quickly chased them through themselves and produce results in the form of a card with the counted amount. These amounts were invested in another tabulator etc.

After winning the competition, Hollerith founded the company - Tabulating machines company, and after a series of mergers and acquisitions, it became known as IBM

. Games that are played machines
As in any experimental science, computer science section, is engaged in the AI ​​needed an own fly Drosophila, a model object, which you can try out the AI ​​techniques. The game - the most famous fly Drosophila in AI

. Game - net model space. It specified conditions states uniquely defined and described as a set of parameters. Creating AI for the game, we thus abstract from the mass of the engineering problems that lie between AI and practical solution to the problem. We abstract from the data encoding on the input and output from the signal conversion, the problem of perception, etc. For us, there is an intellectual task in the game in its purest form. This is convenient, because for AI specialists are lazy and do not want to do anything except AI.



Chess Machine "Turk».

Game - it is a spectacle. If you show the car, who knows how to play well, it will make an impression even on the ignorant person. Game Machine attracted attention for hundreds of years. In the picture above you can see an illustration of the famous hoax - the first chess machine, designed the inventor Wolfgang von Kempelen in 1769. Inside the "car" is actually hiding a real player. In this box did not disdain to climb the leading chess players of his time. Johann Baptist Allgaier, the strongest chess player of Austria late XVIII -. The beginning of the XIX century, has played for The Turk a number of parties

. This is a complex mechanical device is not artificial intelligence, but it is curious that with his help was able to fool contemporaries. People really believed that some craftsman was able to create a system capable of playing chess with the help of gears, levers, mechanisms and balances. Preserved even record games played by a mechanical Turk against Napoleon (though some historians have questioned the accuracy of his subject). So maybe that had fooled even the highest personages.



And this is the first device that really knew how to play chess. El Ajedrecista (in Russian - "chess player"). It was created in 1912 by the famous Spanish mathematician and engineer Leonardo Torres Quevedo.

El Ajedrecista was a chessboard on which the machine using electromagnets moved the king and rook. The machine is guaranteed to put the king and the rook checkmate a lone king from one position: the king was standing by the white on the H8 rook - on the G7, and the black king could be in any field. Two surviving copy machines on display at the Polytechnical Museum in Madrid.



This is another well-known AI last - mechanism "Nimatron", created in 1940 to play him. Him - a mathematical game in which two players take turns taking the items laid out on several piles (usually three). In one move, you can take any number of items (greater than zero) of a handful. The winner is the player who takes the last object.

This is one of the first games that have built a complete mathematical theory back in the 1901-1902 biennium. In terms of methods of "Nimatron" nothing new presented, based on the already known optimal strategy for this game, but it was one of the first decisions of game theory in the gland.

Project "Nimatron" directed by Edward Uhler Condon - one of the fathers of modern quantum mechanics. He considered the project's biggest failure in my life, but not with the technical and financial side. Working on "Nimatronom" Condon and his team invented many technologies (including, for example, printed circuit board manufacturing method), which were later claimed in computer technology. But the team did not patented experts, as a result of anything does not work.

The optimal strategy


Ernst Friedrich Ferdinand Zermelo - German mathematician who made significant contributions to the theory of sets and the creation of the axiomatic foundations of mathematics

. Talking about artificial intelligence for games is complete without mention of Ernst Zermelo and his theorem. Russian-speaking fans of the topic of luck. Zermelo's work was originally written in German. And if it was translated into English only in 1999, the Russian language - in the late 1960s - early 1970s. Because of this, in Russian literature written more or less correct about what Zermelo did, and in English-language literature is still confused. For example, in one study said that Zermelo proved that if the white chess will make perfect moves, be sure to reach at least a draw. In fact, no one to date has not provided any such evidence, however Zermelo made another important discovery.

It is not a good game of chess, and in general did not know the rules of the game. Perhaps because of this, and proved in 1913 the first formal theory of game theory. According to the book "Managed processes and game theory", published in the USSR in 1955, the correct description of Zermelo contribution is: "Zermelo proved determinism games like chess, and what rational players can, using all the information to develop an optimal strategy game . »

Ordinary rules of chess know almost everything, but there are some other very important and not entirely obvious rules. For example, a rule moves 50 states that if during 50 moves no pawn has not moved forward, and no one figure has not been taken, it is awarded to a draw. Or if a certain position is repeated three times - also awarded a draw. Infinite game of chess on the number of strokes can not be - at some point in the game one way or another stop. Ernst Zermelo did not know it, and I thought that the possibilities are endless chess games: you go figure - back, and so play until the universe does not crumble into dust.

How to win at tic-tac-toe


So let's see how to determine the optimal strategy game. A little digress from chess, take a simple example - tic-tac-toe, one of the oldest games in the world, appeared in ancient Egypt. For this game Zermelo used backward induction - the method by which the search is conducted in the opposite direction, starting from the position where one of the parties has received a pat or a mat, and ending with the specific position of standing on the board <. br>
Zermelo did not give a detailed description of backward induction, but used it the principle that there is a position for the winning side. We can appoint to such positions assessment: -1 - won toe, 1 - won crosses 0 - draw

. Now we can go up the tree from these positions and see if the course is, with some positions, leading to a winning position. If there is progress, then the item will be considered winning.

On the other hand, if there is no progress, leading to a winning position, but there is at least one passage leading into the no-man's position, then this position is considered a draw. And if there is no progress, the master nor no man, nor in winning position, the position is considered to be lost.

Using this rule, we are in the tree, starting with the leaves, moving up, and attribute nodes evaluation until we assign marks to all positions. After receiving all the scores for all positions, we see a perfect algorithm for the game. Once in a certain position of the game, we will always see the progress (if any), leading to a winning position. If the winning move is not present, it will do a draw stroke, and only in the worst case will go to a losing position. Theoretically, such a system is capable of storing in memory evaluation tree for each position, will play at the level of a god.



Zermelo is understood, but believed that this tree has infinite branches where there is no terminal point. He wondered whether it is possible for a game that has infinite tree on the size of positions in it, in a finite time to calculate the optimal strategy that is guaranteed to be in any position to make the perfect move? And proved that in spite of the fact that the tree itself can be infinite, we can find the optimal strategy for a finite number of iterations. And it is a finite number of iterations definitely not higher than the number of different items in the game.



EDSAC (Electronic Delay Storage Automatic Calculator) - the first in the world of acting and practically used a computer program stored in memory, created in 1949 by the University of Cambridge (UK). In 1952, the implementation of the game of tic-tac-toe for EDSAC computer was one of the first video games. The computer learned to play the perfect game against a person known to him in terms of optimal strategy.

Contact Induction: History
method

economist Oskar Morgenstern, one of the authors of the theory of games, and the mathematician John von Neumann, who made important contributions to quantum physics, functional analysis, set theory and other branches of science.

Employment about inducing interpretation is reverse in set theory. Another area of ​​knowledge, without which it is impossible to imagine the development of game theory, lies in the field of economy. В 1944 г. вышла монография Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение», в которой авторы обобщили и развили результаты теории игр и предложили новый метод для оценки полезности благ. В этой работе впервые формально было дано определение метода обратной индукции.



В 1965 г. математик Ричард Белман предложил использовать метод ретроспективного анализа для создания баз данных решений шахматных и шашечных эндшпилей (заключительная часть партии). Он дал алгоритмическое описание применения метода обратной индукции для построения оптимальной стратегии в играх.



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

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



В 1977 г. Кен Томпсон, известный за вклад в создание языка С и ОС UNIX, представил одну из первых в мире эндшпильных таблиц для всех пятифигурных окончаний.

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



Эту главу закроет фотография не человека, а компьютера. В 2012 г. рассчитали семифигурные таблицы для ситуаций распределения фигур четыре против трех и пять против двух. Их назвали таблицами «Ломоносова», так как рассчитывались они на суперкомпьютерах МГУ «Ломоносов» и IBM BlueGene/P.

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

Эксперты ФИДЕ (Federation Internationale des Echecs — Международная шахматная федерация) предложили заменить правило 50 ходов на правило 75 ходов, что и было сделано.



Вскоре выяснилось, что в ряде случаев для завершения партии недостаточно и 75 ходов, но и на этом процесс поиска новых решений не остановился. На сегодняшний день рекордная задача — мат в 549 ходов.

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



Кен Томпсон провел несколько показательных выступлений — «ладья и король против ферзя и короля». Компьютер играл за игрока, владеющего ладьей. Этот эндшпиль теоретически проигрышный — шахматист уровня мастера, владея ферзем, обычно легко выигрывает у любого противника. Компьютеру была поставлена задача максимально оттянуть свой теоретически неизбежный проигрыш. На одном из выступлений против компьютера играли Ханс Берлинер, чемпион мира в игре по переписке, со своим другом — сильным гроссмейстером из топ-30 мировых игроков. И двум гроссмейстерам не удалось заматовать короля. На доске происходило нечто феерическое — происходили неясные маневры, но черным чудесным образом удавалось выпутаться. Это была одна из первых прекрасных демонстраций того, что люди, возможно, переоценивают себя в понимании некоторых вещей.



Фрагмент листинга шахматной программы ИТЭФ для ЭВМ М-20.

Первый матч между двумя шахматными программами состоялся в 1967 г. Играли программа Института теоретической и экспериментальной физики и программа Стэнфордского университета. Сохранился исходный код программы ИТЭФ, скачать его можно здесь.

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

Решение на уровне бога


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

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

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

И третий вид — сильное решение. Для каждой позиции мы знаем ее точную оценку. Например, для крестиков-ноликов точно знаем дерево ходов — около 900 позиций, если учесть все симметрии.

29 апреля 2007 г. команда исследователей из Университета Альберты (Канада) под руководством Д. Шеффера (известного как ведущий разработчик шашечной программы «Чинук») смогла достичь «слабого» решения для английских шашек, по правилам которых шашки не бьют назад, а дамки не могут ходить на любое расстояние.

Английские шашки — самая большая из игр, решенных до настоящего времени. Размер ее поискового пространства 5×1020. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (в разное время от 50 до 200) произвела 1014 вычислений.



На начало 2016 г. найдено решение в 16 играх. Последней на данный момент решенной игрой стала пентаго. В отличие от шахмат и го поисковое пространство игры небольшое, что позволяет современному компьютеру играть идеально: с учетом всех возможных симметрий количество возможных позиций в пентаго составляет 3 009 081 623 421 558. В течение нескольких часов суперкомпьютер Edison семейства Cray, находящийся в Национальном научно-вычислительном центре энергетических исследований (NERSC), нашел «сильное» решение игры. Программа использовала для вычислений 98 304 потоков.



Также удалось найти решение для такой необычной игры, как «Магараджа», где черные имеют набор обычных шахматных фигур, а белые — единственную фигуру Магараджа. Это ферзь, способный ходить как конь. Доказано, что черным гарантирована победа.

DRAMA: от проигрыша машины к проигрышу человека


Американский математик и шашист Марион Франклин Тинсли был сильнейшим игроком мира в английские шашки на протяжении 30 лет. Тинсли ни разу в жизни не проигрывал матч за первенство мира и за свою 45-летнюю карьеру проиграл всего семь партий.

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

На матче реванше Тинсли успел сыграть шесть игр — все ничьи. После этого он почувствовал себя очень плохо и у него диагностировали рак поджелудочной железы и вскоре он умер. В 1995 г. программа «Чинук» выиграла у Дона Лафферти, наследника Тинсли на шашечном троне. Из 32 сыгранных партий единственная результативная партия завершилась в пользу компьютера. После этого первенство в шашках окончательно перешло к машинам.



Одна из величайших шахматных партий всех времен.

Более распиаренный матч, о котором слышали даже далекие от шашек и шахмат люди, состоялся в 1997 г. Гарри Каспаров проиграл суперкомпьютеру Deep Blue в матче из шести партий. Для сравнения: Deep Blue был способен просматривать 200 млн позиций в секунду, в то время как современные компьютеры просматривают 1—3 млн позиций в секунду. За прошедшие 20 лет компьютеры так и не смогли догнать этот уникальный инженерный проект.

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

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



На самом деле это не так. На рисунке выше приведен пример задачи из учебника — мат в шесть ходов. Deep Blue, используя полный перебор, должен был бы потратить около 356 лет на поиск решения. В среднестатистической шахматной позиции возможно 35 ходов, чтобы просмотреть на два хода — 35 в квадрате, на три — в кубе и т.д.

Любая сильная современная программа находит решение на настольном компьютере максимум за несколько секунд. Более того, на современной машине вы можете запустить программу чемпиона 2008 г. против программы чемпиона 2015 г. Из 27 партий одну партию будет выигрывать слабейшая программа, 26 партий — сильнейшая. Это прогресс, достигнутый за семь лет. Это произошло не за счет роста мощности железа, а благодаря развитию алгоритмов. За данным процессом не стоят тысячи программистов и десятки гроссмейстеров. Сейчас над шахматными программами работают либо программисты-одиночки, либо очень небольшие группы. Например, одну из самых сильных программ в мире шахмат — Stockfish — создали три программиста. Над самыми крупными, с точки зрения числа задействованных программистов проектами — Deep Blue и Каисса — работало менее десятка программистов.

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

Самое забавное, что если мы говорим о брутфорсе, то надо задаться вопросом: действительно ли брутфорс на стороне машин? В среднестатистическом человеческом мозге примерно 86 млрд нейронов и 150 трлн синапсов. Каждый синапс содержит примерно 1 тыс. молекулярных переключателей. Таким образом, если мы пересчитаем мозг в триггеры, то получим 150 квадриллионов (1, 5х1017) триггеров транзисторов. Конечно же, это две «машины» с абсолютно разной архитектурой, но мы очень примерно можем сравнивать их на некоторых задачах.



Один из самых мощных на сегодняшний день процессоров (Sparc-M7) имеет 10 млрд транзисторов. Самая большая программируемая пользователем вентильная матрица (FPGA) содержит до 20 млрд транзисторов. Это всего 2х109 раз, а в мозге 1, 5х1017 раз. Конечно, компьютеры имеют одно большое преимущество — скорость. Sparc работает на частоте 4, 3 ГГц. Человек же имеет следующие потенциалы действия нервных клеток: амплитуда — около 0, 1 В, длительность — около 1 мс, «рабочая» частота» — 10—100 Гц (до 1000 Гц).

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

Нейронные сети


В ИИ изначально было две крупных школы — «чистюль» и «грязнуль». «Чистюли» — по большей мере математики, настаивавшие, что должны использоваться корректные методы решения задач, имеющие формальное обоснование, или хотя бы обоснование статистическое.

«Грязнули» считали, что неважно, каким образом решать задачу. Если решение работает в рамках предметной области, значит оно хорошее. Они ввели термин hacking для ИИ — мы ломаем задачу, чтобы решить ее.

Если сейчас посмотреть на методы ИИ, используемые в играх, то увидим определенный синтетический подход. Формально необоснованные трюки, но хорошо работающие на практике, соседствуют с формально доказанными методами.

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



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



Схема искусственного нейрона:

нейроны, выходные сигналы которых поступают на вход данному; сумматор входных сигналов; вычислитель передаточной функции; нейроны, на входы которых подается выходной сигнал данного; Wi — веса входных сигналов.

Во многом отношения между этими людьми заложили некоторые базовые вещи в науке. Например, мы не называем нейронные сети кибернетическими системами, хотя МакКалак и Питс начинали работать под началом Норберта Виннера, основоположника кибернетики. Богемный образ жизни МакКалака и Питса и вечеринки с алкоголем очень не нравились жене Виннера. Есть мнение, что она сильно повлияла на раздор между учеными. Питсу это стоило карьеры, и, вполне вероятно, жизни — впоследствии он спился. Но они не стали делать из ссоры идеологический спор. Их пути разошлись по личным, а не научным причинам.

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



MARK 1 — первый в мире нейрокомпьютер, созданный в 1958 г. Фрэнком Розенблаттом.

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



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

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



Спустя полвека после изобретений Розенблата у нас появился нейроморфический процессор TrueNorth, созданный IBM по заказу DARPA. Чип содержит более 5 млрд транзисторов и имитирует работу до 1 млн модельных «нейронов» и до 250 млн связей между ними («синапсов»). В IBM говорят, что из процессоров такого рода будут собирать реальный эмулятор работы человеческого мозга.

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

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

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



Вернемся в 1970-е годы. После успехов Розенблата следующим видным специалистом в области развития ИИ стал Марвин Мински. Вместе со своим коллегой Папертом он написал книгу «Perceptrons», которая показала принципиальные ограничения перцептронов. Косвенным образом эта работа способствовала наступлению «зимы» ИИ (1970-е и 1980-е годы), когда возникло очень много сомнений о возможностях создания полноценного ИИ на основе нейросетей.

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



Leon A. Gatys et al./ arXiv.org

В 2016 г. новости о достижениях нейронных сетей стали появляться чуть ли не каждую неделю. Коллектив ученых из Германии разработал искусственную нейронную сеть, позволяющую «синтезировать» изображение из двух независимых источников: одно из них дает только содержание, другое — только стиль. Нейросеть научилась реалистично раскрашивать черно-белые снимки. Нейросеть научили ставить геотег на снимки еды и котиков. Нейросеть стала вычислять смешные картинки. Ну и так далее.

Новый прорыв: AlphaGo


Игра Го всегда была крепким орешком для ИИ. Скептики утверждали, что программы в го либо никогда не победят, либо одержат победу очень нескоро. Го сложнее шахмат в 10100 раз — именно в столько раз больше возможных позиций камней на стандартной доске 19×19, чем в шахматах.

Прорыв удалось совершить в программе AlphaGo благодаря алгоритму Монте-Карло-поиска по игровому дереву, управляемому двумя нейронными сетями, обученными на основе большого массива игр профессиональных игроков в го. Вначале AlphaGo выиграла у чемпиона Европы, затем победила Ли Седоля, одного из сильнейших (возможно, самого сильного) игроков мира.

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

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



Изображение: The Atlantic.

В AlphaGo одна из нейронных сетей (value network) используется для оценки позиций в терминальных узлах дерева поиска, другая (policy network) предназначена для умного отбора ходов-кандидатов. Также используется небольшое дерево перебора Монте-Карло. В каждом узле рассматривается 1-2 хода, средний коэффициент ветвления — меньше двойки. Благодаря этому стало возможным посчитать осмысленное дерево с очень ограниченным числом вариантов, и за счет этого найти действительно сильнейший ход в позиции.

Сначала AlphaGo тренировалась на партиях сильнейших игроков в го. В качестве входных данных для обучения использовались 160 тыс. игр с 29, 4 млн позиций. С момента, когда она стала играть не хуже обычных людей, корпус для тренировки нейронной сети или для постройки параметров оценочной функции стал генерироваться автоматически. Программа начала играть сама с собой, добавляя новые партии в обучающую выборку.

Угрозы и перспективы: плохой, хороший и очень хороший сценарий


Изображение: TechRadar.

Разные страхи, связанные с искусственным интеллектом, вызваны несколькими проблемами. Люди боятся самих себя, боятся допустить ошибку при создании ИИ — вдруг он будет вести себя не совсем так, как мы хотим. Представьте такую гипотетическую ситуацию: машине долго объясняют, что бывают грибы съедобные и несъедобные, и ядовитые грибы смертельны для человека. Дальше машине задается вопрос: любые ли грибы может есть человек? «Конечно любые, — отвечает машина. — Но некоторые только один раз в жизни».

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

Знакомые страхи? Однако эта история непосредственного отношения к ИИ не имеет — мы говорим лишь о том, что люди сами себе не доверяют. Мы боимся не только того, что развитый разум окажется злым. Он может оказаться и добрым, захочет нести людям добро, но увидит это «добро» по-своему.

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

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



Изображение: Plague Inc.

В XXI в. технологическая мощь такова, что для воплощения апокалиптичных сценариев не требуется большое количество фигурантов. Допустим, биохимическая лаборатория создает убийственный вирус. Быстро защищаться от вирусов мы не умеем. Не исключено, что не так уж сложно сделать заразу, которая будет одновременно очень вирулентна, имея соответствующие фрагменты из вируса гриппа, и в то же время на 100% летальна, получив часть, например, из Эболы. Для воплощения такого проекта хватит нескольких десятков образованных безумцев.

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

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

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

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

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

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

Последние слова: ИИ как личность


Изображение: Machine Overlords

Возможно ли самосознание у искусственного интеллекта?

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



Зеркальные нейроны могут быть задействованы в освоении новых навыков путем имитации.

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

Если данная теория верна, то схожим образом, через побочные эффекты, возможно развитие искусственного интеллекта, неизбежно вырабатывающего у себя самосознание. Если нам потребуется, чтобы ИИ мог спрогнозировать поведение других ИИ или людей, у него появится модель для прогноза действий, и рано или поздно он применит эту модель к самому себе. Осознание — неизбежное следствие развития сложно организованной интеллектуальной системы.

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



Что касается копирования сознания на электронный носитель, то в этой истории тоже не все однозначно. Английский ученый Роджер Пенроуз утверждает, что человеческое сознание не является алгоритмическим, и в силу этого не может быть смоделировано с помощью обычного компьютера типа машины Тьюринга. По мнению Пенроуза, сознание связано с квантовыми эффектами, а значит, принцип неопределенности Гейзенберга не позволит получить точный снимок электронной активности мозга. Поэтому наше сознание, скопированное в машину, не будет точной копией. Большая часть исследователей с этим мнением не согласна, считая, что пороги сигналов в мозге очень далеки от квантового уровня.



Метод опорных векторов в машинном обучении был предложен Владимиром Вапником в 1995 г.

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

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

Можно ли сделать универсальный ИИ не на нейронных сетях? Of course! Просто мы начинаем с бионического подхода. Вначале пробуем улучшить то, что есть сейчас, а затем будем искать более совершенные методы.

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

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

Источник: geektimes.ru/company/mailru/blog/277064/