Poll

1 vote (33.33%)
1 vote (33.33%)
No votes (0%)
1 vote (33.33%)

3 members have voted

socks
socks
Joined: Jul 13, 2011
  • Threads: 15
  • Posts: 364
July 1st, 2013 at 2:31:28 AM permalink
I believe my analyzer produces the correct strategy for an infinite deck (with 3 splits) in about 15s (new mac mini), but it still has bugs that I haven't tracked down. The overall game value is off a bit, and a few of the internal values that aren't used in optimal strategy are off significantly.

The code is in Clojure, a modern Lisp that runs on the JVM. While the code isn't C-like, and my (lack of) coding practices don't help, I mostly wanted to show the potential for compact and expressive code that clojure allows.

I hope you can still see the overall approach. (from-the-top), a function near the bottom of the code, is the starting point. Hit/stand/double/split/surrender are mutually recursive functions that evaluate the game tree from a common dispatch, which calls all possible player choices and orders them by value, returning the best choice. Each player choice checks to see if it is legal given the current game state and returns a large negative number if the choice is not legal. Stand and double both pass control to the dealer function. Most functions are memoized and build a transposition table as the program runs.

After loading the code, call (from-the-top). Give you JVM about 2G before running. View results with (hard-SS17) (soft-SS17) and (pairs). Results will look a bit funny since they use the entire deck1 (4 Tens in each table), and a hard coded a "6" inserted for convenience.

I may or may not release this as open source in the future, but for now, please don't redistribute. Thanks.

 ;blackjack analyzer in Clojure by John Tollison, copyright 2013
(ns myproject.core)

