Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Sun Jun 16, 2019 7:00 am

All times are UTC




Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Fri Feb 14, 2014 2:59 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Hello guys,
I am pretty new to all this stuff (not poker, but poker programming etc.). I recently decided to test my programming skills (I have been learning c#) and create an Omaha Hand Evaluator (and later maybe something more with it).

I decided to start with Keith Rule's library. The concepts of look up tables and storing cards as bitmasks and even working with bitmasks was pretty new to me, but I think I got the basic idea of it.

So after spending several hours on it, I finally managed to write a function called HandOddsOmaha, which is basically a copy of the function HoldemHand.HandOdds (stored in HandAnalysis.cs), but works for Omaha.

It basically just splits the 4-card starting hand into 6 2-card combinations and then when iterating through all possible boards using Keith's code ( foreach (ulong boardhand in Hands(boardmask, deadcards_mask, 5)) ), it also splits every 5-card board into several 3 card boards and combines each 2-card starting hand with each 3-card board, ie. 60 combinations for each 5-card board iteration.

It works just fine, but the problem is that it is too slow now, at least for empty board calculations (if there is a flop then its pretty much instant). It takes around 20s to iterate through those 1M+ possible boards.

Now I am a little stuck and would like your help in optimizing it. I know Odds Oracle can do the same calculations in less than one second, so more than 20 times faster.

Here is the whole code of the HandOddsOmaha function:

Code:
        public static void HandOddsOmaha(string[] pockets, string board, string dead, long[] wins, long[] ties, long[] losses, ref long totalHands)
        {
            ulong[][] pocketmasks = new ulong[pockets.Length][];
            ulong[][] pockethands = new ulong[pockets.Length][];
            int count = 0, bestcount = 0;
            ulong boardmask = 0UL;
            ulong deadcards_mask = 0UL, deadcards = Hand.ParseHand(dead, ref count);

            totalHands = 0;
            deadcards_mask |= deadcards;

            // Split 4 Omaha holecards into 6 combinations of Holdem 2 cards
            string[][] splitPockets = new string[pockets.Length][];
            for (int k = 0; k < splitPockets.Length; k++)
            {
                int index = 0;
                splitPockets[k] = new string[6];
                for (int i = 0; i < 4; i++)
                {
                    for (int j = i + 1; j < 4; j++)
                    {
                        splitPockets[k][index++] = pockets[k].Substring(i * 2, 2) + pockets[k].Substring(j * 2, 2);
                    }
                }
            }

            // Read pocket cards
            for (int i = 0; i < pockets.Length; i++)
            {
                count = 0;
                Hand.ParseHand(pockets[i], "", ref count);
                if (count != 4)
                    throw new ArgumentException("There must be four pocket cards."); // Must have 4 cards in each pocket card set.
               
                pocketmasks[i] = new ulong[6];
                pockethands[i] = new ulong[6];
                for (int j = 0; j < 6; j++)
                {
                    pocketmasks[i][j] = Hand.ParseHand(splitPockets[i][j], "", ref count);
                    deadcards_mask |= pocketmasks[i][j];
                }

                wins[i] = ties[i] = losses[i] = 0;
            }

            // Read board cards
            count = 0;
            boardmask = Hand.ParseHand("", board, ref count);
/*
#if DEBUG
            Debug.Assert(count >= 0 && count <= 5); // The board must have zero or more cards but no more than a total of 5

            // Check pocket cards, board, and dead cards for duplicates
            if ((boardmask & deadcards) != 0)
                throw new ArgumentException("Duplicate between cards dead cards and board");

            // Validate the input
            for (int i = 0; i < pockets.Length; i++)
            {
                for (int j = i + 1; j < pockets.Length; j++)
                {
                    if ((pocketmasks[i] & pocketmasks[j]) != 0)
                        throw new ArgumentException("Duplicate pocket cards");
                }

                if ((pocketmasks[i] & boardmask) != 0)
                    throw new ArgumentException("Duplicate between cards pocket and board");

                if ((pocketmasks[i] & deadcards) != 0)
                    throw new ArgumentException("Duplicate between cards pocket and dead cards");
            }
#endif
*/

            // Iterate through all board possibilities that don't include any pocket cards.
            foreach (ulong boardhand in Hands(boardmask, deadcards_mask, 5))
            {
                ulong bestpocket = 0;
                int n = 0;
                ulong[] cards = new ulong[5];
                int index = 0;
                while (n < 64 && index < 5)
                {
                    if ((boardhand & 1UL << n) != 0) // if n-th bit is 1, then assign card
                        cards[index++] = 1UL << n;
                    n++;
                }
                ulong[] boards = null;
                boards = new ulong[] { cards[0] | cards[1] | cards[2], cards[0] | cards[1] | cards[3], cards[0] | cards[1] | cards[4],
                    cards[0] | cards[2] | cards[3], cards[0] | cards[2] | cards[4], cards[0] | cards[3] | cards[4], cards[1] | cards[2] | cards[3],
                    cards[1] | cards[2] | cards[4], cards[1] | cards[3] | cards[4], cards[2] | cards[3] | cards[4] };               

                ulong[] result = new ulong[pockets.Length];
                int actualBestPlayer = 0;
                for (int i = 0; i < pockets.Length; i++)
                {
                    result[i] = 0;
                    foreach (ulong p in pocketmasks[i])
                    {
                        foreach (ulong b in boards)
                        {
                            if (result[i] < Evaluate(p | b))
                                result[i] = Evaluate(p | b);
                           
                            if (bestpocket < result[i])
                            {
                                bestpocket = result[i];
                                bestcount = 1;
                                actualBestPlayer = i;
                            }
                            else if (bestpocket == result[i] && i != actualBestPlayer)
                            {
                                bestcount++;
                            }
                        }
                    }
                }

                // Calculate wins/ties/loses for each pocket + board combination.
                for (int i = 0; i < pockets.Length; i++)
                {
                    if (result[i] == bestpocket)
                    {
                        if (bestcount > 1)
                        {
                            ties[i]++;
                        }
                        else
                        {
                            wins[i]++;
                        }
                    }
                    else if (result[i] < bestpocket)
                    {
                        losses[i]++;
                    }
                }

                totalHands++;

            }
        }


Thanks for any help.
Joe


Top
 Profile  
 
PostPosted: Fri Feb 14, 2014 4:38 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
So atm I got it down to about 7 sec (from 20-21s, so 3x improvement).

These are the improvements:

Code:
// if current best hand beats current 7 card hand (hole + whole board), we dont need to test it
                        if (bestpocket > Evaluate(p | boardhand))
                            continue;


Code:
// if the very last tested player has the best hand already, there is no need to test the rest
                                if (actualBestPlayer == pockets.Length - 1)
                                {
                                    bestHandFound = true;
                                    break;
                                }


(Whole section to make it clear where it belongs)
Code:
                for (int i = 0; i < pockets.Length; i++)
                {
                    result[i] = 0;

                    foreach (ulong p in pocketmasks[i])
                    {
                        // if current best hand beats current 7 card hand (hole + whole board), we dont need to test it
                        if (bestpocket > Evaluate(p | boardhand))
                            continue;

                        foreach (ulong b in boards)
                        {
                            if (result[i] < Evaluate(p | b))
                                result[i] = Evaluate(p | b);
                           
                            if (bestpocket < result[i])
                            {
                                bestpocket = result[i];
                                bestcount = 1;
                                actualBestPlayer = i;
                               
                               // if the very last tested player has the best hand already, there is no need to test the rest
                                if (actualBestPlayer == pockets.Length - 1)
                                {
                                    bestHandFound = true;
                                    break;
                                }
                            }
                            else if (bestpocket == result[i] && i != actualBestPlayer)
                            {
                                bestcount++;
                            }
                        }
                        if (bestHandFound) break;
                    }
                }


Still it is way too slow and I am kind of getting out of ideas (except maybe optimizing usage of variables and trying to use switch instead of ifs, etc.).


Top
 Profile  
 
PostPosted: Fri Feb 14, 2014 6:16 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 557
I'm assuming you are finding the chance of each of several players holding the best showdown hand.

If you just want to improve the preflop you might try Monte Carlo simulation. Another option would be to build a lookup table of any hand against any other hand. This wouldn't be as large as you might expect because of hand isomorphisms (there are only 16432 distinct 4 card hands), but might still have to go onto disk. You'd still have to solve the problem when there are more than two players. Another option would be to exploit the hand isomorphisms to decrease the number of evaluations you have to do. Poker Stove uses techniques like that, so you might find some clues there https://github.com/andrewprock/pokerstove

According to http://www.poker-ai.org/archive/www.pok ... l?f=3&t=16 poker eval was roughly 4 times slower than the rayw/2+2 solution, so building a omaha version of that would help both pre and post flop but would be hard work.


Top
 Profile  
 
PostPosted: Sat Feb 15, 2014 7:51 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Thanks for the links and suggestions, I will explore them further.

Btw, I am really surprised how little Omaha related code there is publicly available, considering the amount of code available for Holdem.


Top
 Profile  
 
PostPosted: Sat Feb 15, 2014 10:07 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 557
There is this too http://pokersource.sourceforge.net/


Top
 Profile  
 
PostPosted: Mon Feb 17, 2014 10:55 pm 
Offline
Veteran Member

Joined: Mon Mar 04, 2013 9:40 pm
Posts: 262
I have been working on a PLO bot for awhile now and have been using the commercial product Pro Poker Tools for equity calculations using their command line tool. It is java based and fast enough if you do not feel like coding an equity engine yourself.


Top
 Profile  
 
PostPosted: Fri Feb 28, 2014 2:06 am 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Thanks for the recommendation, but I am actually mostly interested in coding my own evaluator engine for Omaha.

So far I wrote an EvaluateOmaha(ulong handMask, ulong boardMask, int numberOfBoardCards) function based on the Keith Rule's library and using a lot of same/similar techniques. It is definately way faster than my previous approach, which was to evaluate every omaha hand by iterating through all possible 2-card combinations from the holeCards and all possible 3-card combinations from the boardCards and using the original holdem version of the Evaluate function.

On my not-so-fast computer, it can evaluate around 1.9M hands per second. (For comparison, the original Evaluate function can evaluate around 16.5M 7-card holdem hands, so EvaluateOmaha is around 8.5 times slower.)

It can exhaustively calculate an Omaha Headsup allin preflop in about 1.25s, going through all the 1 086 008 boards ( = C(44, 5) ). I further intend to use board isomorphism to reduce the number of boards I need to iterate through. I believe quite a significant reduction can be achieved here (as oppossed to possible reductions in the actual EvaluateOmaha function).

I would be quite interested to know what results others were able to get, for comparison, so that I know what to aim for. So anyone reading this who has an omaha evaluator of their own, please let me know what results you are getting.

EDIT: after a couple small improvements (mostly using nBitsTable instead of Bitcount for counting bits), it now takes only 0.64s to calculate an allin preflop. And the benchmark shows it can evaluate around 4.27M hands per second (or about 3.85 times less than the original Evaluate for 7-card-holdem-hand).


Top
 Profile  
 
PostPosted: Sat Mar 01, 2014 2:39 am 
Offline
Junior Member

Joined: Tue Mar 05, 2013 2:24 pm
Posts: 11
Guess I'm a bit late, but a few years back I wrote an omaha-hi evaluator in C++. It does about 25M random hole and board combinations per second per core (Win32 at a 2.4 Ghz laptop).
I stopped tweaking it when it stopped being the bottleneck of my simulator, but I guess minor modifications could double its speed if needed.

At least back then most Omaha evaluators floating around were pretty slow, so if there's enough interest I can clean up the code and upload it.

Always fun to see other people taking a stab at PLO :)


