Poll

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

3 members have voted

socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
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
  • Threads: 13
  • Posts: 770
Joined: May 1, 2012
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
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
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
  • Threads: 13
  • Posts: 770
Joined: May 1, 2012
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
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
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
  • Threads: 13
  • Posts: 770
Joined: May 1, 2012
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
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
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
  • Threads: 8
  • Posts: 1911
Joined: May 10, 2011
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
  • Threads: 13
  • Posts: 770
Joined: May 1, 2012
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
  • Threads: 90
  • Posts: 6814
Joined: Oct 28, 2012
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
Sabretom2
Sabretom2
  • Threads: 11
  • Posts: 718
Joined: Mar 3, 2013
July 2nd, 2013 at 11:45:22 AM permalink
Silly me, I was expecting to see a BJ analysis. Wrong site??
socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
July 2nd, 2013 at 12:12:52 PM permalink
edit: @crystalmath:

Thanks. It's nice to have points for comparison. Is the code public? Are you using mostly linear or recursive algorithms?

I've started to read Eric Farmer's code a couple of times, but it's highly optimized for speed and rather long, and I keep glazing over. I've found a couple of other public BJ programs (CA and sim) in the 1-2k line range. OOM was probably a slight stretch in terms of code volume, but I haven't seen anything that's 500 lines.

