Несколько дней назад мне нужно было реализовать хеш-функцию для игры Tic Tac Toe в качестве упражнения для моего класса ИИ (для непосвященных использование хэш-таблицы вместо связанного списка снижает сложность алгоритма на порядок O (n^ 2) в данном случае [1]) потому что мне нужно сгенерировать все возможные движения игроков в игре, 255168различных состояний, но многие из них были изоморфны после применения некоторого поворота или отражение по оси доски, поэтому, правильно работая с этим вариантом, мне нужно будет сделать как можно более быструю симуляцию.

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

  • 0 -> свободное место
  • 1 -> круг
  • 4 -› крест

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

Затем, в минуту безделья, я прекрасно вспомнил свой класс компьютерного зрения:

SIFT, детектор ключевых точек, инвариантный к поворотам, масштабу и преобразованиям (такая интересная тема, может быть, я напишу о ней позже) и в его ядре функция, которая имеет дело с вращениями, была функцией Гаусса, проще говоря, когда вы нанесете эту функцию на трехмерную среду, вы увидите колокольчик, применяя ядро ​​Гаусса к матрице, которая представляет цифровое изображение, которое мы обрабатываем, и даст нам матрицу со взвешенными значениями изображения на основе его положение, так как оно работает на игре крестики-нолики?

Вы можете увидеть матрицу игры в виде кубика Рубика, в которой у нас есть 3 типа позиций:

  1. Центральный ряд: никогда не подвергайтесь вращению, это самый важный ряд.
  2. Средние ряды: ряды, которые не являются углами.
  3. Угловые ряды: последние важны, потому что они более чувствительны к поворотам.

Затем, помня об этом, было легко выполнить эту хеш-функцию, представление ядра Гаусса в виде матрицы, например:

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

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

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

  • Это мой первый пост на английском языке, я ценю предложения по улучшению моего редактирования, на самом деле, в этом смысл этого занудного поста (да, я возьму еще уроки грамматики, но позже, до этого нужно сделать еще несколько интересных вещей)
  • Также вы можете найти репо упражнения: https://github.com/ndrd/crispy-system/blob/master/Practica%202%20-%20Gatos/src/Gatos.java