Faster poker hand evaluation

Question

I'm trying to use "RayW hand evaluator" approach to get a card combination score (5 best cards out of 7). However I'm having some performance issues with this method. According to sources - using this approach it must be possible to evaluate more than 300 mil hands per second! My result is 10 mills in 1.5 seconds, which is many times slower.

The idea behind "RayW hand evaluator" is following:

The Two Plus Two evaluator consists of a large lookup table containing some thirty-two million entries (32,487,834 to be precise). In order to lookup a given 7-card poker hand, you trace a path through this table, performing one lookup per card. When you get to the last card, the value so obtained is the official equivalence value of the hand

here is how code looks like:

namespace eval
{
public struct TPTEvaluator
{
    public static int[] _lut;

    public static unsafe void Init() // to load a table
    {
        _lut = new int[32487834];
        FileInfo lutFileInfo = new FileInfo("HandRanks.dat");
        if (!lutFileInfo.Exists)
        {throw new Exception("Handranks.dat not found");}

        FileStream lutFile = new FileStream("HandRanks.dat", FileMode.Open, FileAccess.Read, FileShare.ReadWrite, 4096);

        byte[] tempBuffer = new byte[32487834 * 4];
        lutFile.Read(tempBuffer, 0, 32487834 * 4);

        fixed (int* pLut = _lut)
        { Marshal.Copy(tempBuffer, 0, (IntPtr)pLut, 32487834 * 4);}
        tempBuffer = null;
    }

    public unsafe static int LookupHand(int[] cards) // to get a hand strength
    {
        fixed (int* pLut = _lut)
        {
            int p = pLut[53 + cards[0]];
            p = pLut[p + cards[1]];
            p = pLut[p + cards[2]];
            p = pLut[p + cards[3]];
            p = pLut[p + cards[4]];
            p = pLut[p + cards[5]];
            return pLut[p + cards[6]];
        }
    }
}

}

and that's how I test this approach:

    private void button4_Click(object sender, EventArgs e)
    {
        int[] str = new int[] { 52, 34, 25, 18, 1, 37, 22 };

        int r1 = 0;

        DateTime now = DateTime.Now;
        for (int i = 0; i < 10000000; i++) // 10 mil iterations 1.5 - 2 sec
        { r1 = TPTEvaluator.LookupHand(str);} // here
        TimeSpan s1 = DateTime.Now - now;
        textBox14.Text = "" + s1.TotalMilliseconds;
    }

I believe that this method was originally implemented in C++, but nevertheless C# port should work faster. Is there any way how I can get close to at least 100 millions of hands in one sec?

What I tried so far:

• tried using Static, and non-static methods - no difference.

• tried using dictionary lookup instead of array

  public void ArrToDict(int[] arr, Dictionary<int, int> dic)
  {
      for (int i = 0; i < arr.Length; i++)
      {
          dic.Add(i, arr[i]);
      }
  }
  
  public unsafe static int LookupHandDict(int[] cards)
  {
      int p = dict[53 + cards[0]];
      p = dict[p + cards[1]];
      p = dict[p + cards[2]];
      p = dict[p + cards[3]];
      p = dict[p + cards[4]];
      p = dict[p + cards[5]];
      return dict[p + cards[6]];
  }
  

Elapsed time for 10 mills of hands is almost 6 times slower..

• According to one person - he increased the performance by 200 mills by removing "unsafe" code. I tried to do the same thing but results are almost the same.

  public static int LookupHand(int[] cards)
  {
          int p = _lut[53 + cards[0]];
          p = _lut[p + cards[1]];
          p = _lut[p + cards[2]];
          p = _lut[p + cards[3]];
          p = _lut[p + cards[4]];
          p = _lut[p + cards[5]];
          return _lut[p + cards[6]];
  }
  

Here is the quote:

After removing the "unsafe" code parts and some small adjustments in the c# version it is now also around 310 mio.

is there any other way to increase the performance of this hand ranking system?

Answer 1

First - benchmarking is always tricky. Things that perform one way on your machine don't always perform the same way on other machines and there is a lot going on 'under-the-covers' that can invalidate data (like caching done by the OS or even hardware).

Having said that - I took a look at just your Init() method and it left me scratching my head. I found it difficult to follow. My rule of thumb for using 'unsafe' is to not use it, unless I absolutely have to. This Init() method, I'm assuming, gets called once, right? I decided to benchmark it:

static void BenchmarkIt(string input, Action myFunc)
{
    myWatch.Restart();
    myFunc();
    myWatch.Stop();

    Console.WriteLine(input, myWatch.ElapsedMilliseconds);
}

BenchmarkIt("Updated Init() Method:  {0}", Init2);
BenchmarkIt("Original Init() Method: {0}", Init1);  

Where Init1() is your original code and Init2() is my rewritten code (I've also flipped the order several times in the sake of fairness). Here's what I get (on my machine)...

Updated Init() Method: 110

Original Init() Method: 159

Here's the code I used. No unsafe keyword required.

public static void Init2()
{
    if (!File.Exists(fileName)) { throw new Exception("Handranks.dat not found"); }            

    BinaryReader reader = new BinaryReader(File.Open(fileName, FileMode.Open));            

    try
    {
        _lut = new int[maxSize];
        var tempBuffer = reader.ReadBytes(maxSize * 4); 
        Buffer.BlockCopy(tempBuffer, 0, _lut, 0, maxSize * 4);
    }
    finally
    {
        reader.Close();
    }
}

In my opinion, this code is easier to read and it seems to run faster.

I know you are probably more concerned about LookupHand()'s performance, but I wasn't able to make any significant improvements. I tried a few different approaches but nothing that helped.

I was able to run your code 100,000,000 times in 500 milliseconds. I'm running on a fairly beefy 64-bit laptop - which seems to be the speed you were expecting. Like others have said - running in release mode (enabling optimization) can have a big impact on performance.

Answer 2

If you want generic speed, I would suggest using the evaluator at Brecware: https://web.archive.org/web/20160502170946/http://brecware.com/Software/software.html. Steve Brecher's evaluator is faster than the RayW evaluator for evaluations which occur in random order, and is much more compact.

As noted in the comments, the RayW evaluator depends on locality of reference for it's speed. If you're not traversing the evaluations in the exact same order as the lookup tables, it's going to be slow. If that is your problem there are three approaches:

1. Make your evaluation order more closely match the tables.
2. Make tables that match your evaluation order
3. Make an evaluator optimized to your use case.