Top
 Profile  
 
PostPosted: Sat Mar 01, 2014 9:42 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Hey pulser. Yea I would definately be happy to take a look.

What approach do you use?


Top
 Profile  
 
PostPosted: Sun Mar 02, 2014 6:52 pm 
Offline
Junior Member

Joined: Tue Mar 05, 2013 2:24 pm
Posts: 11
Basically a naive approach ruling out options as it goes along with a lot of branching and bit-manipulation. Branching makes the job a lot harder for the branch predictor, but besides huge LUTs it's the best way to minimize the amount of instructions.

It takes in one 64-bit integer representing the hand and one representing the table.
It returns an integer where a higher score means a better hand.

It uses no lookup tables what so ever, but parts could be slightly faster if it did.
Most hands are determined with combinations of bitwise complement, and, or, BitScanReverse and bit-shifts.


Top
 Profile  
 
PostPosted: Sun Mar 02, 2014 7:03 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
I use the same approach. Just a few small LUTs to speed up things, copied from Keith Rule's pokereval port library.

I had the most trouble with straights. How do you determine them?

You want to exchange the code to compare and maybe inspire for some speed up? I would definately like to take a look at yours.


Top
 Profile  
 
PostPosted: Tue Mar 04, 2014 10:30 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
UPDATE (I guess mostly for myself when I later want to look back at it, but maybe somebody might find it useful too)

