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

Выполняется обучение модели на множестве данных, сохранение весов (параметров) модели и использование сохранённых параметров для быстрого принятия решений. Обучение может длиться долго и требовать больших вычислительных мощностей и множества данных; обученная модель работает быстро и на слабых компьютерах. С помощью такого подхода выявляются закономерности в данных, качество результатов напрямую зависит от объёма данных для обучения.

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

Суть игры Баше

Кратко про игру: два игрока из кучки, содержащей первоначально 11 камней, по очереди берут не менее одного и не более 2 камней. Проигравшим считается тот, кому нечего брать. Вместо камней могут быть и другие объекты, например карандаши, их количество так же может отличаться (например, 21), брать можно и больше предметов (до 3 например, максимальное количество обозначим M).

Стратегия победы в игре «Бери столько предметов, чтобы после твоего хода количество предметов было кратно (M+1)». Игра довольно простая и её исход определен после первого хода, если партнёры не делают ошибок.

Алгоритм машинного обучения для обучения компьютера игре Баше

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

Заводим 11 коробок и берём для обучения множество фишек со значениями 1 и 2.
В зависимости от того, сколько осталось камней, совершаем ход (берём 1 или 2 камня) и кладём в коробку текущего хода фишку с номером 1 или 2.
Если победили, сохраняем фишки в коробках. Если нет – не сохраняем.
Если в коробке есть фишки, случайным образом достаём из неё фишку, и берём количество камней с фишки. Если в коробке фишек нет, то берём 1 или 2 случайно.

Предполагается, что при обучении игрок всегда берет фишки случайно. Прогнав таким образом игру много раз (100 и больше) производится заполнение коробок, «компьютер» играет все лучше и лучше, так как на каждом ходу с большей вероятностью можно извлечь фишку с количеством камней из правильной стратегии. Таким образом мы не использовали жёсткого алгоритма с множеством условных операторов, а задействовали лишь аппарат теории вероятности и математической статистики. Для такой простой игры менее затратно было бы обойтись обычным алгоритмом, но при решении более сложных задач, например, распознавания образов, методы машинного обучения (а именно глубокие свёрточные нейронные сети) гораздо эффективнее в работе чем иные подходы, хотя и требуют времени и ресурсы при обучении.

Реализация алгоритма машинного обучения на Python

Для реализации был использован следующий стек технологий: Python, библиотека Numpy, пользовательский интерфейс с использованием фреймворка Kivy, база данных SQLite и библиотека SqlAlchemy для работы с ней.

На рисунке 1 приведена структура базы данных для искусственного интеллекта игры, состоящая из одной таблицы «boxes». База данных на рисунке открыта при помощи SQLiteStudio, показано несколько записей таблицы.

Рисунок 1 – База данных, в которой реализован интеллект игрока

Таблица boxes содержит три столбца: boxesId (уникальный идентификатор записи); boxNumber (номер коробки, от одного до одиннадцати, характеризующий остаток камней в куче) и stoneNumber (количество камней в коробке, от одного до двух).

Работа с базой данных осуществляется с использованием трёх классов. В начале создан класс Base, представляющий собой фабричную функцию, которая создаёт базовый класс для декларативных определений классов.

from sqlalchemy import MetaData, create_engine
from sqlalchemy.ext.declarative import as_declarative
from sqlalchemy.orm import sessionmaker, scoped_session, Query, Mapper


def _get_query_cls(mapper, session):
    if mapper:
        m = mapper
        if isinstance(m, tuple):
            m = mapper[0]
        if isinstance(m, Mapper):
            m = m.entity

        try:
            return m.__query_cls__(mapper, session)
        except AttributeError:
            pass

    return Query(mapper, session)


Session = sessionmaker(query_cls=_get_query_cls)
engine = create_engine('sqlite:///smart_warehouse.db', echo = True)
metadata = MetaData(bind=engine)
current_session = scoped_session(Session)


@as_declarative(metadata=metadata)
class Base:
    pass

Для отображения таблицы boxes создан класс Boxes, содержащий поля, аналогичные столбцам в базе. Класс является наследником Base, реализация с использованием SQLAlchemy приведена ниже.

import sqlalchemy as sa

from .base import Base

class Boxes(Base):
    __tablename__ = 'boxes'

    boxesId = sa.Column(sa.Integer(), primary_key=True)
    boxNumber = sa.Column(sa.Integer)
    stoneNumber = sa.Column(sa.Integer)

Класс, в котором реализованы все функции для подключения к базе, созданию таблиц, извлечения информации из них и добавление новых записей назван SQLDataBase. Подключение к базе выполняется с помощью движка engine, при создании которого указывается строка подключения: engine = сreate_engine('sqlite:///' + nameOfDatabase + '.db', echo = True).

