Оценка покерных рук с помощью таблиц поиска и идеального хеширования

Сегодняшняя запись в блоге продолжает мою серию о компьютерном покере кратким обзором таблиц поиска и идеальных хешей. Огромные благодарности и признательности перед тем, как мы начнем с Kevin Suffecool, Paul Senzee и Mike Benson - без сомнения, отцов-основателей современного компьютерного покера. Не стесняйтесь форк / клонировать мой репозиторий, чтобы следить за тем, как вы читаете об их работе, результатом которой стал один из самых дьявольски умных алгоритмов из когда-либо написанных…

Предыстория: как поворачивается стол

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

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

Разбор рук наивным способом

Если бы я попросил вас, дорогой читатель, написать код для анализа покерной руки, вы, возможно, были бы склонны, например, написать класс ES6, который выглядит примерно так:

class Card {
  constructor( suit, rank ) {
    this.suit = suit;
    this.rank = rank;
  }
  compare( otherCard ) {
    ...code to compare two cards
  }
}

Или вы можете решить, как я вначале, представить карту как что-то более простое - примитивный тип данных, такой как строка или число:

const fullDeck = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 ];
// or, alternately
const fullDeck = [ ...Array( 52 ).keys() ].map( i => i + 1 );
function value( hand ) {.     // an Array( 5 ) as an argument
  const countByPair = [ 0, 0, 0, 0 ];
  const countBySuit = [ 0, 0, 0, 0 ];
  hand.forEach( card => {
    ...iterate through each card and update counter
  } );
}

Подобные подходы имеют интуитивный смысл, и тысячи были написаны благодаря курсам бакалавриата по информатике. Проблема? Вся эта сортировка, итерация для подсчета рангов / мастей и ветвление для проверки определенных рангов рук, таких как флеши, медленны, как меласса - едва достаточно быстры для базового анализа и нигде близко достаточно для покерного бота или инструмента стратегии покера.

Давным-давно в далекой галактике инженер и энтузиаст покера по имени Kevin Suffecool (CactusKev) столкнулся с этой проблемой и продал свою душу за решение: представление карт в виде битов, затем использование таблиц поиска для уменьшения / устранения разветвления, необходимого в подходах, описанных выше. С тех пор код, который появился в результате, вызывает всеобщее восхищение, обсуждается и улучшается. Наденьте солнцезащитный крем и защитные очки - мы глубоко ныряем ...

Представление карточек как 4-байтовых беззнаковых целых чисел

В предыдущем сообщении блога, которое я писал о k-комбинациях, я объяснил, что все карточные игры - это комбинаторические игры: колода - это наша коллекция, а размер руки - наша k (комбинация размер / длина) . Пятикарточный валет или лучше, игра, на которой основан видеопокер в Вегасе, представляет собой игру с 52 комбинациями из пяти, что означает, что существует 2 598 960 возможных комбинаций из пяти карт в покере.

Настоящий гений покеризатора CactusKev заключается в понимании того, что многие из этих рук имеют одинаковую ценность. Например, у игрока с рукой [ “Ace of Spades", “Jack of Spades", “9 of Spades", “Four of Spades", “2 of Spades" ] (флеш пик) рука имеет такой же рейтинг, как и у игрока с [ “Ace of Clubs", “Jack of Clubs", “9 of Clubs", “Four of Clubs", “2 of Clubs" ] (флеш треф). Эти две разные руки имеют одинаковый ранг и, следовательно, могут разделить банк в игре с дро-покером. Это означает, что из почти 2,6 миллиона уникальных пятикарточных покерных комбинаций мы получаем только 7 462 уникальных покерных комбинации рангов:

Hand Value      Unique   Distinct   
Straight Flush  40       10
Four of a Kind  624      156
Full House      3744     156
Flush           5108     1277
Straight        10200    10
Three of a Kind 54912    858
Two Pair        123552   858
One Pair        1098240  2860
High Card       1302540  1277
TOTAL           2598960  7462

Подход CactusKev оценивает каждую руку по рангу от 7 462 (самая низкая из возможных комбинаций семерки) до 1 (флеш-рояль). Он делает это, представляя каждую карту как четырехбайтовое целое число: «Старшие байты используются для хранения битового шаблона ранга, тогда как младшие байты содержат [масть и ранг] карты». Кроме того, каждый ранг также представлен простым числом, так что умножение младших 6 бит карты дает однозначно определяемое множимое:

Имея все это в виду, рассмотрим приведенный ниже код, который return представляет собой массив из 52 целых чисел, каждое из которых представляет собой покерную карту CactusKev:

const fullDeck = () => {
  const rankPrimes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ], result = [];
  for ( let rank = 0; rank < 13; rank++ ) for ( let suit of [ 8, 4, 2, 1 ] )
    result.push( ( rankPrimes[ rank ] ) | ( rank << 8 ) | ( suit << 12 ) | ( ( 1 << rank ) << 16 ) );
  return result;
}

Давайте разберем основные действия по строкам 2 и 3:

• Обратите внимание, мы представляем масти как набор битов: 8 (0b1000) для треф, 4 (0b0100) для бубен, 2 (0b0010) для червей и 1 (0b0001) ) для лопат
• Мы перебираем каждый возможный ранг (от 0 для двойки до 12 для туза) и каждую возможную масть.
• Мы используем битовый сдвиг для правильной установки битов в целое число карты: сдвиг влево rank на 8, сдвиг влево suit на 12 и сдвиг влево бита ранга, 1 << rank, на 16
• Наконец, мы используем побитовое или |, чтобы соединить наши установленные биты вместе, как бутерброд PB&J, затем push каждый в наш массив результатов и возвращаем его.

Результат выглядит так:

fullDeck()
--> [
//    clubs   diamonds     hearts     spades
      98306,     81922,     73730,     69634, // 2
     164099,    147715,    139523,    135427, // 3
     295429,    279045,    270853,    266757, // 4
     557831,    541447,    533255,    529159, // 5
    1082379,   1065995,   1057803,   1053707, // 6
    2131213,   2114829,   2106637,   2102541, // 7
    4228625,   4212241,   4204049,   4199953, // 8
    8423187,   8406803,   8398611,   8394515, // 9
   16812055,  16795671,  16787479,  16783383, // 10
   33589533,  33573149,  33564957,  33560861, // J
   67144223,  67127839,  67119647,  67115551, // Q
  134253349, 134236965, 134228773, 134224677, // K
  268471337, 268454953, 268446761, 268442665  // A
]

В репозитории / пакете для этого сообщения в блоге вы увидите, что я добавил shuffle аргумент к fullDeck(), который рандомизирует порядок возвращаемого массива «колода». Это нетрудно понять, поэтому я не буду здесь объяснять это для краткости; не стесняйтесь убедиться, что fullDeck( shuffled ).slice( 47 ) - это все равно что «вытащить» 5 верхних карт из перетасованной «колоды».

Безупречная цена: оценка рук с помощью таблиц поиска и идеальной хеш-функции

Теперь, когда у нас есть «колода» (Array( 52 )) «карт», пора приступить к тяжелой работе: разбору рук.

Вы также увидите, что я перевел некоторые массивы из исходного кода CactusKev на C и вставил их в файл с именем lookupTables.js, который выглядит так:

exports.flushes = [
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1599, 0, 0, 0, 0, 0, 0, 0, 1598, 0, 0, 0, 1597, 0, 1596,
  ...and so on
];
exports.fiveUniqueCards = [
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 1608, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 7462, 0, 0, 0, 0, 0, 0, 0, 7461, 0, 0,  0,  7460,  0,
  ...and so on
];
exports.hashAdjust = [0, 5628, 7017, 1298, 2918, 2442, 8070, 6383, 6383, 7425, 2442, 5628, 8044, 7425, 3155, 6383, 2918, 7452, 1533, 6849, 5586, 7452, 7452, 1533, 2209, 6029, 2794, 3509, 7992, 7733, 7452, 131, 6029, 4491, 1814, 7452, 6110, 3155, 7077, 6675, 532, 1334, 7555, 5325, 3056, 1403, 1403, 3969, ...and so on ];
exports.hashValues = [
  148, 2934,  166, 5107, 4628,  166,  166,  166,
  166, 3033,  166, 4692,  166, 5571, 2225,  166,
  5340, 3423,  166, 3191, 1752,  166, 5212,  166,
  166, 3520,  166,  166,  166, 1867,  166, 3313,
  166, 3461,  166,  166, 3174, 1737, 5010, 5008,
  166, 4344, 2868, 3877,  166, 4089,  166, 5041,
  ...and so on
];

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

Давайте посмотрим на функцию в нашем index.js файле, которая использует эти таблицы поиска, и разберем ее. Начнем с некоторых функций для выполнения наших побитовых операций:

exports.flush = hand => hand.reduce( ( total, card ) => total & card, 0xF000 );
// same as exports.flush = hand => hand[ 0 ] & hand[ 1 ] & hand[ 2 ] & hand[ 3 ] & hand[ 4 ] & 0xF000;
exports.flushBitPattern = flush => flush.reduce( ( total, card ) => total | card , 0 ) >>> 16;
// same as exports.flushBitPattern = hand => ( hand[ 0 ] | hand[ 1 ] | hand[ 2 ] | hand[ 3 ] | hand[ 4 ] ) >>> 16;
exports.flushRank = flush => flushes[ this.flushBitPattern( flush ) ];
exports.fiveUniqueCardsRank = hand => fiveUniqueCards[ this.flushBitPattern( hand ) ];

