Шахматы и машинное обучение
В процессе изучения "Искусственного интеллекта" и "Машинного обучения" узнаёшь много нового. В частности, мне удалось познакомиться с довольно интересным способом создания игровых программ. В принципе, любой человек, обладающий мало-мальскими знаниями математики и программирования, способен создать серьёзную программу для игры, скажем, в шахматы.
Шахматы моделируются в программе как процесс перехода между состояниями, где каждое состояние - это позиция на доске. Действия программы и её оппонента меняют позицию и переводят игру в новое состояние. Цель - поставить мат. Итак, как создать идеальную шахматную программу?
1. Необходимо ввести понятие позиции как состояния, задать правила перехода между ними (допустимые ходы фигур). Необходимо задать начальую позицию и задать правила, по которым определяется ничья или победа одной из сторон.
2. Далее необходимо реализовать простой алгоритм выбора следующего хода в текущей позиции, где ход выбирается так, чтобы оценка получающейся при этом позиции оказалась максимальной . Необходимо реализовать просчитывание дерева вариантов вглубь до разумных пределов (3-4 хода). При движении по дереву для себя выбираются ходы, максимизирующие оценку позиции, а для противника - минимизирующие её. Изначально все позиции имеют оценку 0. Исключение имеют позиции выигрыша (оценка 1), ничьи (-1) и проигрыша (-3). Эти числа подобраны из соображений: а) начальные оценки хочется видеть целыми; б) оценка ничьи находится ровно между оценками выигрыша и проигрыша; в) нейтральная оценка находится между ничьёй и виыгрышем (чтобы программа стремилась выигрывать) и г) нейтральная оценка равна 0. Поскольку в большинстве ситуаций достижение позиций выигрыша, проигрыша или ничьи за небольшое число ходов малореально, программная система на начальном этапе своего развития будет выбирать очередной ход случайным образом.
3. Далее мы запускаем систему, и она начинает играть сама с собой. В силу случайности выбора ходов партия, скорее всего, закончится вничью из-за правила 50 ходов. Финальная позиция будет иметь, очевидно, оценку -1. Позиция, предшествующая ей, - получит оценку -1, умноженную на некоторый корректирующий коэффициент (скажем, 0.99). Позиция перед этой позицией получит оценку ещё меньше по модулю и т.д. Таким образом, каждая позиция в партии получит уже какую-то оценку.
Во время следующей партии программа будет пытаться перебрать другие ходы, так как они будут приводить к позициями с по крайней мере неотрицательной оценкой. Так программа будет старательно перебирать различные варианты начала игры.
Если позиция получает оценку вторично, нужно скорректировать первичную оценку, взяв, например, среднее значение двух оценок.
4. Позиций в шахматах очень много, и мы никогда не дождёмся, пока программа переберёт их все. Кроме того, и хранить оценку для такого числа позиций накладно. ЧТобы ускорить развитие системы и не пробегать все возможные варианты ходов, нужно определить оценку не в виде перечисления пар "позиция" => "число", а как функцию от позиции, зависящую от ряда показателей. Каких именно показателей? Тут уж в ход идёт ваша смекалка. К примеру, в качестве одного из параметров позции можно взять материальное соотношение сил на доске. Можно указать и количество доступных полей для фигур. Параметров должно быть много. Оценка же позиции представляет собой набор коэффициентов, определяющих веса этих параметров. Когда вычисляется оценка позиции, сначала вычисляются её параметры, затем они перемножаются с соответствующими коэффициентами, и результаты складываются. Полученное число и является искомой оценкой.
Собственно, в процессе развития программа и должна вычислить оптимальные значения этих коэффициентов.
Благодаря этому подходу программа сможет оценивать не только те позиции, которые они играла, но и все остальные, и это будет приближать её к наивысшей степени мастерства.
Шахматы моделируются в программе как процесс перехода между состояниями, где каждое состояние - это позиция на доске. Действия программы и её оппонента меняют позицию и переводят игру в новое состояние. Цель - поставить мат. Итак, как создать идеальную шахматную программу?
1. Необходимо ввести понятие позиции как состояния, задать правила перехода между ними (допустимые ходы фигур). Необходимо задать начальую позицию и задать правила, по которым определяется ничья или победа одной из сторон.
2. Далее необходимо реализовать простой алгоритм выбора следующего хода в текущей позиции, где ход выбирается так, чтобы оценка получающейся при этом позиции оказалась максимальной . Необходимо реализовать просчитывание дерева вариантов вглубь до разумных пределов (3-4 хода). При движении по дереву для себя выбираются ходы, максимизирующие оценку позиции, а для противника - минимизирующие её. Изначально все позиции имеют оценку 0. Исключение имеют позиции выигрыша (оценка 1), ничьи (-1) и проигрыша (-3). Эти числа подобраны из соображений: а) начальные оценки хочется видеть целыми; б) оценка ничьи находится ровно между оценками выигрыша и проигрыша; в) нейтральная оценка находится между ничьёй и виыгрышем (чтобы программа стремилась выигрывать) и г) нейтральная оценка равна 0. Поскольку в большинстве ситуаций достижение позиций выигрыша, проигрыша или ничьи за небольшое число ходов малореально, программная система на начальном этапе своего развития будет выбирать очередной ход случайным образом.
3. Далее мы запускаем систему, и она начинает играть сама с собой. В силу случайности выбора ходов партия, скорее всего, закончится вничью из-за правила 50 ходов. Финальная позиция будет иметь, очевидно, оценку -1. Позиция, предшествующая ей, - получит оценку -1, умноженную на некоторый корректирующий коэффициент (скажем, 0.99). Позиция перед этой позицией получит оценку ещё меньше по модулю и т.д. Таким образом, каждая позиция в партии получит уже какую-то оценку.
Во время следующей партии программа будет пытаться перебрать другие ходы, так как они будут приводить к позициями с по крайней мере неотрицательной оценкой. Так программа будет старательно перебирать различные варианты начала игры.
Если позиция получает оценку вторично, нужно скорректировать первичную оценку, взяв, например, среднее значение двух оценок.
4. Позиций в шахматах очень много, и мы никогда не дождёмся, пока программа переберёт их все. Кроме того, и хранить оценку для такого числа позиций накладно. ЧТобы ускорить развитие системы и не пробегать все возможные варианты ходов, нужно определить оценку не в виде перечисления пар "позиция" => "число", а как функцию от позиции, зависящую от ряда показателей. Каких именно показателей? Тут уж в ход идёт ваша смекалка. К примеру, в качестве одного из параметров позции можно взять материальное соотношение сил на доске. Можно указать и количество доступных полей для фигур. Параметров должно быть много. Оценка же позиции представляет собой набор коэффициентов, определяющих веса этих параметров. Когда вычисляется оценка позиции, сначала вычисляются её параметры, затем они перемножаются с соответствующими коэффициентами, и результаты складываются. Полученное число и является искомой оценкой.
Собственно, в процессе развития программа и должна вычислить оптимальные значения этих коэффициентов.
Благодаря этому подходу программа сможет оценивать не только те позиции, которые они играла, но и все остальные, и это будет приближать её к наивысшей степени мастерства.