24.11.2023 17:00
dacsson 28 3100 Источник

Доброго времени суток, когда вы в последний раз играли в крестики-нолики? Вопрос действительно важный, не удивляйтесь, всё окажется гораздо хитрее чем вы думали. Полагаю что давно, хорошо, вспомните поле которое вы рисовали на бумаге: 3x3? 5x5? А что вы скажете насчёт 19x19? "Долго будем играть!" - и это только часть проблемы. Если вы крайне дотошный игрок в крестики-нолики и не можете позволить себе проиграть младшему брату в такую игру, то вы конечно попытаетесь анализировать положение поля, пред рассчитать шаги брата и выбрать наилучший. Ход мыслей отличный, однако это вполне несложно на маленьких полях, а вот 19 на 19... Именно такая задача встала передо мной в ходе хакатона от компании Тинькофф - написать бота для игры в крестики-нолики на доске 19x19 с поиском самого лучшего хода за небольшое время (на вход поступает состояние всей доски на данный момент - на выход также вся доска с новой фигурой).

Как играть в крестики-нолики?

Давай-те теперь сменим обстановку и скажем, что вы, чтобы точно обыграть младшего брата написали бота который играет за вас и ищет самые лучшие шаги в некой ситуации. Как мы представим в программе эту самую игру, её правила и доску?

Первая идея - представим доску в виде набора символов и будем смотреть где стоит крестик а где нолик. Просто? Вполне! Представим себе поле 3x3 где каждый игрок поставил по одной фигуре:

string board_state = "x_o______";

Выглядит неплохо, однако как проверить что кто-то выиграл? Например, можно сравнить наш board_state с примерами выигрышных строк:

string board_state = "x_o______";
string win_patterns[0] = "xxx______";
if(board_state.Equals(win_patterns[0])) 
  Console.Write("Крестики победили!");

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

Битовые доски

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

uint x_board = 0b100_000_000; // X стоит на 9-ой клетке (считая с правого угла), т.е. в 9 разряде числа
uint o_board = 0b001_000_000; // О стоит на 7-ой клетке, т.е. в 7 разряде числа

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

uint full_board = x_board | o_board; // Просто битово умножаем два числа!

Элегантно? Это ещё не всё! Для проверки того, выиграл ли кто-то мы также будем сравнить положения доски с выигрышной ситуацией, но делать мы это будем с помощью операции побитового умножения:

uint x_board = 0b100_000_000; 
uint o_board = 0b001_000_000; 
uint[] win_patterns = 
{   
  0b111_000_000, // 3 в ряд на позициях 9, 8 и 7
  0b000_111_000, // 3 в ряд на позициях 6, 5, 4
  0b100_010_001, // 3 в диагональ слева-направо
  // и так далее
};

if (win_patterns.Any(w => (x_board & w) == w)) Console.Write("X победили!");
else if(win_patterns.Any(w => (x_board & w) == w)) Console.Write("O победили!");

Согласитесь - операция побитового умножения гораздо приятнее (быстрее) сравнения строк.

Масштабируем проблему

И тут многие догадались, как же я хочу решить проблему написания бота для игры в крестики-нолики на поле 19x19. Однако, как мы представим такую доску?

ulong x_board = 0b0000000000000000000_0000000000000000000_... // 19 рядов по 19 ноликов

Такое число превышает 64 бита, что уже больше ulong! А ведь нам ещё хранить победные ситуации! Как будем выбираться? Можно подключить какую-нибудь библиотеку для больших типов данных но хранить такие переменные? Да и для внешнего восприятия выглядит действительно ужасно. Тогда стоит подумать, доска состоит из строк, почему бы и нам это огромное число разделить не разделить на строки и хранить состояние доски в виде девятнадцати 19-разрядных битовых чисел - строк (рядов) доски?

uint[] x_board = new uint[19]
{
  0b1000000000000000000,
  0b0110000000000000000,
  0b0000000000000000000,
  0b0000000000000000000,
  ... // 19 чисел
}

Тогда спокойно можно использовать uint. Отлично, а как проверять такую красоту на выигрыш (при условии что победа - 5 фигур в ряд, в столбец и диагональ) ? Давайте разбираться, для начала представим все случаи победы в ряд для i-ой строки доски:

private static readonly uint[] _win_patterns_rows =
{
  0b1111100000000000000,
  0b0111110000000000000,
  0b0011111000000000000,
  0b0001111100000000000,
  0b0000111110000000000,
  0b0000011111000000000,
  0b0000001111100000000,
  ... 
};