(defmacro defn-memo [name & body] `(def ~name (memoize (fn ~body))))

(def deck1 [2 3 4 5 6 7 8 9 10 10 10 10 1]) ;infinite deck
(def combos (for [i deck1 j deck1] (vec (sort < [i j]))))

(defn doseqfor [deck fn1] ;dual pass for memoizing and averaging game trees, depth first; returns single average value (for given level)
(do (doseq [pos (range (count deck))] (fn1 pos))
(let [vallist (for [pos (range (count deck))] (fn1 pos))]
(/ (apply + vallist) (count deck)))))

(defn-memo rmCard [arr pos] (vec (concat (subvec arr 0 pos) (subvec arr (+ pos 1))))) ;used outside of being hit (dealer or player)
(defn-memo addCard [arr card] (vec (sort < (conj arr card))))

(defn-memo BJHandVal [hand]
(let [tot (reduce + hand)]
(if (and (< tot 12) (= (hand 0) 1)) (+ tot 10) tot)))

(defn-memo dealerhands [[pHand dHand deck splits notes bet :as gm]]
(let [up (dHand 0)
dHands (for [i deck] (vec (sort < [up i])))
hCombos (count dHands)]
(filter #(not= % [1 10]) dHands)))

(defn-memo deal-e5 [[pTot dHand deckS notes :as gm]] ;add pHand, subtract deckS; for non-infinite decks
(let [dTot (BJHandVal dHand)]
(cond (> dTot 21) 1
(or (< dTot 17) (and (< dTot 18) (not= dTot (reduce + dHand)) (notes :hitsoft)))
(doseqfor deck1 #(let [newdeck (rmCard deck1 %) newdHand (addCard dHand (deck1 %))] (deal-e5 [pTot newdHand deck1 notes])))
(= dTot pTot) 0.5
(< dTot pTot) (if (notes :bj) 1.5 1)
(> dTot pTot) 0)))

(defn deal [[pHand dHand deck splits notes bet :as gm]]
(let [nonBJHands (dealerhands gm) pTot (BJHandVal pHand)]
(/ (reduce + (for [hand nonBJHands]
(deal-e5 [pTot hand deck (if (and (= (count pHand) 2) (= 21 (BJHandVal pHand)) (= splits 0)) (conj notes :bj) (disj notes :splitA))])))
(count nonBJHands))))

(declare hit stand doubledown split surrender)
(def ops [hit stand doubledown split surrender])

(defn-memo dispatch [[pHand dHand deck splits notes :as gm]]
(doseq [op ops] (op gm))
(last (sort #(< (% 1) (%2 1)) (for [op ops] (op gm)))))

(defn-memo hit [[pHand dHand deck splits notes bet :as gm]]
["ht" (if (not (notes :splitA))
(doseqfor deck #(let [newdeck (rmCard deck1 %) newpHand (addCard pHand (deck1 %))]
(if (> (BJHandVal newpHand) 21)
-1
((dispatch [newpHand dHand deck1 splits notes bet ]) 1))))
-10000) ])

(defn-memo stand [[pHand dHand deck splits notes bet :as gm]] ["st" (- (* 2 (deal gm)) 1)])

(defn-memo split [[pHand dHand deck splits notes bet :as gm]]
["sp" (if (and (= 2 (count pHand)) (not (notes :splitA)) (= (pHand 0) (pHand 1)) (< splits 3) (not (and (> splits 0) (= (pHand 0) 1))) )
(doseqfor deck #(let [newdeck (rmCard deck1 %) newpHand (vec (sort < [(pHand 0) (deck1 %)]))]
(+ ((dispatch [newpHand dHand deck1 (inc splits) (if (= (pHand 0) 1) (conj notes :splitA) notes) bet]) 1)
((dispatch [newpHand dHand deck1 (inc splits) (if (= (pHand 0) 1) (conj notes :splitA) notes) bet]) 1)) ))
-10000)] )

(defn-memo doubledown [[pHand dHand deck splits notes bet :as gm]]
["DD" (if (and (= (count pHand) 2) (not (notes :splitA))) ;sometimes no DD after split
(doseqfor deck #(let [newdeck (rmCard deck1 %) newpHand (addCard pHand (deck1 %))]
(if (> (BJHandVal newpHand) 21)
-2
(- (* 4 (deal [newpHand dHand deck1 splits notes bet])) 2)) ))
-10000)] )

(defn-memo surrender [[pHand dHand deck splits notes bet :as gm]] ["sr" (if (= (count pHand) 2) -0.5 -10000)])

(defn from-the-top []
(doseq [pHand combos i deck1] (dispatch [pHand deck1 0 #{} 0]))
(- (*
(/ (reduce + (for [pHand combos i deck1] ((dispatch [pHand deck1 0 #{} 0]) 1)))
(* (count combos) (count deck1)))
(/ 161 169) )
(+ (* 8/169 161/169))))

(defn hard-SS17 [] (for [j deck1] (for [k deck1]
[((dispatch [(vec (sort < [6 j])) [k] deck1 0 #{} 0]) 0)
(format "%.6f" (float ((dispatch [(vec (sort < [6 j])) [k] deck1 0 #{} 0]) 1) ))])))

(defn soft-SS17 [] (for [j deck1] (for [k deck1]
[((dispatch [[1 j] [k] deck1 0 #{} 0]) 0)
(format "%.6f" (float ((dispatch [(vec (sort < [6 j])) [k] deck1 0 #{} 0]) 1)))] )))

(defn pairs [] (for [j deck1] (for [k deck1]
[((dispatch [[j j] [k] deck1 0 #{} 0]) 0)
(format "%.6f" (float ((dispatch [[j j] [k] deck1 0 #{} 0]) 1)))] )))
MonkeyMonkey
MonkeyMonkey
Joined: May 1, 2012
  • Threads: 13
  • Posts: 770
July 1st, 2013 at 2:46:59 AM permalink
Not familiar with the language so I can't begin to track down bugs or suggest optimizations, but there sure appear to be a lot of magic numbers going on. Is that a function of how the language works or just your coding practices?
socks
socks
Joined: Jul 13, 2011
  • Threads: 15
  • Posts: 364
July 1st, 2013 at 3:19:54 AM permalink
Quote: MonkeyMonkey

Not familiar with the language so I can't begin to track down bugs or suggest optimizations, but there sure appear to be a lot of magic numbers going on. Is that a function of how the language works or just your coding practices?



I know it's hard to read, so I'm certainly not expecting anyone to help track down bugs.

What do you mean by magic numbers? If you're talking about hard coded numeric literals, some of that's just me, and some are accessing vectors(similar to arrays). (myvector 0) would be myvector[0] in most languages. The vector is accessed as if it were a function, and since vectors can be returned as results, a trailing 0 or 1 can just be accessing a part of the return value. ((dispatch ...) 0) accessed the first entry from the vector returned which is the id text that I'm returning.

%2 represents the second input to an anonymous fn.

I probably should've named the invalid op choice instead of just using -10000, but other than that, I feel like the other numbers mostly relate to the Blackjack problem. -1 for loss, .5 for push value, 1 for a win, 1.5 for BJ. I tend not to name these sorts of values. Maybe I should, but I doubt I will.
MonkeyMonkey
MonkeyMonkey
Joined: May 1, 2012
  • Threads: 13
  • Posts: 770
July 1st, 2013 at 5:03:51 AM permalink
Quote: socks


What do you mean by magic numbers?



The way I was taught numbers should not be littered about the code. Programs have a way of growing, sometimes beyond the wildest dreams of their initial creator. Many times others, not the initial creator will need to make changes.

So, let's say that at some point down the road you want to use this for 6:5 blackjack, you or someone else is going to need to scour the code for instances of 1.5 and then upon finding them determine if they are for calculating a blackjack or something else. The simple answer would be to have a section that defines these values. $blackjack = 1.5; //Or the syntax of your choice. This makes it easy to change, you change it in 1 place and you're virtually assured that the problem has been solved... unless of course another lazy or undisciplined coder has been mucking about.

Quote: socks

... I feel like the other numbers mostly relate to the Blackjack problem. -1 for loss, .5 for push value, 1 for a win, 1.5 for BJ. I tend not to name these sorts of values. Maybe I should, but I doubt I will.



That's fine, it's your code, just don't show it to anyone if you're interviewing for a coding position.
socks
socks
Joined: Jul 13, 2011
  • Threads: 15
  • Posts: 364
July 1st, 2013 at 11:19:23 PM permalink
Yes, I'm admittedly lazy. Maybe it takes a lazy person to want to cram a BJ analyzer into 100 lines. (The logic may be off, but that's the way lazy people think)
MonkeyMonkey
MonkeyMonkey
Joined: May 1, 2012
  • Threads: 13
  • Posts: 770
July 2nd, 2013 at 12:40:25 AM permalink
Quote: socks

Yes, I'm admittedly lazy. Maybe it takes a lazy person to want to cram a BJ analyzer into 100 lines. (The logic may be off, but that's the way lazy people think)



I fail to see what being lazy and wanting to "cram" a program into 100 have to do with each other.

You'll get more for less by writing elegant code, not hard to maintain code. Unless there's a contest that says something like: write a program to do <something useful> in 100 lines or less and win a prize, I can't see any reason to strive for brevity. Brevity for brevity's sake is only going to result in a difficult to understand program (and the magic numbers won't help).

But whatever, write your program any way you want for any reason you like, I don't care.
socks
socks
Joined: Jul 13, 2011
  • Threads: 15
  • Posts: 364
July 2nd, 2013 at 8:39:34 AM permalink
I choose a lazy person to do a hard job. Because a lazy person will find an easy way to do it. Bill Gates

I don't think an order of magnitude reduction in code is "brevity for the sake of brevity". Cut out 90% of the code and things get easier. If you know of code that solves BJ through enumeration with < an OOM increase in code please tell me. I haven't found it. If you must obsess over not naming numeric literals, please don't do it here.
CrystalMath
CrystalMath
Joined: May 10, 2011
  • Threads: 8
  • Posts: 1907
July 2nd, 2013 at 9:19:43 AM permalink
Quote: socks


I don't think an order of magnitude reduction in code is "brevity for the sake of brevity". Cut out 90% of the code and things get easier. If you know of code that solves BJ through enumeration with < an OOM increase in code please tell me. I haven't found it. If you must obsess over not naming numeric literals, please don't do it here.



My blackjack analyzer uses under 500 lines of code, but it is easy to read. It also handles any number of decks, which is a more difficult problem than infinite decks.
I heart Crystal Math.
MonkeyMonkey
MonkeyMonkey
Joined: May 1, 2012
  • Threads: 13
  • Posts: 770
July 2nd, 2013 at 10:13:48 AM permalink
Quote: socks

I choose a lazy person to do a hard job. Because a lazy person will find an easy way to do it. Bill Gates



"Or, more likely, do a piss poor job" -Me.

Quote: socks


I don't think an order of magnitude reduction in code is "brevity for the sake of brevity".



Ok.

Quote: socks

Cut out 90% of the code and things get easier.



I wasn't aware that one followed the other. Interesting.

Quote: socks

If you know of code that solves BJ through enumeration with < an OOM increase in code please tell me. I haven't found it.



I'll do you one better: I don't care. Just the progress on the poll, apparently I'm not alone.

Quote: socks


If you must obsess over not naming numeric literals, please don't do it here.



Oh, does your name appear in green? No? Then you're not a moderator. Alright then, if you don't like comments don't present your work for such. Let me help you out here, I'll add this thread to my block list and you can watch it fade out of sight.

Good luck, bye!
Buzzard
Buzzard
Joined: Oct 28, 2012
  • Threads: 90
  • Posts: 6814
July 2nd, 2013 at 10:20:16 AM permalink
I tried using the Blackjack analyzer between my ears, but Dan Lubin said I was cheating. LOL
Shed not for her the bitter tear Nor give the heart to vain regret Tis but the casket that lies here, The gem that filled it Sparkles yet

  • Jump to: