The Value of Serum Powder

[Sylvester]

You may remember my framework at http://www.themanadrain.com/forums/viewtopic.php?t=15234&start=0&postdays=0&postorder=asc&highlight=. I used this tonight to check out Serum Powder. Basically, i was studying the odds of having a certain two-cards combo on turn 0 with and without powder, while mulliganning down to 5 at most (60 cards deck, 4 of both combo part, 4 powder). After 20k runs (and 65 minutes because i don't have any native compiler for windows), the results are:

With Serum Powder: 44.93%
W/o     "          "     : 34.91%

The odds of having a Powder in our hand or in the 4 topmost cards of the deck when we have a hand we want to keep(both combo pieces are present) are as follows:
Two or more Powders in hand: 1.08%
Only one or more Powders in hand: 5.41%
Only one or more Powder in topmost cards: 9.11%*
1+ Powder in both the hand and the topmost cards: 5.37%

*This result may seem surprising considering that the minimal hand size is 5 cards, and we only look at the top 4 cards of the deck, but keep in mind that for a hand to be kept, both combo pieces must be present, reducing the odds of other cards being in hand at the same time.

Serum Powder lets us have the combo 10.02% more often, but we will pay for this with card disadvantage turn 0 10.78% of the time, and _19.89_% of the time in the first 4 turns.

Conclusions: Serum Powder is sensibly useful; however, the combo must be extremely strong (ie, it must be a real, "i win", combo) for it to be worth the just as extreme card disadvantage. Obviously, Powder is better in decks that must have a combo and yet can't afford to mulligan too much (EDIT: Or, obviously, decks that can use RFGed cards or a smaller deck). I also understand that real decks have tutoring and drawing, but i'm not sure how it affects the results. Overall, nothing really new, but we finally have numerical results to back our intuition.

Are there any interesting cases to be examined in light of these results? Most likely, it'll only take a couple minutes of my time and one hour of my computer's time

[urza_insane]

Holy crap! I wish i understood what you did and or are talking about! Your smart... sounds like a good find, people can finally have some basis for judging the powder thingy.

Thanks!

[BrokenDeck]

When you ran the test, did you include the possibility of removing a combo piece from the game with the powder?

[Sylvester]

BrokenDeck: Yes. Whenever powder is used, the whole hand is removed from the library before recursing. That's why using normal statistical analysis tools like MWS (or my calculator) wasn't really feasible: while mulligans are painful, but doable, with powder, the number of cases that must be separately considered is incredibly high.