Тогда чтобы проверить выиграл ли какой-либо игрок будем побитового перемножать i-ую строку из доски игрока на j-ую строку из всевозможных выигрышных строк:

private bool check_if_board_win_pattern_horizontal(uint[] board)
{
  uint horizontal_check;
  uint win_pattern;

  // проходим по каждой строке состояния доски игрока
  for (byte j = 0; j < 19; j++)
  {
    // проверяем каждый выигрышный случай данной строки
    for(byte i = 0; i < 15; i++)
    {
      // проверяем все возможные состояние доски при победе в ряд
      horizontal_check = board[j] & _win_patterns_rows[i];
      win_pattern = _win_patterns_rows[i];
      if (horizontal_check == win_pattern) return true;
    }
  }
  return false;
}

Но это только в ряд, как же в столбец? Представим, что наше двоичное представление доски 19x19 - это бинарная матрица, ведь правда похоже! Тогда нам достаточно просто транспонировать эту матрицу и запустить функцию проверки сверху - ведь столбцы станут строками!

Для транспонирования будем умножать i-ое число j-ой строки доски на 0b1000000000000000000 попутно побитово сдвигая это j-ую строку на i бит вправо:

private bool check_if_board_win_pattern_vertical(uint[] board)
{
  // По сути транспонирование матрицы (если представить числа как биты в 19) 19х19
  // ну или поворот доски)
  uint[] transp_board = new uint[19];
  for(byte i = 0; i < 19; i ++)
  {
    for(byte j = 0; j < 19; j++)
    {
      transp_board[i] |= ((board[j] << i) & (uint)0b1000000000000000000) >> j;
    }
  }
  return check_if_board_win_pattern_horizontal(transp_board);
}

Хорошо, тут разобрались, а как же проверка по диагонали? Попытаемся представить выигрышную позицию в случае победы в диагональ слева-направо:

    private static readonly uint[] _win_patterns_diagnal =
    {
        0b1000000000000000000,
        0b0100000000000000000,
        0b0010000000000000000,
        0b0001000000000000000,
        0b0000100000000000000,
        // остальные строки такой доски будут нулевыми поэтому нет смысла их заполнять
        // нам важны 5 в диагональ
    };

Проверить конкретно такую выигрышную ситуацию мы сможем - перемножим доску какого-либо игрока на эти значения как мы делали выше. Однако нам нужно проверить все случаи 5 фигур подряд в диагональ. Сделаем очень хитрую вещь - представим опять, что наше поле игрока - это матрица 19х19, разделим эту матрицу на все возможные подматрицы 5x19 (так как нам необходимы только 5 столбцов для проверки) и будем умножать их на наш _win_patterns_diagnal, однако затем заново пойдём делать тоже самое применим к каждой строке _win_patterns_diagnal сдвиг вправо на i количество битов. Звучит сложно, посмотрим в виде кода:

private bool check_if_board_win_pattern_diagnall(uint[] board, bool left_to_right)
{
  uint[] _win_patterns;
  uint[] diagnal_check = new uint[5];
  
  for(byte h = 0; h < 19; h++)
  {
    // Сдвигаем матрицу победы наискок чтобы посмотреть все варианты a.k.a
    // 1, 0, 0, 0, 0         0, 1, 0, 0, 0
    // 0, 1, 0, 0, 0   =>    0, 0, 1, 0, 0
    // 0, 0, 1, 0, 0         0, 0, 0, 1, 0
    // ....                     ....
    _win_patterns = (uint[])_win_patterns_diagnal.Clone();

    // Реверсировать каждую строку (число) доски игрока
    // код затычка - нужно будет дописать...
    if (left_to_right) _win_patterns.Reverse();

    _win_patterns[0] >>= h;
    _win_patterns[1] >>= h;
    _win_patterns[2] >>= h;
    _win_patterns[3] >>= h;
    _win_patterns[4] >>= h;
    // Заполняем проверочную матрицу 5x19 (т.к. 5 наискосок)
    for (byte i = 0; i < 5; i++)
    {
      // Проходимся шагом 5, иначе говоря рассматриваем все подматрицы 5x19 матрицы 19x19
     for (byte count = 0; count < 14; count += 5)
      {
        // проверяем все возможные состояние доски при победе в ряд
        diagnal_check = new uint[5];
        diagnal_check[i] = board[count] & _win_patterns[i];
      }
      if (new HashSet<uint>(diagnal_check).SetEquals(_win_patterns)) return true;
    }
  }

  return false;
}

