НейроБашня

В 94-м проекте мы построим робота, который будет играть с нами в известную игру "11 палочек". В этот раз мы снова коснемся темы нейросетевых технологий. Нейронная сеть робота сможет обучаться как в результате игры с человеком, реагируя на его стратегию, так и в результате "игры в уме", играя в памяти с себе подобной сетью.

Суть игры такова: в кучке 11 палочек, два игрока ходят по очереди. За каждый ход можно взять 1 или 2 палочки. Выигрывает тот, кто взял последнюю палочку.

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

В этот раз мы построили конструкцию из старого доброго LEGO Mindstorms NXT. Это связано с тем, что параллельно с Python мы изучаем C/C++, а для платформы NXT есть замечательная свободно распространяемая среда разработки BricxCC, Си-компилятором в которой мы и воспользуемся для программирования робота.

Инструкцию по сборке нашего робота в формате LEGO Digital Designer можно скачать по ссылке. В конструкции мы используем средний EV3-мотор в силу его компактности, однако вам ничего не помешает использовать NXT-мотор, изменив способ его крепления, изменений в коде это не потребует.

Робот может работать в двух режимах:

• Игра на двоих. В этом режиме играют два человека. В башню заряжено 11 лего-кубиков. Игроки по очереди нажимают 1 или 2 раза на кнопку со своей стороны, забирая себе 1 или 2 кубика. Выигрывает игрок, который забрал последний кубик.
• Игра человека против нейронной сети робота. В этом режиме игрок использует правую кнопку, за левого игрока думает робот.

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

Так как у нашего робота 11 состояний (по количеству оставшихся кубиков в башне), представим 11 коробков, в каждом из которых в начале игры по 1 камню белого и черного цветов. Когда наступает ход нейронной сети, она "смотрит" сколько кубиков осталось в башне и выбирает соответствующий коробок, затем наугад вытаскивает из него камень. Если он белый - она берет 2 кубика, если черный, то 1 кубик, при этом запоминая сколько она взяла в каждый ход. После того как камень вытащен и его цвет определен, он помещается назад в коробок.
По окончанию игры наступает пора поощрений и наказаний:

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

Этот способ был опубликован в серии книг «Берсеркер» (издавались в рамках «Боевая фантастика») Фреда Саберхагена в 1995 году. По сюжету, главный герой должен был замаскировать своё отсутствие на космокорабле. Он обучил методу «спичечных коробков» свою мартышку, которая и имитировала игру с жутким космическим монстром. 

Ранее, в 70-x годах задача «Самообучающаяся машина из спичечных коробков» была опубликована известным математиком Мартином Гарднером в книге "Математические досуги".

В самом начале игры наша нейронная сеть не обучена, ее ходы случайны, как как в каждом "коробке" у нее 50% белых и 50% черных камней. Каждый такой коробок - это нейрон сети.

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

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

Третьим способом, который мы применили, явилось создание еще одной нейронной сети и проведение непрерывной последовательности фоновых игр между сетями. Обе сети обучаются одновременно, по каждый ведется статистика побед.. Этот способ оказался самым эффективным, правда удвоенная вычислительная нагрузка снизила количество фоновых игр (теперь их 70-80 в секунду), однако качество обучения заметно выросло.

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

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

Исходный код программы приведен ниже. Скачать программу можно по ссылке. Мотор подключается в порт А, датчики кнопки - в порты 1 и 2. Чтобы озвучить игры мы записали набор звуков в формате RSO, которые нужно поместить в память робота, их вы тоже найдете по ссылке.

//время ожидания второго нажатия
long timeToPress=0;

//переменные с количеством выигрышей нейросетей
long winNN1=0;
long winNN2=0;

//количество игр NN против NN (здесь и далее NN - нейросеть)
long game=0;

//сколько осталось кубиков в игре с человеком
int box1 = 0;
//сколько осталось кубиков в игре NN с NN
int box2=0;

//win это переменная обозначает чей-то выйгрыш
//win2 это тоже самое, только в подпроцессе  learn
int win1=0;
int win2=0;

//7 строк обозначают 7 строк экрана, мы в них храним то, что надо вывести
string line1,line2,line3,line4,line5,line6,line7;

//buttonPress это количество нажатий на кнопку
int buttonPress=0;

//ошибка и старая ошибка PD-регулятора
int ERR = 0;
int ERRo=0;

//управляющее воздействие
int u = 10;