Константы, существующие в программе (название БД nameOfDatabase1; переменная plInitial для ответа на вопрос, нужно или нет создавать базу данных и первоначальные записи в ней; первоначальное количество камней numberOfBoxes; список возможного количества камней для изъятия во время хода stonesList; переменная idPlayerWin, хранящая порядковый номер игрока, чей ход идёт в настоящее время; количество игр для обучения epochsOfTraining) хранятся в файле appEnvironment.

Метод класса SQLDataBase для создания базы данных и таблицы в ней назван tableCreate, метод для создания сессии (session), через которую отображаются объекты базы – createSession.

def tableCreate(self):
    Base.metadata.create_all(self.engine)

def createSession(self):
    self.session = sessionmaker(bind=self.engine)()

Для формирования «первичного» интеллекта игрока в SQLDataBase существует метод initRepletionDataBase, создающий 24 первоначальные записи в базу данных для возможности игры компьютером до начала собственно обучения. На каждом ходе при первоначальном «интеллекте» компьютер будет извлекать кучи 1 или 2 камня с равной вероятностью, наугад.

def initRepletionDataBase(self):
# Создание объектов в таблице Boxes
namesList = [i+1 for i in range(apEnv.numberOfBoxes)]

# Добавать в сессию
for name in namesList:
    for numberStones in apEnv.stonesList:
        typeObject = Boxes(boxNumber=name, stoneNumber = numberStones)
        self.session.add(typeObject)
self.session.commit()

Добавление записи в сессию и завершения транзакции в session существуют команды add() и commit(), используемые в initRepletionDataBase().

Выбор всех записей из базы данных и сохранение их в список выполняется с помощью функции listOfBoxesAndStonesInIt().

def listOfBoxesAndStonesInIt(self):
    # Вызов всех состояний искусственного интеллекта
    request_str = "SELECT boxNumber, stoneNumber \
                                  FROM \
                                  boxes;"
    s4 = self.session.execute(request_str)
    result_of_query = resultproxyToDict(s4)
    ciphers = []
    for a1 in result_of_query:
        #print(a1)
        ciphers.append([a1['boxNumber'], a1['stoneNumber']])
    return ciphers

Вспогательная функция resultproxyToDict, распаковывающая результат запроса из базы в список словарей формата {‘название столбца’: ‘значение’} храниться в файле supportFunctions.

def resultproxyToDict(s2):
# Функция сохранения результатов запроса в словарь
d, a = {}, []
for rowproxy in s2:
    # Для SQLAlchemy 1.4.17
    k=0
    for column in rowproxy._fields:
        value = rowproxy._data[k]
        d = {**d, **{column: value}}
        k += 1
    a.append(d)
return a

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

def addTrainingSet(self, trainingSet):
#Обучение выигрывшего игрока
for train in trainingSet:
    typeObject = Boxes(boxNumber=str(train[0]), stoneNumber=str(train[1]))
    self.session.add(typeObject)
self.session.commit()

Обучение компьютера производится на N играх – компьютеры играют друг с другом в цикле и сохраняют накопленный опыт в базу данных (на каждой игре накапливает тот игрок, который победил). Как говорилось выше, база данных содержит номера остатка камней и количество камней, которые надо взять на ходе. Делается выбор количества камней случайным образом из массива сохранённых значений для данного хода. Стратегии компьютер научился сам, на основании «опыта» множества игр. Чем больше игр, тем больше опыта и, как следствие, надёжнее стратегия компьютера.

Игрока описывает класс PlayerClass(), содержащий два статических метода: initialPlayer() для инициализации игрока (подключение к базе данных и загрузки опыта игрока) и метод selectionOfStones, позволяющий игроку сделать выбор количества камней для изъятия, в зависимости от количества оставшихся камней.

Код PlayerClass:

import numpy as np
from var1.applicationEnvironment import appEnvironment as apEnv
from var1.dataBase.sqlDataBase import SQLDataBase

class PlayerClass():
    @staticmethod
    def initialPlayer(nameOfDatabase1):
        #Фукнция инициализации игрока
        data_base1 = SQLDataBase(nameOfDatabase1)
        if (apEnv.plInitial[0] == 1):
            data_base1.tableCreate()
        data_base1.createSession()
        if (apEnv.plInitial[0] == 1):
            data_base1.initRepletionDataBase()

        # Запрос достать все из баз данных
        resultRequest1 = data_base1.listOfBoxesAndStonesInIt()
        #Интеллект игрока
        Player1 = np.asarray(resultRequest1)
        # Список для обучения игрока
        trainingSet1 = []
        return data_base1, Player1, trainingSet1

    @staticmethod
    def selectionOfStones(Player1, stoneNumber, trainingSet1):
        indexArrayOfStones = np.where(Player1[:, 0] == stoneNumber)
        ArrayOfStones = Player1[indexArrayOfStones, 1]
        idxStone = np.random.randint(ArrayOfStones.shape[1], size=1)
        pickUpStones = ArrayOfStones[0, idxStone]
        if (pickUpStones[0] > stoneNumber):
            pickUpStones[0] = 1
        trainingSet1.append([stoneNumber, pickUpStones[0]])

        return trainingSet1, pickUpStones