Для проверки победы на диагональ справа-налево будем просто реверсировать каждую строку (в коде сверху это не реализовано).

А как же сам алгоритм поиска решений?

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

Для чего это написано?

Во время решения данной проблемы я не нашёл стоящей информации про игры на доске 19х19, их представление в виде битовых досок и ещё очень много чего. Алгоритмы которые я описал были додуманы мною на основе чужих наработок решения той же проблемы на небольших полях (3х3 и 5х5), в частности работа с доской как с набором строк (рядов) и вытекающие отсюда последствия.

Заметки

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

Также думаю стоит упомянуть, что как и в проверке на 5 в диагональ - так и в проверках в ряд и в столбец можно оптимизировать алгоритм путём динамического битового сдвига.

Многие решения в реализации были приняты исходя из:

  • Сжатого срока хакатона

  • Жёсткие рамки на ресуры, выделяемые для бота (память + время)

  • Условием задачи: на вход поступает нынешнее состояние доски, а на выход новое состояние доски с новой фигурой

Комментарии (28)


  1. Cheater
    24.11.2023 17:22
    #26195388
    +3

    Имхо ваш алгоритм неэффективен. Вместо того чтобы перебирать всё поле, достаточно проходиться по всем позициям, на которых стоит крестик или нолик, и для каждой такой позиции проверять, не стоит ли она в ряду из 5 таких же символов, вертикальном горизонтальном или диагональном. (прямой проверкой индексов во все стороны). Символы, провалившие проверку, можно помечать, чтобы не проверять много раз. На пометки нужна доп. память и нужны 4 вида пометок тк позиция, помеченная например "не в вертикальном ряду из 5", может находиться в горизонтальном ряду из 5). Это решение в лоб, думаю есть ещё эффективнее


    1. amphasis
      24.11.2023 17:22
      #26195452
      +3

      Если задача стоит в проверке наличия выигрышной позиции после хода, то достаточно все эти проверки производить относительно последнего поставленного крестика/нолика


    1. dacsson Автор
      24.11.2023 17:22
      #26195478

      Условности задания, там к боту приходит конкретно вся доска, а он отвечает новой доской с новой фигурой


      1. amphasis
        24.11.2023 17:22
        #26195786

        Контекст вообще никакой нельзя хранить?


        1. dacsson Автор
          24.11.2023 17:22
          #26195830

          хранить то можно - но боту даётся 1 ядро, 1 gb и 1 секунда на ответ


          1. amphasis
            24.11.2023 17:22
            #26195848
            +1

            Ну, кажется даже в таких условиях можно хранить в каком-нибудь локальном memory cache. С другой стороны, при небольшом количестве клиентов, вероятно такая оптимизация и не имеет смысла, поскольку алгоритм не упрется в лимит по CPU.

            Будет интересно почитать следующую статью по алгоритму выбора хода.


    1. dacsson Автор
      24.11.2023 17:22
      #26195588

      Вопрос будет ли это быстрее побитового умножения и по загруженности памяти, не совсем уверен


  1. Alohahwi
    24.11.2023 17:22
    #26195592
    +2

    Пару лет назад просчитал пьяницу. Играл с детьми, захотелось выигрывать. Единственное что там можно делать - это порядок карт убираемых в низ колоды менять. Результат был неожиданным. Если начинать вводить любую сортировку карт, идущих в низ колоды - вероятность бесконечной партии сразу становится 90+ процентов. Было пару вариантов, где вероятность своего выигрыша можно было увеличить на 5%, но это при 80% вероятности бесконечной партии.


  1. aeder
    24.11.2023 17:22
    #26195716

    Нахрена хранить позицию в виде битовой карты? Я понимаю, если бы вы играли на поле мегабайт на мегабайт. Но поле 19 на 19 - это всего лишь ~400 байт в виде двумерного массива.


    1. dacsson Автор
      24.11.2023 17:22
      #26195718

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


      1. aeder
        24.11.2023 17:22
        #26195724

        На возню с битовыми операциями вы потратили больше ресурсов, чем эти самые 400 байт.


        1. dacsson Автор
          24.11.2023 17:22
          #26195748

          Важны не мои ресурсы, что были потрачены, а ресурсы машины, которые тратит бот


  1. ri1wing
    24.11.2023 17:22
    #26195938
    +2

    Игра на поле 19x19, где надо поставить пять в ряд, называется гомоку.

    https://ru.wikipedia.org/wiki/Гомоку


    1. klimkinMD
      24.11.2023 17:22
      #26199838

      Она же рэндзю, и теория говорит, что без дополнительных ограничений (правил) выигрывает тот, кто ходит первым ("чëрные", в оригинале). Я, к тому, что теория игры достаточно разработана. Про "Алгоритм лучшего хода" пока -- ни слова. По-мне, так с него и нужно начинать серию статей, а танцы с битами оставить на финал потому как это давно известное дело. Хотя, наверное, от командного мировоззрения зависит.


  1. wataru
    24.11.2023 17:22
    #26195974
    +4

    Ваши битовые оптимизации - нифига не оптимизации.

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

    Например, для горизонтальных проверок:

    for (int i = 0; i < 19; ++i) {
  int cur_len = board[i][0] == cur_char;
  for (int j = 1; j < 19; ++j) {
    cur_len = (board[i][j] == cur_char) ? cur_len+1 : 0;
    if (cur_len == 5) {
      // нашли пять в ряд.
    }
  }
}

    Если вместо переменной cur_len завести матрицу и хранить значения в каждой клетке, то вообще один и тот же код проверяет по всем трем направлениям:

    const int dx[3] = {1, 0, 1};
