Серия Машины, которые играют разбита на 7 частей: это 6-я часть серии.
Эта серия охватывает историю искусственного интеллекта и игр (до Deep Blue) и фокусируется на машинах, которые играли в шахматы, шашки и нарды. Рассмотрены следующие темы: как построить шахматные машины, работы Шеннона по шахматам, работы Тьюринга по шахматам, Турок, Эль-Аджедресиста, MANIAC, шахматная программа Бернштейна, шашки Самуэля, Mac Hack VI, Cray Blitz, BKG, HiTech, Chinook, Deep Thought, TD-Gammon и Deep Blue.
Часть 1: Машины, которые играют (Обзор) - эта
Часть 2: Машины, которые играют (сборка шахматных машин)
Часть 3: Машины, которые играют (Chess-Before Deep Blue)
Часть 4: Машины, которые играют (Deep Blue)
Часть 5: Машины, которые играют (сообщение Deep Blue)
Если вы хотите получить краткое изложение первых 5 частей с акцентом на человеческий фактор, перейдите сюда.
Часть 6: Машины, которые играют (шашки) - эта
Часть 7: Машины, которые играют (в нарды)
Часть 6: Машины, которые играют (шашки)
В этой части речь пойдет о шашках Сэмюэля (1950-е годы) и «Чинук» Джонатана Шеффера (1990-е годы). Шашки Самуэля были первой программой, которую нужно изучить (до того, как был изобретен ИИ). Chinook была первой компьютерной программой, выигравшей титул чемпиона мира против людей. Шеффер также решал шашки в 2007 году - это скоро.
Сложность игры
Прежде чем мы начнем, давайте рассмотрим некоторые способы измерения сложности игры.
Сложность игры в пространстве состояний - это количество допустимых игровых позиций, достижимых из начальной позиции игры.
Размер игрового дерева - это общее количество возможных игр, в которые можно играть: количество конечных узлов в игровом дереве, корень которого находится в начальной позиции игры.
Фактор ветвления - это количество дочерних элементов в каждом узле. Например, в шахматах предположим, что «узел» считается допустимой позицией, тогда средний коэффициент ветвления оценивается примерно в 35. Это означает, что в среднем у игрока на каждом ходу доступно около 35 разрешенных ходов. Для сравнения, средний коэффициент ветвления для игры Go равен 250!
Статус Оптимальный: невозможно улучшить работу (некоторые из этих записей были решены людьми)
Сверхчеловеческий: работает лучше, чем все люди.
Немного теории игр (1928–1944)
Идеальное против несовершенного
Джон фон Нейман основал область теории игр.
В 1928 году он доказал теорему о минимаксе. Эта теорема утверждает, что в играх с нулевой суммой (т. Е. Если один игрок выигрывает, то другой игрок проигрывает) с точной информацией (т. Е. В которых игроки каждый раз знают все ходы, которые были сделаны на данный момент), - пара стратегий для обоих игроков, которая позволяет каждому минимизировать свои максимальные потери, отсюда и название минимакс.
Это означает, что вы предполагаете, что ваш противник будет двигаться таким образом, чтобы максимизировать его выигрыш, а затем вы делаете свой собственный ход таким образом, чтобы минимизировать потери, вызванные ходом вашего оппонента.
Джон фон Нейман был процитирован как высказывание Насколько я понимаю, не может быть теории игр ... без этой теоремы ... Я думал, что нет ничего достойного публикации, пока не будет доказана теорема о минимаксе .
Шахматы, покер или любая другая игра для двух игроков с одним победителем и одним проигравшим может считаться игрой с нулевой суммой.
История Minimax восходит к статье 1913 года, написанной Эрнстом Цермело, отцом современной теории множеств. Статья содержала несколько ошибок и неправильно описывала минимакс. Однако он предложил (но не доказал) то, что стало известно как теорема Цермело: в любой конечной детерминированной (то есть в которой шанс не влияет на процесс принятия решения) существует идеальная информационная игра двух игроков (например, шахматы). есть три возможности: либо первый игрок может принудительно выиграть, либо второй игрок может принудительно выиграть, либо оба игрока могут принудительно сыграть вничью. Применительно к шахматам теорема Цермело гласит: либо белые могут добиться победы, либо черные могут добиться победы, либо обе стороны могут добиться как минимум ничьей. Мы (пока) не знаем, что это за шахматы. (Шашки, с другой стороны, решены: любой игрок может форсировать ничью.)
Улучшение минимаксной процедуры
Фон Нейман улучшил теорему Цермело о минимаксе, включив в нее игры с несовершенной информацией и игры с более чем двумя игроками. В 1944 году Джон фон Нейман и Оскар Моргенштерн опубликовали Теорию игр и экономического поведения. Это революционная книга, которая создала область исследований в области теории игр. Первоначально теория игр относилась к играм с нулевой суммой, но с тех пор она стала применяться к широкому кругу поведенческих отношений и стала основой для моделирования сценариев, в которых существует конфликт интересов между участниками.
Что значит сказать, что игра идеальна? Каждый игрок имеет полное представление о состоянии игры. В играх для двух игроков они ходят по очереди. Примеры: шахматы, шашки, Connect-Four, Go, Othello.
Что значит сказать, что игра несовершенная? Некоторые сведения о состоянии игры скрыты. Примеры: покер, бридж.
Что значит сказать, что игра недетерминирована? Игра включает в себя элемент случайности. Пример: нарды (с броском кубиков)
Теперь поговорим о машинах.
AI перед AI (1952–1962)
Шашки Самуэля
Игра: Шашки
IBM 701 - первый крупный коммерческий компьютер
В 1949 году Артур Самуэль присоединился к лаборатории IBM в Покипси, а в 1952 году он запрограммировал первый крупный компьютер IBM - IBM 701 - для игры в шашки. Это была первая игровая программа, запускаемая на компьютере - это была первая программа для шашек.
24 февраля 1956 года Артур Самуэль продемонстрировал программу и сыграл в шашки по телевидению. Перед демонстрацией Томас Дж. Уотсон-старший, основатель и президент IBM, предсказал, что демонстрация произведет сильное впечатление - и Это подняло бы стоимость акций IBM на 15 пунктов. Это было!
[Примечание. См. Видео под названием Компьютерные пионеры: разработка IBM 701: «Компьютерные пионеры - это устный видео-проект, созданный Ричардом Джеем Соломоном. В этом сегменте серии обсуждается разработка компьютера модели IBM 701, также известного как Defense Calculator, в начале 1950-х годов. Эти интервью были проведены 12 июля 1983 г., и в них приняли участие несколько членов команды разработчиков IBM 701, включая Джерриера Хаддада, Кларенса Фриззелла, Натана Рочестера и Ричарда Уэлена. ”]
Шашки Самуэля: первая машина, которой предстоит научиться
К 1955 году Сэмюэл сделал нечто революционное; он создал программу, которая могла учиться - чего еще никто не делал - и это было продемонстрировано по телевидению в 1956 году.
Сэмюэл думал о машинном обучении с тех пор, как присоединился к IBM, и хотел сосредоточиться на создании программ, которые могли бы научить играть в шашки. В 1959 году он ввел термин машинное обучение как область обучения, которая дает компьютерам возможность учиться без явного программирования. Позже он сказал: Я был настолько заинтригован этой общей проблемой написания программы, которая, казалось бы, обладала интеллектом, что она занимала мои мысли почти в каждую свободную минуту на протяжении всего периода моей работы в IBM и действительно, еще на несколько лет вперед .
В 1959 году он опубликовал основополагающую статью под названием Некоторые исследования машинного обучения с использованием игры в шашки, где он говорил о том, как машина может заглядывать вперед , оценивая полученные позиции на доске так же, как это мог бы сделать игрок-человек . Компьютер начал проигрывать Сэмюэлю и в конце концов победил Самуэля.
Он запрограммировал « цифровой компьютер на поведение, которое, если бы это сделали люди или животные, было бы описано как вовлекающее процесс обучения. »
Фактически, программа превзошла своего создателя, и она сделала это, обучившись за относительно короткий промежуток времени: «компьютер можно запрограммировать так, чтобы он научился играть в лучшую игру. шашек, в которые может играть человек, написавший программу. Кроме того, он может научиться делать это за очень короткий период времени (8 или 10 часов машинного времени). »
Представьте себе это:
8 утра: твоя компьютерная программа плохо разбирается в шашках. Вы научите его играть.
9 утра: вы оставляете его в покое и позволяете ему играть сам по себе весь день.
Он играет против себя и учится на своих ошибках.
18:00: Вернись и сыграй это. Это тебя бьет.
И это было в 1950-х годах - с медленными компьютерами того времени. В каком-то смысле это первое представление о том, что ждет впереди в играх: независимо от того, какова скорость улучшения для людей, как только машины научатся учиться, будет трудно угнаться за машинами, прогресс которых в конечном итоге будет измеряться. экспоненциально. А у нас нет.
Независимо от того, какова скорость улучшения для людей, как только машины научатся учиться, будет трудно угнаться за машинами, прогресс которых в конечном итоге будет измеряться экспоненциально. А наши - нет.
Безумно необъятные деревья поиска (решение: альфа-бета обрезка)
Мы знаем (из работы Шеннона, описанной в Machines That Play (Chess), что основным драйвером машины, которая играла в игры, было дерево поиска набора всех возможных позиций на доске, достижимых из текущего состояния.
Шашки чрезвычайно сложны - в них есть примерно 500 миллиардов миллиардов возможных позиций (5 x 10²⁰). Примерно 10 возможных позиций на доске по сравнению с шахматами (10) или го (10)). Несмотря на то, что шашки проще, чем эти игры, они все же достаточно сложны, чтобы подход, основанный только на грубой силе, был непрактичным.
В своей статье Самуэль сказал, что «на нынешнем уровне знаний единственный практический подход, даже с помощью цифрового компьютера, будет заключаться в разработке эвристики, которая имеет тенденцию подражать человеческому поведению. «
Программа Самуэля была основана на минимаксной стратегии Шеннона, чтобы найти лучший ход из данной текущей позиции.
Напомним, что в играх для двух игроков алгоритм минимакса определяет лучший ход - минимакс - это рекурсивный алгоритм, и он выбирает оптимальный ход на основе предположения, что оба игрока играют оптимально. Проще говоря, он пытается смоделировать то, что мы делаем, когда играем: мы думаем: «Если я сделаю этот ход, тогда мой противник сможет сделать только эти ходы, тогда я сделаю этот ход…»
Проблема с алгоритмом полного минимаксного поиска заключается в том, что он исследует все части дерева, включая те части дерева, которые ему не нужны. Другими словами, учитывая позицию на доске, специалисты-люди склонны «знать», что некоторые ходы неуместны, а некоторые - хороши. Они не исследуют все ходы, они заранее исключают ненужные или плохие.
Эмпирические правила, которые используют специалисты-люди для исключения неверных ходов, называются эвристикой. В играх реализована эвристика, чтобы сократить время вычислений. (Простой) пример эвристики в шахматах: если ход приводит к мату королем игрока, алгоритм не должен смотреть дальше по этому пути, потому что игрок никогда не захочет сделать этот ход. Нет смысла исследовать эту ветвь - это пустая трата драгоценных вычислительных ресурсов, но простой минимаксный поиск все равно будет исследовать этот путь. Alpha-beta prunin не будет исследовать этот путь.
Чтобы решить проблему сложности, Самуэль реализовал альфа-бета-отсечение - вместо того, чтобы искать каждый путь к концу игры, Самуэль разработал функцию подсчета очков, основанную на положении доски в любой момент времени.
Альфа-бета обрезка - это оптимизация минимакса. В данном узле n, если у игрока есть лучший выбор a (в узле выше), то n не будет достигнуто. Посмотрев на некоторых преемников n, мы можем узнать о n достаточно, чтобы исключить его. Идея состоит в том, что алгоритм будет поддерживать два значения: альфа и бета, где альфа представляет собой минимальный балл, который гарантирован максимизирующему игроку, а бета - максимальный балл, который гарантирован минимизирующему игроку. Оба игрока начинают с наихудшим результатом: альфа - отрицательная бесконечность, а бета - положительная бесконечность. Итак, когда обрезать? Что ж, каждый раз, когда бета (максимальный балл, который гарантируется минимизирующему игроку) становится меньше или равен альфа (минимальный балл, который гарантирован максимизирующему игроку) (или когда альфа становится больше или равна бета), максимизирующий игрок может обрезать эти узлы. Таблица ниже объясняет это:
Алгоритм альфа-бета дает тот же результат, что и алгоритм минимакса, но более эффективен, поскольку целые ветви могут быть исключены из процесса поиска. Это позволяет программе гораздо глубже оценивать минимаксное дерево поиска, используя те же ресурсы. Эта комбинация минимаксного алгоритма и альфа-бета-отсечения значительно уменьшила общее количество ветвей дерева, что сделало возможным играть в игры на компьютере. Вот основная идея (часто упоминаемая):
«Если у вас есть определенно плохая идея, не торопитесь, чтобы увидеть, насколько она ужасна». - Пэт Уинстон
Знакомство с машинным обучением
Помимо минимаксного и альфа-бета-отсечения, Самуэль использовал принципиально новый и важный компонент: обучение. Он использовал два основных метода обучения для создания первой компетентной программы ИИ: а) механическое обучение и б) обучение путем обобщения.
Механическое обучение означало, что программа сохраняла все позиции доски, встреченные во время игры, вместе с их счетами. Затем, когда эти ходы необходимо оценить дальше по дереву, на них можно будет просто ссылаться, а не оценивать, что сэкономит некоторое время вычислений. Несмотря на то, что это не была продвинутая форма обучения, идея состоит в том, чтобы программа использовала сэкономленное время для более глубоких вычислений. А механическое обучение приводило к медленным, но непрерывным улучшениям, которые были наиболее эффективны для дебютов и эндшпилей.
Обучение путем обобщения означало изменение функции оценки на основе предыдущих игр, сыгранных программой. Это было новаторским, поскольку показало, что программа может учиться, играя с предыдущими версиями самой себя (что было бы ключевым аспектом AlphaGo). Этот метод обучения ближе всего подошел к технике обучения с подкреплением, позже получившей название обучения с разницей во времени (TD-Lambda), согласно которой ценность состояния должна равняться значению вероятных следующих состояний. (Замечание: концептуально метод Сэмюэля был таким же, как тот, который много позже использовал Тесауро в TD-Gammon.) Версия, использующая обобщенное обучение, смогла разработать хорошую среднюю игру, но оставалась слабой в дебютной и эндшпильной игре. Позже в этой серии мы увидим, как некоторые из наиболее успешных программ решают эти проблемы.
Самуэль выполнял свою работу, несмотря на низкую вычислительную мощность в тот период, работая в основном в одиночку и занимаясь собственным программированием. Принципы машинного обучения, проверенные программой «экспериментами, конечно, применимы ко многим другим ситуациям». Сегодня нет ни одной области, не затронутой машинным обучением.
Последовательные улучшения, сделанные Сэмюэлем, позволили компьютеру улучшиться и достичь хороших навыков - он в конечном итоге победил Самуэля, но все равно не смог стабильно побеждать экспертов.
Но он победил опытного игрока Роберта Нили, однако есть споры о том, проиграл ли Нили игру, когда была доступна ничья (то есть он играл плохо), или программа Сэмюэла выиграла (то есть сыграла хорошо).
В следующем году матч-реванш из шести матчей был выигран Нили со счетом 5–1.
Шашки Самуэля продемонстрировали, что компьютер можно запрограммировать так, чтобы он научился играть в игру лучше, чем его создатель. Он мог улучшить свою производительность, делая то, чего не могли люди, - играя в тысячи игр против самого себя, чтобы практиковаться.
Это было грандиозным достижением для своего времени. Но сам Самуэль не питал иллюзий относительно силы своей программы искусственного интеллекта. Несмотря на то, что это важный этап в развитии искусственного интеллекта, средства массовой информации раздули его до предела. Некоторые сказали: Эта работа создала ложное впечатление, что шашки - это« решенная игра. В результате исследователи перешли к шахматам и больше 25 лет игнорировали шашки ».
Работа Сэмюэля, хотя и является новаторской сама по себе, могла ограничить исследования Checks до 1989 года, когда Джонатан Шеффер начал работу над Chinook.
В 1990 году Шеффер связался с Самуэлем, чтобы рассказать ему о значительных улучшениях в его программе, но Самуэль только что умер. Это был конец одного из основателей, который дал нам первое представление о машинном интеллекте.
На мили впереди самых сильных игроков-людей
Чинук (1989–1996)
Игра: Шашки
Чинук встречает человека - дубль 1
Он действительно человек или сверхчеловек?
Шел 1991 год. Марион Тинсли согласилась на товарищеский матч по шашкам с Чинук. Тинсли был лучшим игроком в шашки в мире на протяжении 40 лет. Относительно Тинсли было сказано, что он проверял, чем был Леонардо да Винчи для науки, кем был Микеланджело для искусства и чем Бетховен был для музыки.
После работы Самуэля над шашками сложилось ложное впечатление, что шашки - это« решенная игра». В результате исследователи перешли к шахматам и в основном игнорировали шашки, пока Джонатан Шеффер не начал работать над Chinook в 1989 году. Целью Шеффера было разработать программу, способную победить лучшего игрока в шашки.
В 1991 году Чинук играл лучшего игрока всех времен, Тинсли. Все первые девять игр они сыграли вничью. В десятой партии Чинук сделал ход, который, по его мнению, был немного выгодным. Увидев это, Тинсли заметил: Вы пожалеете об этом. В интервью Шеффер сказал. И в то время я подумал, какого черта он знает, что может пойти не так? Оказалось, что Тинсли начал вырываться вперед, и Чинук подал в отставку. Шеффер сказал (о Тинсли): В своих примечаниях к игре он позже написал, что видел до конца игры и знал, что выиграет.
После игры, когда Шеффер заглянул в базу данных, он обнаружил, что от этого хода до конца игры, если обе стороны играли идеально, он каждый раз проигрывал. Но чтобы увидеть это, компьютер или человек должны были бы смотреть на 64 шага вперед. Тинсли, похоже, выбрал единственную стратегию, которая могла бы победить Чинука с этого момента - Тинсли смог увидеть победу на 64 хода вперед.
Я был совершенно ошеломлен, - сказал Шеффер.
« Как вы можете соревноваться с кем-то, чье понимание игры настолько глубокое, что он сразу же понимает по опыту, знаниям или удивительным поискам, что он выиграет эту позицию? »
Чинук встречает человека - дубль 2
Это только вопрос времени
Чинук и Марион Тинсли снова встретились в 1992 году на чемпионате мира по человеко-машинному спорту. Это был первый раз в истории, когда человек играл на компьютере за титул чемпиона мира.
Из-за величия Тинсли большинство игроков играло с Тинсли осторожно, надеясь на ничью. Однако Чинук вел совсем другую игру. Относительно того, как играл Чинук, Шеффер сказал, Он делал дерзкие, агрессивные ходы - он шел по краю пропасти… Он делал то, на что люди смотрели и говорили:« Чувак, эта программа сумасшедшая? em> '”
Хотя Чинук проиграл Тинсли, он был близок к победе над Тинсли. Он провел потрясающую восьмую игру и выиграл; это была шестая потеря Тинсли за 40 лет.
Согласно The Atlantic, Шаффер опечалился о потере Тинсли и позже написал в этой книге:
« Мы по-прежнему являемся представителями человеческой расы, и победа Чинука Тинсли в одной игре означает, что это будет лишь вопросом времени, когда компьютеры станут главенствующими в шашках, а в конечном итоге и в других. такие игры, как шахматы. ”
Но это была не просто одна одиночная игра. Чинук снова выиграл в 16-й игре. Ни один из ныне живущих игроков не побеждал Тинсли более одного раза. Тинсли проиграл всего семь игр за всю свою 45-летнюю карьеру, две из них - Чинуку.
Наконец, машина становилась более совершенной.
Но у Чинука была какая-то ошибка, из-за которой Шаффер отказался от игры. Шеффер был опустошен.
Чинук встречает человека - дубль 3
Утрата своей божественной поддержки
В 1994 году Чинук, победив другого игрока, был готов снова встретиться с Тинсли. Scientific American сообщил, «В ночь перед матчем
… Тинсли приснилось, что Бог говорил с ним и сказал: «Мне тоже нравится Джонатан», что привело его к мысли, что он, возможно, потерял исключительную божественную поддержку. »
Чинук не проиграл ни одной игры за последние 125 игр, а с 1992 года команда Шеффера потратила тысячи часов на улучшение Чинука.
Перед матчем у Тинсли болел живот. В день матча снова было больно. После шести игр, все из которых были ничьи, ему потребовалось обратиться к врачу, поэтому Шеффер отвез его в больницу. На следующий день Тинсли сказали, что у него на поджелудочной железе опухоль - у него рак поджелудочной железы. Он удалился.
Дон Лафферти, занимавший в то время второе место в рейтинге игроков в мире, заменил Тинсли и стал играть против Чинука. Chinook выиграл и стал первой компьютерной программой в истории, выигравшей чемпионат мира среди людей. Семь месяцев спустя Тинсли умер.
Программе Шеффера никогда не удавалось обыграть лучшего игрока в шашки - и именно поэтому он начал все это в 1989 году. Лучший игрок-человек никогда по-настоящему не проигрывал ни одного матча Чинуку. К концу 1980-х годов программы для шашек стали более продвинутыми. Чинук сыграл свой последний турнир в 1996 году, где Чинук финишировал на много миль впереди сильнейших игроков чемпионата США.
Но для Шеффера этого было недостаточно. Ему нужно было убедиться, что его программа может побить лучшего игрока на свете.
Люди почти идеальны. «Но моя компьютерная программа идеальна».
С 1997 по 2001 год Шеффер дисквалифицировал Чинука и начал работать над решением игры в шашки, что означало, что его программа всегда знала правильный ход. Было бы идеально.
В интервью Scientific American Шеффер сказал: С конца саги Тинсли в 94–95 годах до 2007 года я упорно работал над созданием идеальной программы для шашек. Причина была проста: я хотел избавиться от призрака Марион Тинсли. Люди говорили мне: «Ты никогда не смог бы победить Тинсли, потому что он был совершенен.
«Что ж, да, мы бы обыграли Тинсли, потому что он был почти идеален. Но моя компьютерная программа идеальна. ”
В 2007 году Шеффер и его команда опубликовали статью в журнале Science под названием Checkers Is Solved: программа больше не могла быть побеждена кем-либо, ни человеком, ни кем-либо еще.
«Восемнадцать лет спустя я, наконец, закончил». сказал Шеффер.
Решение шашек (2007)
Игра: шашки
В 2007 году создатели Chinook опубликовали статью в журнале Science, в которой объявили, что Chinook полностью решила Checkers: программа больше не может быть побеждена кем-либо, человеком или кем-либо еще. Джонатан Шеффер и его команда работали над решением проблемы шашек с 1989 года. В статье говорилось: … шашки теперь решены: идеальная игра обеих сторон ведет к ничьей. Это самая сложная и популярная игра, которую предстоит решить на сегодняшний день, примерно в миллион раз сложнее, чем Connect Four. «Шашки - самая крупная игра, которая была решена на сегодняшний день, с пространством поиска 5 × 10²⁰. «Количество расчетов составило« 10¹⁴ , которые были выполнены за 18 лет. Процесс включал от 200 настольных компьютеров на пике до 50 ».
Скоро в продаже