//коФф-ты PD регулятора
float P = 0.5;
float D = 1.5;

//точка, которой мы хотим достичь при повороте мотора
int target=0;

//время для поворота влево или вправо
long timeToMove=0;

//два массива пуговиц NN1
int white1[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int black1[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

//два массива пуговиц NN2
int white2[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int black2[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

//три временных массива 2 для learn и 1 для main
int tmp1[11];
int tmp2[11];
int tmp[11];

//блок для поворота по регулятору налево
sub Left (int raz)
{
  //устонавливаем точку, которой хотим достичь
  target=MotorRotationCount(OUT_A)+360*raz;

  //засекаем время
  timeToMove=CurrentTick();

  //цикл, работоющий пока мы не достигнем точки или времени
  while(abs(MotorRotationCount(OUT_A)-target)>5 && CurrentTick()-timeToMove < 1000){
    //с помощью регулятора подаем нагрузку на мотор
    ERR=target-MotorRotationCount(OUT_A);
    u=P*ERR+D*(ERR-ERRo);
    if(u>100)u=100;
    if(u<-100)u=-100;
    OnFwd(OUT_A,u);
    ERRo=ERR;
  }

  //выключаем мотор
  Off(OUT_A);
}

//блок для поворота по регулятору направо
sub Right(int raz)
{
  //устанавливаем точку, которой хотим достичь
  timeToMove=CurrentTick();
  
  //засекаем время
  target=MotorRotationCount(OUT_A)-360*raz;

  //цикл, работающий пока мы не достигнем точки или времени
  while(abs(MotorRotationCount(OUT_A)-target)>5 && CurrentTick()-timeToMove < 1000){
    //с помощью регулятора подаем нагрузку на мотор
    ERR=target-MotorRotationCount(OUT_A);
    u=P*ERR+D*(ERR-ERRo);
    if(u>100)u=100;
    if(u<-100)u=-100;
    OnFwd(OUT_A,u);
    ERRo=ERR;
  }

  //выключаем мотор
  Off(OUT_A);
}

//функция для подсчета нажатий на кнопки
int touch(int sensor) {
  //переменная, в которой мы храним количевство нажатий
  int countPress=0;
  //условие, проверяющее на каком датчике ждать нажатия
  if(sensor==1){
    //ожидание первого нажатия
    while(Sensor(S1)==0){
      Wait(1);
    }
    //защина от шума
    Wait(100);
    //ожидаем отжатия
    while(Sensor(S1)!=0);
    long timeToPress=CurrentTick();
    //цикл, ожидающий второго нажатия заданое время
    while(Sensor(S1)==0 && CurrentTick()-timeToPress < 1000);
    //если вылетели не по времени, а по нажатию
    if(CurrentTick()-timeToPress < 1000) {
      //зашита от шума
      Wait(100);
      //устанавливаем количество нажатий в 2(0 - одно нажитие, 1 - два нажатие)
      countPress=1;
      //ожидаем отжатия
      while(Sensor(S1)!=0);
    }
    //возвращаем значение
    return countPress+1;
  }
  //если проверяется второй датчик
  if(sensor==2){
    //ожидаем нажатия
    while(Sensor(S2)==0){
      Wait(1);
    }
    //защита от шума
    Wait(100);
    //ожидание отжатия
    while(Sensor(S2)!=0);
    long timeToPress=CurrentTick();
    //цикл, ожидающий второго нажатия заданое время
    while(Sensor(S2)==0 && CurrentTick()-timeToPress < 1000);
    //если вылетели не по времени, а по нажатию
    if(CurrentTick()-timeToPress < 1000) {
      //защита от шума
      Wait(100);
      //устанавливаем количество нажатий в 2
      countPress=1;
      //ожидаем отжатия
      while(Sensor(S2)!=0);
    }
    //возвращаем значение
    return countPress+1;
  }

// параллельный процесс для обучения нейронных сетей
}
task learn(){
  Wait(2000);
  //говорим "начало обучения нейронной сети"
  PlayFile("start.rso");
  Wait(2000);
  //запоминаем время
  long timeToLearn = CurrentTick();
  //главный цикл
  while(true)
  {
    //обнуляем tmp1 и tmp2
    for(int i=0;i<=10;i++){
      tmp1[i]=0;
      tmp2[i]=0;
    }
    //если прошла секунда? (каждую секунду)
    if(CurrentTick()-timeToLearn>=1000){
      //вывод на экран  количевства игр и выигрышей
      line1=NumToStr(game)+" "+NumToStr(winNN1)+" "+NumToStr(winNN2);
      //вывод на экран выигрывающей нейросети
      if(winNN1>=winNN2){
        line2="HC1";
      }
      else{
        line2="NC2";
      }
      //вывод строк
      ClearScreen();
      TextOut(0,LCD_LINE1,line1);
      TextOut(0,LCD_LINE2,line2);
      TextOut(0,LCD_LINE3,line3);
      TextOut(0,LCD_LINE4,line4);
      TextOut(0,LCD_LINE5,line5);
      TextOut(0,LCD_LINE6,line6);
      TextOut(0,LCD_LINE7,line7);
      //очистка строк
      line1 = "";
      line2 = "";
      line4 = "";
      line6 = "";
      line7 = "";
      //перезаписываем время
      timeToLearn = CurrentTick();
    }
    //увеличиваем число игр
    game++;
    //переменная кто выиграл
    win2=0;
    //сколько кубиков осталось
    box2=11;

    //цикл игры
    while(true){

      //ход НС2
      //вытягиваем камень
      if(Random(100) < white2[box2-1]*1.0/(white2[box2-1]+black2[box2-1])*100.0){
        //запоминаем какой использовали коробок
        tmp2[box2-1]=2;
        //уменьшаем количество оставшихся кубиков в кучке
        box2-=2;
      }
      else{
        //запоминаем какой использовали коробок
        tmp2[box2-1]=1;
        //уменьшаем количество оставшихся кубиков в кучке
        box2-=1;
      }
      //проверка на выигрыш
      if(box2<=2){
        win2=1;
        break;
      }

      //ход НС1
      //вытягиваем камень
      if(Random(100) < white1[box2-1]*1.0/(white1[box2-1]+black1[box2-1])*100.0){
        //запоминаем какой использовали коробок
        tmp1[box2-1]=2;
        //уменьшаем количество оставшихся кубиков в кучке
        box2-=2;
      }
      else{
        //запоминаем какой использовали коробок
        tmp1[box2-1]=1;
        //уменьшаем количество оставшихся кубиков в кучке
        box2-=1;
      }
      //проверка на выигрыш
      if(box2<=2){
        win2=2;
        break;
      }

    }
    //поощрение-наказание
    //NN1 выиграла
    if(win2==1){
      winNN1++;
      for(int i = 0;i<=10;i++){
        if(tmp1[i]==1) black1[i]++;
        if(tmp1[i]==2) white1[i]++;
      }
    }
    else{
      for(int i = 0;i<=10;i++){
        if (tmp1[i] > 0)
        {
          if(tmp1[i]==1 && black1[i]>1) black1[i]--;
          if(tmp1[i]==2 && white1[i]>1) white1[i]--;
          break;
        }
      }
    }
    //NN2
    if(win2==2){
      winNN2++;
      for(int i = 0;i<=10;i++){
        if(tmp2[i]==1) black2[i]++;
        if(tmp2[i]==2) white2[i]++;
      }
    }
    else{
      for(int i = 0;i<=10;i++){
        if (tmp2[i] > 0)
        {
          if(tmp2[i]==1 && black2[i]>1) black2[i]--;
          if(tmp2[i]==2 && white2[i]>1) white2[i]--;
          break;
        }
      }
    }
  }
}

task main()
{
  //подключаем датчики
  SetSensorTouch(IN_1);
  SetSensorTouch(IN_2);
  ClearScreen();
  line1 = "";
  line2 = "";
  line3 = "";
  line4 = "";
  line5 = "";
  line6 = "";
  line7 = "";

  //делаем случайные числа действительно случайными
  for(int i=0; i<=CurrentTick()%1000; i++) { int tmp_r = Random(); }

  //сбрасываем tmp
  for(int i=0;i<=10;i++){
    tmp1[i]=0;
    tmp2[i]=0;
    tmp[i]= 0;
  }
  
  //запуск параллельной задачи learn для обучения нейросетей
  start learn;


  //Ожидание нажатия на кнопки
  line5="left 2 right 1";
  while (!ButtonPressed(BTNRIGHT, true) && !ButtonPressed(BTNLEFT, true));
  line5 = "";
  // если нажат левый датчик, игра человек-человек
  if(ButtonPressed(BTNLEFT, true))
  {
    //бесконечный цикл игры
    while(true)
    {
      //сброс tmp
      for(int i=0;i<=10;i++){
        tmp[i]= 0;
      }
      //Кубиков 11
      box1=11;
      while(true)
      {
        //ход игрока1
        buttonPress=touch(2);
        //выкидываем столько кубиков, сколько нажатий
        Left(buttonPress);
        //запоминаем сколько выкинули
        box1-=buttonPress;

        line4=NumToStr(box1);
        //проверка на выигрыш
        if(box1<=2){
          win1=1;
          line3="Player1 Win";
          break;
        }
        //ход игрока2
        buttonPress=touch(1);
        //выкидываем столько кубиков, сколько нажатий
        Right(buttonPress);
        //запоминаем сколько выкинули
        box1-=buttonPress;

        line4=NumToStr(box1);
        if(box1<=2){
          //проверка на выигрыш
          win1=2;
          line3="Player Win";
          break;
        }
      }
      //ожидания нажатия для новой игры(загрузка кубиков)
      while (!ButtonPressed(BTNCENTER, true));
      line3 = "";
    }
  }

  //если нажат правый датчик, игра человек-NN
  if(ButtonPressed(BTNRIGHT, true))
  {
    while(true)
    {
      //переменная кто выйграл
      win1=0;
      //сколько кубиков осталось
      box1=11;
      //рандомно определям первый ход
      if (Random(100)>50)
      {
        //первый ходит человек
        while(true){
          //ход игрока
          PlayFile("playerh.rso");
          Wait(1000);
          buttonPress=touch(2);
          if(buttonPress==1) {
            PlayFile("player1.rso");
            Wait(2000);
          }
          else{
            PlayFile("player2.rso");
            Wait(2000);
          }
          //выкидываем кубики по количеству нажатий
          Left(buttonPress);
          box1-=buttonPress;
          line4=NumToStr(box1);

          //проверка на выигрыш
          if(box1<=2){
            PlayFile("networkw.rso");
            Wait(2000);
            win1=1;
            line3="Robot Win";
            break;
          }
          PlayFile("networkh.rso");
          Wait(2000);
          PlayFile("networkd.rso");
          Wait(Random(10000)+2000);
          
          //ход НС
          if(Random(100) < white1[box1-1]*1.0/(white1[box1-1]+black1[box1-1])*100.0){
            PlayFile("network2.rso");
            Wait(2000);
            //берёт 2 кубика
            Right(2);
            box1-=2;
          }
          else{
            PlayFile("network1.rso");
            Wait(2000);
            //берёт 1 кубик
            Right(1);
            box1-=1;
          }

          line4=NumToStr(box1);
          
          //проверка на выигрыш
          if(box1<=2){
            PlayFile("playerw.rso");
            Wait(2000);
            win1=2;
            line3="Player Win";
            break;
          }
        }
      }
      // если первой ходит NN
      else
      {
        while(true){
          //ход НС
          if(Random(100) < white2[box1-1]*1.0/(white2[box1-1]+black2[box1-1])*100.0){
            PlayFile("network2.rso");
            Wait(2000);
            //берёт 2 кубика
            Right(2);
            box1-=2;
          }
          else{
            PlayFile("network1.rso");
            Wait(2000);
            // берёт 1 кубик
            Right(1);
            box1-=1;
          }

          line4=NumToStr(box1);
          // проверка на выигрыш
          if(box1<=2){
            PlayFile("playerw.rso");
            Wait(2000);
            win1=2;
            line3="Player Win";
            break;
          }

          //ход игрока
          PlayFile("playerh.rso");
          Wait(1000);
          buttonPress=touch(2);
          if(buttonPress==1) {
            PlayFile("player1.rso");
            Wait(2000);
          }
          else{
            PlayFile("player2.rso");
            Wait(2000);
          }
          // выкидываем по количеству нажатий
          Left(buttonPress);
          box1-=buttonPress;
          line4=NumToStr(box1);

          //проверка на выигрыш
          if(box1<=2){
            PlayFile("networkw.rso");
            Wait(2000);
            win1=1;
            line3="Robot Win";
            break;
          }
          PlayFile("networkh.rso");
          Wait(2000);
          PlayFile("networkd.rso");
          Wait(Random(10000)+2000);
        }
      }

      // одидания нажатия для продолжения игры
      PlayFile("networkl.rso");
      Wait(3000);
      PlayFile("next.rso");
      Wait(2000);
      while (!ButtonPressed(BTNCENTER, true));
        line3 = "";
      }
    }
  }
}