const int dy[3] = {0, 1, 1};
for (int k = 0; k < 3; ++k) {
  for (int i = 0; i < 19; ++i) {
    cur_len[i][0] = (board[i][0] == cur_char);
    cur_len[0][i] = (board[0][i] == cur_char);
  }
  for (int i = 1; i < 19; ++i) {
    for (int j = 1; j < 19; ++j) {
      cur_len[i][j] = (board[i][j] == cur_char) ? cur_len[i-dx[k]][j-dy[k]]+1 : 0;
      if (cur_len[i][j] == 5) {
        // нашли пять в ряд 'cur_char'.
      }
    }
  }
}

    Если еще перевести поле в 2 булевых матрицы для X и O, то точно будет быстрее вашего подхода. Особенно для диагональных проверок. И не надо десятков шаблонов.


    1. dacsson Автор
      24.11.2023 17:22
      #26196016
      -3

      Не думаю, что то,что вы написали - верно, напишите такого же бота вашим методом - проверим)

      А вам советую больше про битовые операции почитать над bitboards почитать


      1. wataru
        24.11.2023 17:22
        #26197168
        +2

        Нет, это вам стоит почитать про динамическое программирование.

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

        А битовыми трюками можно ускорить не в 5, а в 19 раз. И не надо никаких масок. Если у вас каждая строка хранится в битах одного uint, то взяв board[i]&board[i+1]&board[i+2]&board[i+3]&board[i+4] вы получите единичные биты в тех столбцах, где в первых 5 строках есть символы. Если получили не 0 - то любой единичный бит - это искомое начало 5 элементов вертикально в ряд.

        Соответственно, вам надо транспанировать матрицу для проверки горизонтальных пятерок, а не вертикальных. Для диагональных проверок вам надо брать board[i] & (board[i+1]<<1) & (board[i+2] << 2)...

        Для другого наклона диагонали - сдвигайте вправо, а не влево.


        1. dacsson Автор
          24.11.2023 17:22
          #26197198

          как мне кажется, я делаю нечто подобное что вы написали, но может я не до конца вас понял


          1. wataru
            24.11.2023 17:22
            #26197258
            +3

            Подобного у вас только то, что вы битовые операции используете. У меня циклы 14*5 и всего 14 проверок. У вас же циклы 19*15 и столько же проверок. А в диагональных случаях у вас вообще циклы 19*5*3 (кстати, как у вас там вообще работает? Вы к board обращаетесь только к строкам count, кратным 5 - вообще не проверяя все, кроме трех строк).

            Главная ваша проблема, что вы пытаетесь прикладывать жесткие маски. Это имеет смысл делать, только когда вам важны символы, скажем именно в 4-ом ряду. Нет, в этой задаче 5 в ряд могут быть где угодно. Поэтому ваш подход заставляет прикладывать одну и ту же маску ко всем позициям. Хотя можно наоборот, для всех позиций сразу проверить, а проходит ли через них пять в ряд.

            Вот код для проверки вертикальных 5-в-ряд:

            bool CheckVertical (int board[19]) {
  for (int i = 0; i < 14; ++i) {
    int acc = board[i];
    for (int j = 1; j < 5; ++j) {
      acc &= board[i+j];
    }
    if (acc != 0) return true;
  }
  return false;
}

            Это работает, потому что если где-то есть 5 в ряд, то там board[i], board[i+1]... board[i+4] все будут иметь 1 в одном и том же разряде. И мы получим 1 в acc в этом разряде. И наоборот, если мы получили где-то 1 в acc, то значит на доске в 5 строках в этом столбце есть 1.

            Вот диагонали. Вместо диагональной маски, мы сдвигаем строки поля и потом ищем тут вертикальные 5-в-ряд: 

            bool CheckDiagLeft (int board[19]) {
  for (int i = 0; i < 14; ++i) {
    int acc = board[i];
    for (int j = 1; j < 5; ++j) {
      acc &= board[i+j] << j;
    }
    if (acc != 0) return true;
  }
  return false;
}