Оказывается, при таком представлении карт поразрядная обработка каждой карты в руке с 0xF000 вернет 0, если рука не является флешем! Еще более невероятно то, что поразрядная обработка каждой карты в руке и сдвиг результата вправо на 16 бит даст индекс, указывающий на элемент одной из наших двух таблиц поиска, flushes или fiveUniqueCards, соответствующие рангу этой руки , если рука флеш или имеет пять уникальных карт. Попробуйте и убедитесь сами!

Обратите особое внимание на то, что в приведенном выше коде мы используем беззнаковый оператор сдвига >>>! Это связано с тем, что JavaScript не является языком со строгой типизацией, как C; мы получим несколько странно неверных индексов, если воспользуемся оператором сдвига "садового разнообразия" >>. Не стесняйтесь читать это сообщение в блоге, которое я написал, объясняющее слабую типизацию в JavaScript, чтобы глубже погрузиться в то, почему это важно здесь.

Если рука не flush и не содержит fiveUniqueCards, мы в следующий раз проверим, нет ли двойки или тройки. Вот где наши простые числа войдут в стадию справа:

exports.primeMultiplicand = hand => hand.reduce( ( total, card ) => total * ( card & 0xFF ), 1 );
// same as exports.primeMultiplicand = hand => ( hand[ 0 ] & 0xFF ) * ( hand[ 1] & 0xFF ) * ( hand[ 2 ] & 0xFF ) * ( hand[ 3 ] & 0xFF ) * ( hand[ 4 ] & 0xFF );
exports.findFast = u => {
  u += 0xe91aaa35;
  u ^= u >>> 16;
  u += u << 8;
  u ^= u >>> 4;
  let a  = ( u + ( u << 2 ) ) >>> 19;
  return a ^ hashAdjust[ ( u >>> 8 ) & 0x1ff ];
};
exports.handRank = hand => {
  if ( this.flush( hand ) ) return this.flushRank( hand );
  let fiveUniqueCardsRank = this.fiveUniqueCardsRank( hand );
  if ( fiveUniqueCardsRank ) return fiveUniqueCardsRank;
  return hashValues[ this.findFast( this.primeMultiplicand( hand ) ) ];
};

Сначала мы определяем метод primeMultiplicand, который поразрядно присваивает каждой карточке значение 0xFF. Это вырезает простое число, соответствующее рангу карты, с конца карты и умножает их все вместе.

Это простое множимое, к сожалению, очень велико, слишком велико для прямого использования в качестве индекса в таблице поиска, как в случае с flushes и fiveUniqueCards, поэтому нам потребуется небольшая оптимизация с помощью метода под названием findFast - a идеальная хеш-функция. Идеальные хэш-функции преобразуют данные в целые числа, без конфликтов - никакие два элемента никогда не дадут одинаковый результат. Идеальные хэши часто используются вместе с таблицами поиска, и они широко используются при управлении данными и мониторинге сети. В этом случае они переводят primeMultiplicand руки в индекс в таблице поиска, содержащий ранги для пар, двух пар, тройки и фулл-хаусов.

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

exports.handRank = hand => {
  if ( this.flush( hand ) ) return this.flushRank( hand );
  let fiveUniqueCardsRank = this.fiveUniqueCardsRank( hand );
  if ( fiveUniqueCardsRank ) return fiveUniqueCardsRank;
  return hashValues[ this.findFast( this.primeMultiplicand( hand ) ) ];
};
exports.handValue = hand => {
  const value = this.handRank( hand );
  if ( value > 6185 ) return "High card";
  else if ( value > 3325 ) return "One pair";
  else if ( value > 2467 ) return "Two pair";
  else if ( value > 1609 ) return "Three of a kind";
  else if ( value > 1599 ) return "Straight";
  else if ( value > 322 )  return "Flush";
  else if ( value > 166 )  return "Full house";
  else if ( value > 10 )   return "Four of a kind";
  else return "Straight flush";
};
...in the console...
drawFive = fullDeck( true ).slice( 0, 5 );
console.log( drawFive.map( cactus.cardName ) );
--> [ 'Nine of Clubs', 'Ten of Clubs', 'Six of Clubs', 'Nine of Diamonds', 'Five of Diamonds' ]
console.log( cactus.handValue( drawFive ) );
--> 4601
console.log( cactus.handRank( drawFive ) );
--> One pair

Заключение и дальнейшее чтение

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

• Coding The Wheel - это очень забавный и информативный блог с наиболее удобоваримым резюме покерных алгоритмов в Интернете, включая таблицы поиска CactusKev и их различные варианты / улучшения.
• Этот набор конспектов лекций от Университета Карнеги-Меллона представляет собой интересное (но подробное) введение в идеальное хеширование и его приложения.
• Эта веб-страница была добавлена ​​в закладки более десяти лет - Шон Эрон Андерсон из Стэнфордского университета делится некоторыми умопомрачительными приемами манипулирования битами, многие из которых полагаются на широко по таблицам поиска