О теории Мартина Гарднера

О теории Мартина Гарднера

Меня всегда интересовал принцип создания искусственного интеллекта. Играя в компьютерные игры, я отмечал довольно неплохой интеллект своих компьютерных оппонентов. Они искали укрытия, пытались выманить меня на открытое пространство (S.T.A.L.K.E.R) или же взять в клещи. В других играх была интересно представлена мирная сторона жизни. Персонажи ходили по своим делам, в церковь, погулять. Ночью они спали, а не стояли истуканами – большинство из них все время перемещались (The Elder Scrolls IV Oblivion).

Но ещё больше меня интересовали не такие глобальные проблемы, а более мелкие. Например, принцип построения интеллекта противника в игре Гомоку (Крестики и Нолики на большом поле). А недавно я прочитал статью Мартина Гарднера «Самодельная самообучающаяся машина из спичечных коробков» [1]. Принцип построения процесса самообучения машины в игре «Шесть Пешек» вызвал у меня интерес, и я решил создать подобную программу.

Для начала я бы хотел предложить интересные моменты из статьи, а потом предоставить её разбор.

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

Приведенный отрывок взят из классического рассказа Амброза Бирса “Хозяин Моксона”. Изобретатель Моксон построил робота, играющего в шахматы. После того как Моксон выиграл одну партию, робот задушил своего создателя.

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

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

В 1959 году Сэмюел создал программу, которая позволяла машине не только правильно играть в шашки, но и улучшать стратегию игры, используя опыт, накопленный в предыдущих партиях. Вначале Сэмюел с легкостью обыгрывал машину, но IBM 704 не стала душить своего программиста, а вместо этого начала быстро совершенствоваться. Вскоре она достигла такого уровня, что с блеском выигрывала у Сэмюела все партии подряд! Существует только несколько остроумных шахматных программ для обычных (несамообучающихся) машин.

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

В статье «Метод проб и ошибок» Мичи описывает самообучающуюся машину для игры в крестики и нолики, которую можно собрать из трехсот спичечных коробков. Называется эта машина MENACE (Mathbox Educable Naughts and Crosses Engine — машина из спичечных коробков, умеющая играть в крестики и нолики; menace (англ.) — угроза, опасность.))

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

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

Чтобы узнать очередной ход машины, надо встряхнуть и перевернуть коробок, затем открыть его и посмотреть, какого цвета «вершинная» бусинка, то есть бусинка, закатившаяся в вершину картонного уголка коробка; «принявшие участие» в игре коробки остаются открытыми до конца партии. Если машина выигрывает, ее поощряют, добавляя в каждый открытый коробок по три бусинки того же цвета, что и «вершинная» бусинка. Если игра заканчивается вничью, в каждый коробок добавляют только по одной бусинке (того же цвета, что и «вершинная»). Если же машина проигрывает, ее «наказывают», вынимая из каждого коробка бусинку, закатившуюся в вершину уголка. Такой метод кнута и пряника находит весьма близкие параллели в обучении животных и даже людей. Чем больше партий в крестики и нолики играет машина Мичи, тем лучше она «запоминает» выигрышные ходы и тем упорнее стремится избегать проигрышных. Это и означает, что она представляет собой хотя и очень простое, но все же самообучающееся устройство. Правда, в отличие от IBM 704, работающей по шахматной программе Сэмюела, наша «спичечная» машина не умеет анализировать сыгранные партии и разрабатывать новые «стратегические замыслы» в соответствии с накопленным опытом.

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

Поскольку вряд ли кто-нибудь возьмется за изготовление самообучающейся машины из трехсот спичечных коробков, существует игра попроще. Чтобы построить играющую в нее машину, достаточно взять всего лишь двадцать четыре коробка. Это игра в «Шесть Пешек» Построив машину и постигнув все тонкости «шестипешия» в процессе обучения ее игре, вы получите гораздо больше удовольствия.

В шесть пешек играют на доске размером 3х3 клетки. Каждый из игроков имеет по 3 пешки. Начальная позиция показана на Рис. 1.

1. 
   пешка может передвинуться на одну клетку вперед, если эта клетка пуста;
   

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

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

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

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

1. 
   М. Гарднер «Математические досуги», статья 14 «Самодельная самообучающаяся машина из спичечных коробков» - М.: «Мир», 1972.
   

Определить лучший метод в общем случае сложно. Есть методы, которые требуют вычисления производных и есть методы, которые работают без производных [3]. Методы, которые требуют вычисления производной сложнее в использовании, т.к. требуют от пользователя вычисления и задания производной.

Обычно для сравнения численных методов используется тестирование. Собирается набор тестовых задач, формулируются измеряемые характеристики решения, фиксируется алгоритм тестирования.
Цель работы: Провести исследование свойств алгоритмов поиска корня нелинейного уравнения.

Дана экспериментальная программа «КОРЕНЬ», разработанная Горновым А.Ю. Необходимо придумать методику сравнения различных алгоритмов, реализованных в программе, собрать пакет тестовых задач и провести тестирование алгоритмов по предложенной методике, а также дополнительно реализовать метод полного перебора, отсутствующий в программе [1].

Найти решение . Здесь - заданная нелинейная функция, - числа, такие, что .

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

1) Метод Перебора (Горнов А.А.)

2) Метод Хорд

3) Метод Дихотомии

4) Метод Риддера

5) Метод Ньютона

6) Метод Секущих

7) Метод Delta-Квадрат

8) Кубический Метод

9) Метод Стеффенсона

10) Метод Простых Итераций

11) Метод Брента

12) Гибридный Метод.


Алгоритм полного перебора






















да нет



1. Задать интервал поиска корня (процедура test_fx)

2. Задать точность вычислений (процедура test_fx)

3. Задать функцию (процедура f(x))

4. Задать производную функции (процедура pf(x))

5. Задать вторую производную функции (процедура p2f(x))

6. Скомпилировать исполняемый файл (test.exe)

7. Запустить счетную программу (pusk.bat)

8. Получить результат расчёта в файле result.doc
Пример. Результаты расчета для задач 1 и 2.


Методика сравнения методов.
1. За единицу берется число вычислений функции или ее производных.

2. Собран пакет тестов из 20 задач (см. приложение).

3. Точность метода будем вычислять по формуле

4. Надежность метода будем вычислять по формуле

5. Эффективность метода будет оценивать коэффициентом ускорения

6. Качество метода будем оценивать по формуле

Оценку надёжности методов см. таблицу 2

Оценку ускорения методов см. таблицу 3
Табл. 1. Таблица точности

Табл. 2. Таблица надёжности

Табл. 3. Таблица ускорения

В таблице 4 представлен результат исследования.

Названия методов	Рейтинг	Место	Место (без производных)
Перебор	1,40	11	9
Хорд	1,79	4	3
Дихотомии	1,64	8	6
Риддера	1,47	9	7
Ньютона	2,4	1	-
Секущих	1,7	6	4
Delta-Квадрат	1,42	10	8
Кубический	1,73	5	-
Стеффенсона	1,67	7	5
Простой итерации	0,53	12	10
Брента	1,94	3	2
Гибридный	2,09	2	1

1. Идеального метода для всех задач не существует.

2. Популярный метод простой итерации почти всегда работает хуже других.

3. Использование производных не обязательно.

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

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

Благодарю за внимание к моей работе: моих преподавателей Горнова Александра Юрьевича, Суржик Татьяну Николаевну, Казазаеву Анну Васильевну, а также фирму “Borland” за любезно предоставленный free-компилятор С.

1. Информатика и образование. Методическое пособие № 6. – 2003 г.

2. Мудров А.Е.. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль.- МП Раско. 1992.

3. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся вузов. - М.: Наука. 1981.

4. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир. 1980. - 279 с.
Приложение. Пакет тестовых задач.
Тест 1.

Тест 2.

Тест 4.

Тест 5.

Тест 7.

Тест 8.

Тест 9.

Тест 10.

Тест 11.

Тест 12.

Тест 13.

Тест 14.

Тест 15.

Тест 16.

Тест 17.

Тест 18.

Тест 19.

Тест 20.