bool CheckDiagRight (int board[19]) {
  for (int i = 0; i < 14; ++i) {
    int acc = board[i];
    for (int j = 1; j < 5; ++j) {
      acc &= board[i+j] >> j;
    }
    if (acc != 0) return true;
  }
  return false;
}

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

            bool CheckHorizontal (int board[19]) {
  for (int i = 0; i < 19; ++i) {
    int acc = board[i];
    for (int j = 1; j < 5; ++j) {
      acc &= board[i] << j;
    }
    if (acc != 0) return true;
  }
  return false;
}


            1. dacsson Автор
              24.11.2023 17:22
              #26197786
              +1

              Теперь дошло! Спасибо за комментарии, действительно так выходит гораздо лучше


  1. VladimirFarshatov
    24.11.2023 17:22
    #26196756
    +1

    Когда-то писал подобное для игры в крестики-нолики "по 5" на бесконечном поле, ещё для ЕС .. деталей уже не помню к сожалению. Но, как-бы там памяти с гулькин нос было, хранить пустые клетки вообще незачем (поле безрамерно) и оценивать надо далеко не всю массу крестиков и ноликов, а только "краевые", которые могут участвовать в возможных вариантах.

    Так, на вскидку что вспомнилось..


    1. dacsson Автор
      24.11.2023 17:22
      #26196812

      вот это действительно интересно реализовать на бесконечном поле, надо будет покумекать


      1. VladimirFarshatov
        24.11.2023 17:22
        #26197410
        +1

        Ещё как подсказка: клетки, удаленные от края дальше 5 - хранить нет никакого смысла, они уже не участвуют ни в чем. ;)


  1. appet1te
    24.11.2023 17:22
    #26197090

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


    1. dacsson Автор
      24.11.2023 17:22
      #26197262

      да, это отложил на вторую статью, но вы правы на 100%


    1. VladimirFarshatov
      24.11.2023 17:22
      #26197422
      +1

      Смутно вспоминаю, что алгоритм был тупым как палка: ищем куда можно воткнуть 5-й элемент, если такого места нет, то ищем .. где можно воткнуть третий, но так чтобы получилось 2 тройки, открытых с обоих концов, если нет то ищем 3+4 или просто 4. Если нет ничего "подходящего выше", то ищем подобное в других элементах и затыкаем возможный проигрыш своим. как-то так..


  1. wataru
    24.11.2023 17:22
    #26197308
    +1

    Есть очень простой алгоритм основанный на оценках: Для каждого множества из 5-в-ряд на доске проверим, состоит ли оно лишь из 'O' или лишь из 'X'. Если там есть и те и другие, то это множество никогда не станет победным ни для одного из игроков. В противном случае, добавим всем пустым клеткам в этом множестве очков, в зависимости от количества стоящих заполненных символов. Самая большая оценка должна быть у множества из 4 'X' (если мы за крестики играем). Тогда одним ходом мы можем закрыть пятерку и победить. Допустим 10^9. Потом идет 4 'O'. Надо обязательно закрыть эту клетку, ведь иначе враг следующим ходом выиграет. Можно тут назначить 10^8 Потом должны идти те клетки, которые лежат на пересечении двух множеств из троек. Ведь поставив сюда, мы получим 2 пересекающиеся четверки, что даст нам "вилку": что бы враг следующим ходом не закрыл - мы победим на следующем ходу. Поэтому тройке 'O' назначим 10^7. И так далее, чередуем символ и уменьшаем количество и назначаем ситуации какую-то степень 10. Просуммировав эти оценки повсем пятеркам на поле для всех клеток останется только выбрать максимум.

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


    1. VladimirFarshatov
      24.11.2023 17:22
      #26197428
      +1

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