So I managed to improve my evaluator a little bit more.

Decent improvement was to stop using Arrays where not necessary and instead using just regular variables (in my particular case, I had arrays for splitting cards by suits, now I just have 8 regular variables). I was quite surprised how big a difference it made, around 20% speedup this change alone.

Then I slightly improved the part of code which determines straights. Now it first scans for 5+ consecutive cards from all ranks from hole + board and when such a sequence is found, it goes down from the top card of the sequence and checks if there is a 5-card sequence that uses 2+ cards from hole and 3+ cards from board.

And then I decided it wasnt enough and created a lookup table for straights. It has around 10 MB.
(EDIT: I updated the code to speed up straight flushes with it too. Only change needed is to add value to the return value so that it isnt straight but straightflush (4U << HANDTYPE_SHIFT).)

So, currently it can evaluate around 9.2M hands/s. (My PC is slow, it can only evaluate around 16.5M 7-card-holdem hands/s using the original Keith Rule's Evaluate function.) The non-LUT version can evaluate around 7M h/s.
An Omaha headsup preflop all-in is calculated in around 290ms (compared to around 370ms without the straight LUT).


Top
 Profile  
 
PostPosted: Thu Mar 06, 2014 11:46 pm 
Offline
Junior Member

Joined: Tue Mar 05, 2013 2:24 pm
Posts: 11
Quote:
I had the most trouble with straights. How do you determine them?
Sadly my straight calculations are kind of slow too. By far the slowest part of my code.

Code:
//check if straight
//NB: straights can be computed using a lookup-table for further performance increases. 715*1200ish bits..? alternatively 40bits per hand and table
for (int i=8;i>=0;i--) {
   short mask=0x1F<<i;
   if ((mask&totRanks)==mask && AtLeast2bit(holeRanks&mask) && countBits(tableRanks&mask) >2)
      return STRAIGHT_OFFSET+i+1;
}
short mask=0x100F;
if ((mask&totRanks) == mask && AtLeast2bit(holeRanks&mask) && countBits(tableRanks&mask) >2)   //A-5 straight
   return STRAIGHT_OFFSET;

Could be sped up in a number of ways though. Simplest would be preceding it with a check to eliminate known non-straights. Something like if ( AtLeast2bit(totRanks&0x18) | AtLeast2bit(totRanks&0x180) | AtLeast2bit(totRanks&0x1800)) where totRanks is the combined rank-mask of the hand and table. This specific fix would eliminate about half(?) of the cases where you'd have to check for straights.

The fastest way to check straight would be a tiny lookup-table, or storing pre-calculated straight options with the hands and tables. Then just ANDing them together, as it seems I mentioned in the comments.

If you still want it, I'll see if I can cut the code out of my project any time soon. But doubt there's much you can gain. The speed of your evaluator seems to quickly catch up with mine :)