I'm taking another look at multiple decks now, using something like Nairn's algorithm( http://www.cof.orst.edu/cof/wse/faculty/Nairn/papers/splitting.pdf ). I wish I could see that code. The code in the appendix's doesn't seem to cover section 2.4 - dealer caching. It looks like he's allocating a large, sparse, array for his jx11 cached values, but if he's just using upcards for keys, it makes me wonder if he's caching intermediate dealer results. I'm wondering if I can tradeoff the extra lookup time in clojure's high branching(log32) data types for the sparseness, and add intermediate dealer caching. I'm kind of tired and can't get it all straight in my head at the moment.
socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
July 2nd, 2013 at 1:07:32 PM permalink
For the record, I mostly posted my code here as a sortof show of good faith. At the end of my last request-for-help thread, a couple of months ago, I listed several potential future uses for my code including performing calculations for "myself and friends". Baring any commercial uses, I didn't intend to keep my code private and I thought I might've come off as being a bit unappreciative.

Additionally, I'd hoped that people could see the basic shape of my code, the mutual recursion for player decisions, leading to a dealer subtree, with depth first transversal for memoization, but I was never really asking for a critique. In retrospect, I might should've just posted an explanation since I don't really expect anyone here to have experience in lisps.
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1911
Joined: May 10, 2011
July 2nd, 2013 at 1:14:20 PM permalink
Quote: socks

edit: @crystalmath:

Thanks. It's nice to have points for comparison. Is the code public? Are you using mostly linear or recursive algorithms?

I've started to read Eric Farmer's code a couple of times, but it's highly optimized for speed and rather long, and I keep glazing over. I've found a couple of other public BJ programs (CA and sim) in the 1-2k line range. OOM was probably a slight stretch in terms of code volume, but I haven't seen anything that's 500 lines.

I'm taking another look at multiple decks now, using something like Nairn's algorithm( http://www.cof.orst.edu/cof/wse/faculty/Nairn/papers/splitting.pdf ). I wish I could see that code. The code in the appendix's doesn't seem to cover section 2.4 - dealer caching. It looks like he's allocating a large, sparse, array for his jx11 cached values, but if he's just using upcards for keys, it makes me wonder if he's caching intermediate dealer results. I'm wondering if I can tradeoff the extra lookup time in clojure's high branching(log32) data types for the sparseness, and add intermediate dealer caching. I'm kind of tired and can't get it all straight in my head at the moment.



Sorry, the code is not public, nor is it very fast, but plenty fast for my purposes. I use recursion and I cache intermediate dealer results, which does speed it up, but I don't remember the details. The most agonizing part is for splitting, because I take into account the split card that you know is missing. To help out, I estimate the return for a split using the standard hands I've calculated, and I only calculate the split if it is close enough to be a possibility.
I heart Crystal Math.
socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
July 2nd, 2013 at 10:31:48 PM permalink
Quote: CrystalMath

Sorry, the code is not public, nor is it very fast, but plenty fast for my purposes. I use recursion and I cache intermediate dealer results, which does speed it up, but I don't remember the details. The most agonizing part is for splitting, because I take into account the split card that you know is missing. To help out, I estimate the return for a split using the standard hands I've calculated, and I only calculate the split if it is close enough to be a possibility.



Interesting. Thanks. My goal wrt speed is simply to keep it in the usable range, not to make it fast.

As I understand it, the Nairn method calculates the dealer endpoint frequencies for given a shoe(or the cards that are out), and then caches them, thereby taking all removed cards into account whether they're in the player's hand, the dealer's hand, or removed by split.
AcesAndEights
AcesAndEights
  • Threads: 67
  • Posts: 4300
Joined: Jan 5, 2012
October 30th, 2013 at 9:11:12 PM permalink
I say if you enjoy it, continue. IMO learning and using a functional language is a huge workout for your brain as a programmer and you'll be better for it. I'm trying to set aside some time to do the same, since I mostly code in Java all day, which gets boring.

Anyway, I can't read Clojure at a glance and don't have the time/inclination to learn it at this very moment. But good on ya. Hard to imagine this analysis can fit in 100 lines of code!

I do agree with Money about the magic numbers though, if you continue to build on this.
"So drink gamble eat f***, because one day you will be dust." -ontariodealer
socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
November 4th, 2013 at 4:36:10 PM permalink
Quote: AcesAndEights

I say if you enjoy it, continue. IMO learning and using a functional language is a huge workout for your brain as a programmer and you'll be better for it. I'm trying to set aside some time to do the same, since I mostly code in Java all day, which gets boring.

Anyway, I can't read Clojure at a glance and don't have the time/inclination to learn it at this very moment. But good on ya. Hard to imagine this analysis can fit in 100 lines of code!

I do agree with Money about the magic numbers though, if you continue to build on this.



Thanks. The goal was to learn clojure and to make something that filled a new niche, hopefully profitable, but at least, useful. My work on it slowed, but hasn't stopped and I'm still hoping it turns out to be useful.

Clojure is hard to read. "Unpack" might be more appropriate. But there are so many bonuses, being able to pass functions around as easily as anything else, almost seamless concurrency... You should give it a try as soon as you have the chance. The JVM interop is good and a lot of people sneak it in at work.

John
AcesAndEights
AcesAndEights
  • Threads: 67
  • Posts: 4300
Joined: Jan 5, 2012
November 4th, 2013 at 6:00:08 PM permalink
Quote: socks

Thanks. The goal was to learn clojure and to make something that filled a new niche, hopefully profitable, but at least, useful. My work on it slowed, but hasn't stopped and I'm still hoping it turns out to be useful.

Clojure is hard to read. "Unpack" might be more appropriate. But there are so many bonuses, being able to pass functions around as easily as anything else, almost seamless concurrency... You should give it a try as soon as you have the chance. The JVM interop is good and a lot of people sneak it in at work.

John


If I do try to "sneak" anything in at work, it will probably be Scala - we already have a few rogue principal engineers here writing stuff in Scala :). Same interop win with the JVM.
"So drink gamble eat f***, because one day you will be dust." -ontariodealer
socks
socks
  • Threads: 15
  • Posts: 364
Joined: Jul 13, 2011
November 4th, 2013 at 6:30:36 PM permalink
Quote: AcesAndEights

If I do try to "sneak" anything in at work, it will probably be Scala - we already have a few rogue principal engineers here writing stuff in Scala :). Same interop win with the JVM.



I think we're already corrupting the local (not Vegas) scala meetup. Last week, one of them commented that while his coursera study group liked scala, none of them seemed as excited about it as every clojure programmer he talked to, generally people who he respected.
  • Jump to: