Топпоиск.рф
 
ТОППОИСК.РФ Наука Математика О выборе целевой функции на примере игры «точки»

УДК
519.7

О выборе целевой функции на примере игры «точки»

Афанасьев Сергей Георгиевич,
магистр математики,
преподаватель кафедры ПИМ,
НОУ ВПО «СКСИ»,

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

The article discusses a sample scenario of computer realization of game situations, the example of the game "Points", discusses the success AlfaGo program to play at a world level in the game of Go, draws parallels between the work of neural networks and the holographic structure of thinking.

Ключевые слова: целевая функция, алгоритм игры точки, искусственный интеллект, мозг как голограмма.

Keywords: objective function, the algorithm of the game "points", artificial intelligence, the brain as a hologram.

 

«Есть длины волн, которые люди не могут видеть, звуки, которые люди не могут слышать, и может, у компьютеров есть мысли, которые люди не могут думать».

Ричард Хэмминг

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

Интерес к логическим, позиционным играм постоянен. Шахматы, шашки, Го, точки, уголки и так далее –  являются великолепным тренажёром для мозга.

Правила игры в “точки” аналогичны правилам игры Го, но более простые. Вместо камней используются точки двух цветов или форм, наносимые на бумагу в клетку. Цель игры – взять в окружение точки противника.

рис.1 Обозначение игровых фигур и ходов

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

Игра простая в силу того, что фигуры – однотипные – “точки” с одинаковыми игровыми возможностями. Существует возможность реализации “ничейной” стратегии.

Реализация алгоритма игры включает в себя следующие возможные пункты:

  1. Построение оценочной функции для игровой позиции.
  2. Алгоритм дерева перебора игровых позиций.
  3. Алгоритм обхода точек противника (алгоритм обхода точек организуется по принципу поиска выхода из лабиринта).
  4. Создание графического, лёгкого в использовании, понятного интерфейса.

Как человек делает выбор хода? Как он оценивает лучший ход? Как устроена оценочная функция?

Во-первых, существуют различные способы оценки фигур. Для шахмат простейшая оценка: пешка - 1, конь и слон - 3, ладья - 5, ферзь – 10, король – 100.

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

Примерный алгоритм выбора целевой функции:

Игровое поле представляет – пересечение горизонтального и вертикального множества прямых.

рис. 2 Игровое поле

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

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

Тогда матрица целевой функции запишется как:

(1)

После хода оценка позиции может быть следующей:

рис. 3 Игровая позиция первого хода

(2)

Возможно увеличить оценку потенциала хода, тогда:

(3)

Область игрового поля с выставленными точками обладает нулевым потенциалом.

рис. 4 Игровая позиция второго хода

Применяя принцип суперпозиции потенциала, после второго хода, целевая функция (2) перепишется как:

(3)

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

рис. 5 Игровая позиция трёх ходов

  (4)

рис. 6 Игровая позиция четырёх ходов

  (5)

рис. 7 Игровая позиция пяти ходов

(6)

рис. 8 Игровая позиция шести ходов

В матрице ходов с отрицательным знаком записывается позиция для фигур одного игрока, с положительным знаком – другого игрока.

(7)

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

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

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

Программа АльфаГо представляет комбинацию двух нейронных сетей, одна из которых ведёт позиционную оценку, другая отвечает за дерево возможных ходов. Искусственный интеллект имитирует работу цепочек нейронов мозга человека. Особенностью работы мозга является высокая скорость обработки информации, обеспечивающиеся большим числом параллельных вычислительных связей, превышающих на много параллельные вычислительные возможности современных компьютеров. На ряду, с вычислительной функцией мозг выполняет функцию хранения информации. Быстрый доступ к памяти обеспечивается как параллельностью нейронных связей, так и распределённым характером памяти. Утрированной физической моделью мышления может быть запись и считывание голограммы. Мозг как голограмма, сознание как голографическое изображение. Воспринимаемая человеком информация отдельным сегментом мозга вызывает формирование некоторого соответствующего образа, который, в свою очередь, благодаря положительной обратной связи, путём вторичных когерентных импульсов, завершает голограмму ответного образа. Мозг – огромный банк данных, накопленных и в результате опыта – сталкиваясь с новой задачей, используя распределенное свойство памяти, осуществляет поиск готового решения или же аналогичного, близкого к нему.  Современные игровые программы максимально загружают память компьютера, которая в других целях бы не использовалась, библиотеками дебютов, эндшпилей и ранее рассмотренных игровых позиций. Теперь программа может не только оценивать позицию и осуществлять перебор ходов, но и использовать готовые решения позиционных оценок. Такой подход позволяет широко использовать способность нейронных сетей к обучению.

Список литературы:

  1. Асташкин В. Нилов Г. Школа Го // Наука и жизнь. – 1975. - №8. – С. 127-129.
  2. Ивашко Е. Компьютер играет в шахматы. Часть 3. Компьютер разумный // Мир ПК. – 2008. – № 02.
  3. Круг П.Г. Нейронные сети и нейрокомпьютеры: Учебное пособие по курсу «Микропроцессоры». – М.: Издательство МЭИ, 2002. – 176 с.
  4. Ландсберг Г. С. Элементарный учебник физики: Учеб. пособие. В 3 т. / Под ред. Г. С. Ландсберга: Т. 3. Колебания и волны. Оптика. Атомная и ядерная физика. — 12-е изд. — М.: ФИЗМАТЛИТ, 2001. — 656 с.
  5. Прибрам К. Языки мозга. Экспериментальные парадоксы и принципы нейропсихологии, «Прогресс»,1975 г.
  6. http://ria.ru/science/20160127/1366087868.html#ixzz3yTkxhsse
  7. http://sci-humor.blogspot.com/2014/01/blog-post_21.html
  8. http://www.litres.ru/pages/biblio_book/?art=178747
  9. http://www.osp.ru/pcworld/2008/02/4881544/