Two nice sources for bit-hacks speeding things up:
http://graphics.stanford.edu/~seander/bithacks.html
http://realtimecollisiondetection.net/blog/?p=78


Top
 Profile  
 
PostPosted: Fri Mar 07, 2014 4:27 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Thank you for the reply.

Yea I am using a LUT for straights now, it has under 5MB as a textfile with indexes and values. Index is calculated as Index = (holeRanks * 7937 + boardRanks), where 7937 is the width ( 1 + 7936 which is mask for AKQJT = highest possible board). I am now using a couple other LUTs, a flush LUT and a LUT for no pair in the hole and no pair on board. The speed is currently around 10M hands / second on my slow PC.

Before I was using a similar code as yours (except I first checked if there is a 5+ consecutive bits sequence from all 9 cards and then just tried from the top card of the sequence down, if 2+ cards are from hole and 3+ from board).

Code:
// CHECK for STRAIGHT
            // if its not a flush, check for straight
            if (retval == 0 && nBitsTable[allRanks] >= 5)
            {
                uint allRanks2;
                if ((allRanks2 = (allRanks & (allRanks << 1))) != 0 &&
                    (allRanks2 &= (allRanks << 2)) != 0 &&
                    (allRanks2 &= (allRanks << 3)) != 0 &&
                    (allRanks2 &= (allRanks << 4)) != 0)
                {
                    do
                    {
                        // 31U = 11111 in binary, mask for the 65432 straight; left shifting the mask gives all other straights
                        uint straightMask = 31U << (topCardTable[allRanks2] - 4);
                        if ((nBitsTable[straightMask & holeRanks] >= 2) && (nBitsTable[straightMask & boardRanks] >= 3))
                        {
                            retval = HANDTYPE_VALUE_STRAIGHT + (uint)(topCardTable[allRanks2] << TOP_CARD_SHIFT);
                            break;
                        }
                        allRanks2 ^= (1U << topCardTable[allRanks2]);
                    } while (allRanks2 != 0);
                }
                if (retval == 0)
                {
                    // 4111U = 1000000001111 in binary, mask for the wheel (A5432) straight
                    if (((4111U & allRanks) == 4111U) && (nBitsTable[4111U & holeRanks] >= 2) && (nBitsTable[4111U & boardRanks] >= 3))
                    {
                        retval = HANDTYPE_VALUE_STRAIGHT + (3U << TOP_CARD_SHIFT);
                    }
                }
            } // end of CHECK for STRAIGHT


