Quantcast

Maximum PC

It is currently Thu Dec 25, 2014 1:45 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: Poker Hand Evaluator in CL
PostPosted: Fri Mar 05, 2010 12:52 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Hey guys,

A couple of my academic projects have included "poker bots". Poker is an interesting game to program compared to many games due to uncertainty. Scrabble would be another game involving a high-degree of uncertainty. (However, I don't think anyone would be dumb enough to try and "bluff" a computer program by playing an illegal word!) Until recently, I've relied pretty heavily on a popular Java API known as Meerkat to code up the bots. For a couple of new projects, I will need to either extend that API (which has quite a few bugs -- some might call this questionable design decisions -- they're bugs, trust me), copy the API (replacing the ugly parts) or roll my own solution.

One of the first things that I will need to create is a general purpose hand evaluator. One of the more popular hand evaluators is known as the Cactus Kev HE. You can find a short description and the C files for it below. It is basically a bit vector / hashing method for determining the best five card hand.

http://www.suffecool.net/poker/evaluator.html

I've decided to implement this HE in Common Lisp (CL) for a couple of reasons. First, I've haven't done any work with bit vectors in CL and would like to test the waters. CL was designed to be a very wide ranging programming language, and I imagine this is about as far as most of us get from the typical programs that we might encounter in a programming language or AI course. Second, I'm curious to see if the CL implementation is significantly shorter and clearer than the C version (or not!). Third, I'm going to purposely not overly familiarize myself with the entire Cactus Kev project because I also want to test the "bottom up" design waters. I'm curious to see if there is much evolution in the quality of the program. Anyways, I'm going to implement some of it tonight and probably finish it up tomorrow or the next day depending on my schedule. Heck, I might even write some unit tests over the weekend. We'll see how it goes... =)


Top
  Profile  
 
 Post subject:
PostPosted: Fri Mar 05, 2010 1:11 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Note: I forgot to mention in my previous post that using bit vectors is probably not the best way to implement this HE in CL -- we'll see.

First update... There are four C files. One is a header file that contains quite a few defs. I'm going to hold off on this one until later since copying it directly to the CL implementation is probably not going to work that well. One of the files contains mostly precomputed arrays for dealing with the various flush hands (ie a lookup table). This was done this way
to create an extremely fast HE -- I don't think that I'll need to precompute all of these values, but we'll see later on. The other file that I'm going to ignore for the time being tests all possible 52 C 5 hands.

Below are the function definitions for the lib file.
http://www.suffecool.net/poker/code/pokerlib.c


Code:
// perform a binary search on a pre-sorted array
int findit( int key )

One of the things that I did happen to read about the implementation is that Kevin originally used a BST to find some kind of values for the hands. Someone else contributed a hash table implementation that was 2.7x faster. As CL as both of these data structures in the language, I'm going to save this for later.

Code:
//   This routine initializes the deck.  A deck of cards is
//   simply an integer array of length 52 (no jokers).  This
//   array is populated with each card, using the following
//   scheme:
//
//   An integer is made up of four bytes.  The high-order
//   bytes are used to hold the rank bit pattern, whereas
//   the low-order bytes hold the suit/rank/prime value
//   of the card.
//
//   +--------+--------+--------+--------+
//   |xxxbbbbb|bbbbbbbb|cdhsrrrr|xxpppppp|
//   +--------+--------+--------+--------+
//
//   p = prime number of rank (deuce=2,trey=3,four=5,five=7,...,ace=41)
//   r = rank of card (deuce=0,trey=1,four=2,five=3,...,ace=12)
//   cdhs = suit of card
//   b = bit turned on depending on rank of card
init_deck( int *deck )
{
    int i, j, n = 0, suit = 0x8000;

    for ( i = 0; i < 4; i++, suit >>= 1 )
        for ( j = 0; j < 13; j++, n++ )
            deck[n] = primes[j] | (j << 8) | suit | (1 << (16+j));
}


Looks like fun... I'll probably implement this portion of the code tonight (init-deck).

Code:
//  This routine will search a deck for a specific card
//  (specified by rank/suit), and return the INDEX giving
//  the position of the found card.  If it is not found,
//  then it returns -1
int find_card( int rank, int suit, int *deck )


//  This routine takes a deck and randomly mixes up
//  the order of the cards.
shuffle_deck( int *deck )

print_hand( int *hand, int n )


Without really looking at the code, I'm pretty sure that I'll get all of these things for free (or nearly free) in CL, so I'm going to save them for now.

Code:
int hand_rank( short val )
{
    if (val > 6185) return(HIGH_CARD);        // 1277 high card
    if (val > 3325) return(ONE_PAIR);         // 2860 one pair
    if (val > 2467) return(TWO_PAIR);         //  858 two pair
    if (val > 1609) return(THREE_OF_A_KIND);  //  858 three-kind
    if (val > 1599) return(STRAIGHT);         //   10 straights
    if (val > 322)  return(FLUSH);            // 1277 flushes
    if (val > 166)  return(FULL_HOUSE);       //  156 full house
    if (val > 10)   return(FOUR_OF_A_KIND);   //  156 four-kind
    return(STRAIGHT_FLUSH);                   //   10 straight-flushes
}

short eval_5cards( int c1, int c2, int c3, int c4, int c5 )

short eval_5hand( int *hand )

// This is a non-optimized method of determining the
// best five-card hand possible out of seven cards.
// I am working on a faster algorithm.
short eval_7hand( int *hand )


These I'll definitely have to write up. It's getting a bit late, so I'll probably save them for tomorrow though.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Mar 05, 2010 5:10 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
I wish I had time to do something like this... as it stands I have a handful of projects left unfinished.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Mar 05, 2010 1:24 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
I wish I had time to do something like this... as it stands I have a handful of projects left unfinished.

Oh, I know the feeling. I have notepads, folders, and entire boxes of unfinished projects. Lately, I've had a bit more free time and have gotten around to finishing a few of them. I should be doing some Roomba hacking here pretty soon. I'll probably start a thread for that project as well.

--Sleepy. =)


Top
  Profile  
 
 Post subject:
PostPosted: Fri Mar 05, 2010 1:41 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Alright, I'm only one night into the project and I've decided I need to work two branches. The first branch is going to largely mimic the C code. The second branch is going to be more "lispy" and do things like interning symbols (ie using a loop to create the variables) with names like 2s (two of spades). The second branch is necessary in order for me to accomplish my larger project goals.

At the moment, I have some serious doubts about whether all the bit manipulation will improve the performance by more than 10%. I am certain that it won't increase performance by 2.7x like using a hash table instead of the BST. I'll run some tests later today and see how all of that goes... until then, here is the CL c version of the code from last night and some test output. I should have the "lispier" version finished up later today or tonight depending on time constraints.

pokerlib-c.lisp
note: The forums wasn't indenting my code properly so I went in and added some spaces here and there. PITA. Also, I started researching the shuffle routine last night and just happened to come up the shuffle routine that I included below.

Code:
;;   This routine initializes the deck.  A deck of cards is
;;   simply an integer array of length 52 (no jokers).  This
;;   array is populated with each card, using the following
;;   scheme:
;;
;;   An integer is made up of four bytes.  The high-order
;;   bytes are used to hold the rank bit pattern, whereas
;;   the low-order bytes hold the suit/rank/prime value
;;   of the card.
;;
;;   +--------+--------+--------+--------
;;   |xxxbbbbb|bbbbbbbb|cdhsrrrr|xxpppppp|
;;   +--------+--------+--------+--------+
;;
;;   p = prime number of rank (deuce=2,trey=3,four=5,five=7,...,ace=41)
;;   r = rank of card (deuce=0,trey=1,four=2,five=3,...,ace=12)
;;   cdhs = suit of card
;;   b = bit turned on depending on rank of card
;;
(defun init-deck (deck)
  (let ((deck '()))
    (dotimes (suit 4)
      (dotimes (rank 13)
        (push (get-card-vector suit rank) deck)))
    (nreverse deck)))

(defun get-card-vector (suit rank)
  ;;bit selectors for accessing the bits in the diagram above
  ;;and a list containing the prime numbers used for the hashing
  (let ((rank-sel (byte 4 8))
   (suit-start-bit 12)
   (b-start-bit 16)
   (primes (list 2 3 5 7 11 13 17 19 23 29 31 37 41)))
    (dpb 1 (byte 1 (+ b-start-bit rank))             ;set the b bit
      (dpb 1 (byte 1 (+ suit-start-bit suit))     ;set the suit bit
            (dpb rank rank-sel                     ;set the rank bits
         (nth rank primes))))))            ;select the prime hash

;;utility function for checking the bit vectors...
(defun print-card-as-32bit-vector (card)
  (format t "~32b~%" card))

(defun print-test-cases ()
  (let ((msg "A couple of test cases from the Cactus Kev website:")
   (bit-pattern "xxxbbbbbbbbbbbbbcdhsrrrrxxpppppp")
        (t1 "00001000000000000100101100100101    King of Diamonds")
        (t2 "00000000000010000001001100000111    Five of Spades")
   (t3 "00000010000000001000100100011101    Jack of Clubs"))
    (format t "~a~2%~a~%~a~%" msg bit-pattern t1)
    (print-card-as-32bit-vector (get-card-vector 2 11)) 
    (format t "~%~a~%~a~%" bit-pattern t2)   
    (print-card-as-32bit-vector (get-card-vector 0 3)) 
    (format t "~%~a~%~a~%" bit-pattern t3)
    (print-card-as-32bit-vector (get-card-vector 3 9))))

(defun hand-rank (val)
  (cond ((> val 6185) 'high-card) 
   ((> val 3325) 'ONE-PAIR)
   ((> val 2467) 'TWO-PAIR)
   ((> val 1609) 'THREE-OF-A-KIND)
   ((> val 1599) 'STRAIGHT)
   ((> val 322)  'FLUSH)
   ((> val 166)  'FULL-HOUSE)
   ((> val 10)   'FOUR-OF-A-KIND)
   (t            'STRAIGHT-FLUSH)))

(defun hand-rank-tests ()
  (let ((test-values '(7000 4000 3000 1700 1607 400 200 44 4))
   (exp-return-values '(high-card ONE-PAIR TWO-PAIR THREE-OF-A-KIND STRAIGHT
              FLUSH FULL-HOUSE FOUR-OF-A-KIND STRAIGHT-FLUSH)))
    (dotimes (i 9)
      (format t "test #~a  exp: ~a  act: ~a~%"
         (1+ i) (nth i exp-return-values) (hand-rank (nth i test-values))))))

;;This routine takes a deck and randomly mixes up
;;the order of the cards.
(defun shuffle (list)
  (let ((len (length list)))
    (loop for i from 0 to (1- len)
     do (rotatef (elt list i) (elt list (random len)))))
  list)


Output from tests...
Code:
CL-USER> (load "../lisp code/pokerlib-c.lisp")
;; Loading file ..\lisp code\pokerlib-c.lisp ...
;; Loaded file ..\lisp code\pokerlib-c.lisp
T
CL-USER> (print-test-cases)
A couple of test cases from the Cactus Kev website:

xxxbbbbbbbbbbbbbcdhsrrrrxxpppppp
00001000000000000100101100100101    King of Diamonds
    1000000000000100101100100101

xxxbbbbbbbbbbbbbcdhsrrrrxxpppppp
00000000000010000001001100000111    Five of Spades
            10000001001100000111

xxxbbbbbbbbbbbbbcdhsrrrrxxpppppp
00000010000000001000100100011101    Jack of Clubs
      10000000001000100100011101
NIL
CL-USER> (hand-rank-tests)
test #1  exp: HIGH-CARD  act: HIGH-CARD
test #2  exp: ONE-PAIR  act: ONE-PAIR
test #3  exp: TWO-PAIR  act: TWO-PAIR
test #4  exp: THREE-OF-A-KIND  act: THREE-OF-A-KIND
test #5  exp: STRAIGHT  act: STRAIGHT
test #6  exp: FLUSH  act: FLUSH
test #7  exp: FULL-HOUSE  act: FULL-HOUSE
test #8  exp: FOUR-OF-A-KIND  act: FOUR-OF-A-KIND
test #9  exp: STRAIGHT-FLUSH  act: STRAIGHT-FLUSH
NIL
CL-USER>


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 1 guest


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:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group

© 2014 Future US, Inc. All rights reserved.