I can post the scoring function, if you want, but basically, it passes only the deck minus the first Hand-Size cards when recursing due to Powder (i shouldn't shuffle the deck after RFG the hand, but it's done, and it doesn't affect anything, except for longer runtimes). Unfortunately, because i wanted to check for so many cases at the same time, it's not very pretty - i'll rewrite it much better.

Urza: I basically drew hands 20k times (mulligans/Powder are not counted in the 20k) and marked how much time certain things happened. Except that, in this case, i made my computer do it

[defector]

Do yuo have a linux version of this ware.  This is very clever and useful, thank you for your work.
defector

[Smash]

Link your source, let us check the logic.

[Fëanor]

I'll start by saying, wondefully helpful work Sylvester. You get my cool face of approval

Second I'd Like to delve further into the card itself, based upon not just numbers but specifics. Sure, in combo, it's a big help to get your cards the way you want them. But...based on the kind of hand you end up starting with, might some of those cards be the fuel for your combo?
If that doesn't make sense, I'll put it this way (though more specific and more apt to spring misunderstanding).

If you(the powder user) draw Power with two moxen, two search, one land and one disruption, will you want to serum and lose two moxen and your speed? If you do, you may end up with the combo the second time (and powder says chances are you'll run into one combo card this time at least) but you have only a land and disruption, no accelleration. You have run into a wall and have to topdeck, or am I missing something?

Maybe I'm thinking of it the wrong way. I would certainly test it in Dragon and Stax anyway.

Peace

[Sylvester]

Fëanor: Yes, this needs to be looked into, but that's much harder to describe and score.

Defector: It's in Common Lisp. CMUCL and SBCL are two good _ native compiling_(it'll be much faster than the bytecode compiling one i'm using) Free (speech) implementations available on linux.

Smash: It's getting late, so I'll just paste the whole file here, and clean up/separate/comment later. You want to look at 'score', which takes a list describing the cards making up the deck (in order) and the current res (result) as arguments, and returns the new res. It's divided in two parts, the one which scores the hand if there was no Powder (simply ignores its presence), and the other with. CardA and CardB represent the two combo pieces, CardC Powder.

Code:

(defun lstdesc2lst (alist)
  "Transform an alist list description to a flat list"
  (mapcan #'(lambda (pair) (make-list (cdr pair) :initial-element (car pair))) alist))

(defun swap (lst a b)
  "Swap a list's a'th and b'th elements *0-indexing* . Rewrite so as not to walk list twice."
  (labels ((fn (lst value rank acc)
	  (if (= 0 rank)
	      (append (nreverse acc) (list value) (cdr lst))
	    (fn (cdr lst) value (1- rank) (push (car lst) acc)))))
	  (let ((valuea (nth a lst))
		(valueb (nth b lst)))
	    (fn (fn lst valueb a nil) valuea b nil))))

(defun shuffle (lst &optional (n 100))
  "Shuffles a list n (default: 100) times by swapping 2 random elements"
  (labels ((fn (lst len n)
	       (if (= 0 n)
		   lst
		 (fn (swap lst (random len) (random len)) len (1- n)))))
    (progn 
;      (format t "shuffle ~D ~A~%" (length lst) (firstn lst 7))
      (fn lst (length lst) n))))

(defun score (lst res &optional (hand-size 7))
  (labels ((with-powder (lst res &optional (hand-size 7))
			(let ((hand (firstn lst hand-size))
			      (rest (nthcdr 4 (firstn lst (+ hand-size 4)))))
;			  (format t "With-Powder Hand: ~A~%Rest: ~A~%" hand rest)
			  (cond ((and (member 'CardA hand) (member 'CardB hand)) 
				 (setq res (upd-or-ins res 'With-Powder))
				 (if (exists hand 'CardC 2)
				     (setq res (upd-or-ins res '2MoreC)))
				 (cond ((and (member 'CardC hand) (member 'CardC
									  rest))
					(upd-or-ins res 'CardCInBoth))
				       ((member 'CardC hand) (upd-or-ins res
									 'CardCInHand))
				       ((member 'CardC rest) (upd-or-ins res
									 'CardCInRest))
				       (T res)))
				((member 'CardC hand) (with-powder (shuffle (nthcdr 7 lst)) res hand-size))
				((< hand-size 6) res)
				(T (with-powder (shuffle lst) res (1-
								   hand-size))))))
	   (no-powder (lst res &optional (hand-size 7))
		      (let ((hand (firstn lst hand-size)))
;			(format t "No-Powder Hand: ~A~%" hand)
			(cond ((and (member 'CardA hand) (member 'CardB hand))
;			       (print "Hit1")
			       (upd-or-ins res 'No-Powder))
			      ((< hand-size 6) 
;				(print "res")
			       res)
			      (T 
;				(print "mulligan")
			       (no-powder (shuffle lst) res (1-
							     hand-size)))))))
    (with-powder lst (no-powder lst res))))

;(setq deck (lstdesc2lst '((a . 1) (b . 19))))

(defun calc (deck n)
  (do ((i 0 (1+ i))
       (res 0 (score (shuffle deck 100) res)))
      ((= n i) res)))

(defun calc2 (deck n &key (score #'score) (shuffle #'shuffle) (init-res nil))
  "score: scoring fxn (score deck res) returns result and deck;
   shuffle: shuffling fxn (shuffle deck) returns a deck;
   init-res: initial result value."
  (let ((res init-res))
    (dotimes (i n res)
      (multiple-value-bind (inner-res inner-deck)
	  (funcall score (funcall shuffle deck) (upd-or-ins res 'Total))
	(setq res inner-res)
	(unless (null inner-deck) (setq deck inner-deck))
	(if (= (mod i 250) 0)
	    (format t "~A~%" res))))))
	    
(defun reload () (load "c:/paul/temp.lisp"))

(defun test () 
  (calc2 deck 1000 :score #'score :shuffle #'(lambda (lst) (shuffle lst 100))
	 :init-res 0))

(defun upd-or-ins (alist key &key (init 1) (fn #'1+))
  "Update or Insert: If key in alist, update its cdr w/ fn, else insert new couple (key . init).
   init is inserted as a value. fn is funcall'ed w/ the current value as argument."
  (let ((cpl (assoc key alist)))
    (if cpl
	(setf (cdr cpl) (funcall fn (cdr cpl)))
      (setq alist (acons key init alist)))
    alist))

(defun deck-wizard ()
  "A Wizard to build deck descriptions"
  (labels ((get-name (lst)
		     (progn (format t "Card Name - end to stop?~%")
			    (get-count lst (read-line))))
	   (get-count (lst name)
		      (if (eq (read-from-string name) 'end)
			  lst
			(progn (format t "How many ~A?~%" name)
			       (get-name (push (cons name (read-from-string
							   (read-line))) lst))))))
    (get-name nil)))

(defun exists (lst symb num)
  "Are there num symb in lst? - Might be interested in count."
  (cond ((= 0 num) T)
	((null lst) nil)
	(T (if (eq (car lst) symb)
	       (exists (cdr lst) symb (decf num))
	     (exists (cdr lst) symb num)))))

#|(defun condition-wizard ()
  "Condition-list: assoc list (condition-name . fxn-name)
   count: how many conditions."
  (labels ((get-condition-name (condition-list count)
			       (progn (format t "Condition Name - end to
stop?~%")
				      (build-conditions condition-list (incf
									count)
							(read-line))
				      ))
	   (build-conditions (condition-list count condition-name)
			     (compile (read-from-string (format nil
								"Condition~D"
								count))
				      `(lambda (&optional lst)
					 ,(get-condition-line
					   condition-list))))
	   (get-condition-line (condition-list)
			       (let ((Operation nil))
			       (progn (format t "And, Or or other?~%")
				      (setq Operation (read-line))
				      (format t "Exists 
|#

(defun firstn (lst n)
  (labels ((fn (lst n acc)
	       (cond ((or (= 0 n) (null lst)) (nreverse acc))
		     (T (fn (cdr lst) (decf n) (push (car lst) acc))))))
    (fn lst n nil)))

Good night

[Sylvester]

I didn't want to start another thread, so i'm posting some new results on number of lands here. My goal was to have 2 or 3 lands out by turn 3, with less than 5 lands after turn 6. I didn't have much time, so these are the results after 1k runs for each number of lands.

Code:

n        2-3      3
15    : 56.5    23.9
16    : 56.4    27.0
17    : 57.1    30.0
18    : 58.3    31.5  <<<
19    : 55.5    32.1  <<<
20    : 52.9    30.9
21    : 50.5    29.1
22    : 46.1    27.1
23    : 43.1    24.6
24    : 40.0    24.5
25    : 40.5    24.6
26    : 33.2    21.3

n: number of lands
2-3: odds (%) of having 2 or 3 lands out by t3 and drawn less than 5 t6
3: odds (%) of having 3 lands out by t3 and drawn less than 5 t6

Mmm.. Around 18-19 lands seem to be the most interesting. I don't know yet how i'll do it with fetchies, but i've an idea. Still, it shouldn't have that much of an impact.

btw, the code for the scoring function:
 

Code:

(defun score (deck res)
  "Score for land distribution"
  (let* ((t0 (firstn deck 7))
	(t1 (firstn deck 8))
	(t2 (firstn deck 9))
	(t3 (firstn deck 10))
	(t4 (firstn deck 11))
	(t5 (firstn deck 12))
	(res (upd-or-ins res (list (count 'carda t0)
					     (count 'carda t1)
					     (count 'carda t2)
					     (count 'carda t3)
					     (count 'carda t4)) :test #'equal)))
    (cond ((and (exists t0 'cardA 1)
		(exists t1 'cardA 2)
		(exists t2 'cardA 3)
		(< (count 'cardA t5) 5))
	   (upd-or-ins res '3in3))
	  ((and (exists t0 'carda 1)
		(exists t1 'carda 2)
		(< (count 'cardA t5) 5))
	   (upd-or-ins res '2in2))
	  ((and (exists t2 'carda 2) 
		(exists t0 'carda 1)
		(< (count 'cardA t5) 5))
	   (upd-or-ins res '2in3))
	  (T res))))

[the Luke]

You used lisp! My hero

Looking at your shuffle algorithm... is it up to scratch? Swapping two cards n times, where n is less than twice the number of cards in the deck seems unsatisfactory.

Why not just do a destructive random selection (without replacement) to build a new list? Then you guarantee randomness (as much as you can with a pseudo-random generator, anyway).

Also of interest... you could actually simulate riffle shuffling without too much trouble. Cut the deck in half (easy with lisp), then select (with 50/50 chance) the next card in the new deck like this (I'm a bit rusty):

Code:

(defun riffle (lst) 
  ;; riffle shuffle a list. Returns the shuffled list 
  (let ((top (butlast lst (floor (/ (length lst) 2))))
	(bottom (nthcdr (ceiling (/ (length lst) 2)) lst))
	retlst) 
    (do () 
	((and (null top) (null bottom)) (nreverse retlst)) 
      (if (flip) 
	  (if top (push (pop top) retlst)) 
	(if bottom (push (pop bottom) retlst))))))

(defun flip ()
;; returns t or nil 50/50.
  (cond ((equals (random 2) 0))))

[33]> (riffle (riffle (riffle '(a b c d e f g h i j k l m n o p))))
(B O N A F G M E J H I L P D K C)
[34]> (riffle (riffle (riffle '(a b c d e f g h i j k l m n o p))))
(K E C O B A N D J H M L G P I F)
[35]> (riffle (riffle (riffle '(a b c d e f g h i j k l m n o p))))
(I F A E M P D H L G O C K J N B)

Just repeat this 3 or so times, and you're done, with a more realistic shuffling mechanism.

Good work!

-Luke

EDIT: Fixed the bugs in my code ^^;;

[Sylvester]

here's how i'd do it

Code:

(defun flip (&optional (n 2))
  (= 0 (random n)))

(defun riffle-shuffle (lst &optional (n 3))
  (labels ((fn (top bottom acc)
	       (cond ((null top) (append bottom acc))
		     ((null bottom) (append top acc))
		     ((flip) (fn (cdr top) bottom (push (car top) acc)))
		     (T (fn top (cdr bottom) (push (car bottom) acc))))))
    (riffle-shuffle (fn (firstn lst (/ (length lst) 2)) (nthcdr (/ (length lst) 2) lst) nil) (1- n))))

Well, that's gonna be my default shuffle routine now... Do you think i should raise the default number of shuffles (currently 3)?

[Smash]

I don't agree with using riffle shuffles. I think you should continue to use fisher-yates shuffle.

Code:

(etypecase vec
    (vector (loop :for ii :downfrom (1- (length vec)) :to 1
                  :for jj = (random (1+ ii))
                  :unless (= jj ii)
                  :do (rotatef (aref vec ii) (aref vec jj)))
            vec)
    (number (vector-shuffle (make-vector-indexed vec)))))

[Sylvester]

Thanks for the routine; it's obviously much better than my original one is Bleh, i think i really have to convert the list to an array (like you do) and back if i want good performances.