В методе selectionOfStones выбираются записи из таблицы Boxes (сохранены в двумерном массиве Player1, где в строках хранятся пары числе (‘количество оставшихся камней’, ‘сколько взять камней’), получен с помощью c помощью метода listOfBoxesAndStonesInIt() класса SQLDataBase) по параметру stoneNumber (количество оставшихся камней). Формируется массив ArrayOfStones, в котором элементами являются числа 1 или 2 (сколько взять камней). Случайным образом выбирается элемент массива pickUpStones, если он равен 2 и превышает stoneNumber, то берётся 1. Добавляется в список trainingSet1 пара значений (stoneNumber, pickUpStones), элементы trainingSet1 в случае победы игрока сохраняются в базу данных.

Приведу листинг основной функции игры (храниться в файле main), где в цикле (количество итераций равно значению epochsOfTraining) проходят игры компьютеров, по итогам которых обучаются их «интеллекты».

Код основной программы обучения игроков:

import numpy as np

from var1.applicationEnvironment import appEnvironment as apEnv

from var1.playerModel.player import PlayerClass

for iter in range(apEnv.epochsOfTraining):
    #Инициализация первого игрока
    data_base1, Player1, trainingSet1 = PlayerClass.initialPlayer(apEnv.nameOfDatabase1)
    #Инициализация второго игрока
    data_base2, Player2, trainingSet2 = PlayerClass.initialPlayer(apEnv.nameOfDatabase2)

    stoneNumber = apEnv.numberOfBoxes

    idProgress = 1
    while stoneNumber>0:
        #Основной цикл игры

        if (stoneNumber==apEnv.numberOfBoxes):
            #Кто начинает первым
            idxPlayer = np.random.randint(2, size=1)

        print(str(idProgress))
        print('Ходит игрок ' + str(idxPlayer+1))

        #Выбрать количество камней
        if (idxPlayer==0):
            trainingSet1, pickUpStones = PlayerClass.selectionOfStones(Player1, stoneNumber, trainingSet1)
        else:
            trainingSet2, pickUpStones = PlayerClass.selectionOfStones(Player2, stoneNumber, trainingSet2)

    
        print('Игрок ' + str(idxPlayer+1) + ' взял ' + str(pickUpStones[0]) + ' камней')
        stoneNumber -= pickUpStones[0]
        print('Осталось ' + str(stoneNumber) + ' камней')
        idProgress +=1
        if (stoneNumber == 0):
            if (idxPlayer == 0):
                apEnv.idPlayerWin = 1
                print('Победил первый игрок')
            else:
                apEnv.idPlayerWin = 2
                print('Победил второй игрок')

        if (idxPlayer==0):
            idxPlayer = 1

        else:
            idxPlayer = 0


    #Запись нового обучающего множества в базу данных после выигрыша
    if apEnv.idPlayerWin==1:
        data_base1.addTrainingSet(trainingSet1)
    else:
        data_base2.addTrainingSet(trainingSet2)

Исходный код приложения находится в репозитории https://gitlab.com/vadimpechenin/boshe-game-with-artificial-intelligence.git. Для игры с обученным компьютером созданы две версии: игра через командную строку (в пакете var2HumanPlayer проекта) и через GUI интерфейс (в пакете var3MobileApp проекта), созданный с использованием фреймворка Kivy. В обоих версиях логика игры остаётся одинаковой, только ходы одного из компьютеров уже делает пользователь. Приведу два основных окна из приложения на Kivy (рисунок 2).

Рисунок 2 – Окно настроек (левое) и основное игровое окно (правое)

В окне настроек можно выбирать: 1) ходить первым или вторым; 2) сложность игры (какой интеллект противника загрузить, хорошо или плохо обученный). В основном меню можно выбирать количество камней в свой ход, нажимая на кнопки «Взять 1» или «Взять 2». В итоге появляется окно, сообщающая результаты игры и предлагающее начать новую игру. Если не придерживаться выигрышной стратегии, приведённой в начале статьи, то при высокой сложности интеллекта компьютера (прошедшего 1000 эпох обучения) проигрыш человека обеспечен!

Создание искусственного интеллекта для игры Баше без нейронных сетей