I would still like to have a look at your evaluator code if you dont mind. Also if you dont mind sharing, how do you create ranges of cards, if you do? I mean for example from a string "AAhh:(23+,35+)", ie. PPT style. That is what I am working on now and it seems tougher than i thought.


Top
 Profile  
 
PostPosted: Fri Mar 07, 2014 5:32 pm 
Offline
Junior Member

Joined: Tue Mar 05, 2013 2:24 pm
Posts: 11
Attached a standalone version of the code here, with a simple profiler running 10 mill random hands. Seems it only does 17M hands/s for me now, not sure if it's my compiler settings or if I did something wrong last time i tested it.

Didn't go through the comments, but guess they can be ignored for the most part :p

Quote:
Also if you dont mind sharing, how do you create ranges of cards, if you do? I mean for example from a string "AAhh:(23+,35+)", ie. PPT style. That is what I am working on now and it seems tougher than i thought.
Guess I could share code for this too, but don't think I'll do so publicly.

Anyway, I read in hands at a format similar to what you mentioned, creating Range-objects hierarchically, combined with and or or links. After connecting all the rules it feeds hands through the different Rule-filters, eventually storing the final range as Hand-objects in a vector.

In no way rocket science, but it allows for complex combination of rules and a fast final product.


Attachments:
File comment: C++ Omaha Hand Evaluator Source Code.
Source.7z [3.76 KiB]
Downloaded 284 times
Top
 Profile  
 
PostPosted: Sat Mar 08, 2014 5:52 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Thanks for the code.

I jut ran it and I dunno if I am doing something wrong (I am noob with using VS and c++, even had trouble getting it to run lol) or if my PC is really that slow, but it takes around 4.3s to evaluate those 10M hands (= 2.3M hands per second evaluated). Really the difference is just weirdly huge, 2.3M vs 17M you said you were getting.

My system is 6 years old, but still works fine for most things.
The specs are:
- Win7 64bit
- Intel Core 2 Quad Q9300 @ 2.50 GHz
- RAM 4 GB DDR2 @ 332 MHz


Top
 Profile  
 
PostPosted: Sat Mar 08, 2014 6:27 pm 
Offline
Junior Member

Joined: Tue Mar 05, 2013 2:24 pm
Posts: 11
That does sound really strange.. I'm running a 3 year old laptop and got a little under 600ms with /O2 /Ot /Oi using the visual studio 2012 compiler. :(
Well, well..


Top
 Profile  
 
PostPosted: Sat Mar 08, 2014 7:58 pm 
Offline
Site Admin
User avatar

Joined: Sun Feb 24, 2013 9:39 pm
Posts: 557
Quote:
I jut ran it and I dunno if I am doing something wrong (I am noob with using VS and c++, even had trouble getting it to run lol) or if my PC is really that slow, but it takes around 4.3s to evaluate those 10M hands (= 2.3M hands per second evaluated). Really the difference is just weirdly huge, 2.3M vs 17M you said you were getting.


debug symbols on?


Top
 Profile  
 
PostPosted: Mon Mar 10, 2014 7:36 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Ok I tried again in release mode with all the settings for speed and the results are reasonable now. It takes around 960ms, so around 10.4M hands / sec, which is about the same speed I am getting with my c# evaluator LUTs version.


Top
 Profile  
 
PostPosted: Mon Mar 17, 2014 1:14 pm 
Offline
Junior Member

Joined: Fri Feb 14, 2014 2:45 pm
Posts: 13
Just found out one intestesting thing (for me at least):

If I run my evaluator outside of Visual Studio just by running the .exe in bin/release dir, it can evaluate around 18.5M hands per second. If I run it from VS using the release mode, it can evaluate around 10M hands per second.

I always thought that release mode is the same as running the .exe file outside of VS, apparently not true.

Whats the reason for this behavior? Also, is there a compiler settings in VS that will produce a program with exactly the same speed as running the .exe from outside?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group