;;; -*- mode: lisp; syntax: common-lisp -*-

(defmemo decide-tosses-1 (k1 k2)
  (iter (for a1 from 1 to (1+ (ceiling (log k1 2))))
        (finding a1 minimizing
                 (iter (for a2 from 1 to (1+ (ceiling (log k2 2))))
                       (maximizing (+ (* (expt 2 (- a1))
                                         (player2 (- k1 (expt 2 (1- a1))) k2))
                                      (* (- 1 (expt 2 (- a1)))
                                         (player1-helper k1 k2 a1 a2))))))))

(defmemo decide-tosses-2 (k1 k2)
  (iter (for a2 from 1 to (1+ (ceiling (log k2 2))))
        (finding a2 maximizing
                 (iter (for a1 from 1 to (1+ (ceiling (log k1 2))))
                       (minimizing (+ (* (expt 2 (- a2))
                                         (player1 k1 (- k2 (expt 2 (1- a2)))))
                                      (* (- 1 (expt 2 (- a2)))
                                         (player1-helper k1 k2 a1 a2))))))))

(defun player1-helper (k1 k2 a1 a2)
  (/ (+ (* (expt 2 (- a1)) (player2 (- k1 (expt 2 (1- a1))) k2))
        (* (- 1 (expt 2 (- a1))) (expt 2 (- a2))
           (player1 k1 (- k2 (expt 2 (1- a2))))))
     (- 1 (* (- 1 (expt 2 (- a1))) (- 1 (expt 2 (- a2)))))))

(defmemo player1 (k1 k2)
  (if (<= k2 0)
      1.0d0
      (player1-helper k1 k2 (decide-tosses-1 k1 k2) (decide-tosses-2 k1 k2))))

(defun player2-helper (k1 k2 a1 a2)
  (/ (+ (* (expt 2 (- a2)) (player1 k1 (- k2 (expt 2 (1- a2)))))
        (* (- 1 (expt 2 (- a2))) (expt 2 (- a1))
           (player2 (- k1 (expt 2 (1- a1))) k2)))
     (- 1 (* (- 1 (expt 2 (- a2))) (- 1 (expt 2 (- a1)))))))

(defmemo player2 (k1 k2)
  (if (<= k1 0)
      0.0d0
      (player2-helper k1 k2 (decide-tosses-1 k1 k2) (decide-tosses-2 k1 k2))))

;;; The probability that the not-starting player wins when the goal is 100,
;;; and both players can decide how many times they want to toss the coin.
;;; (format nil "~,8f" (player1 100 100))

(defun test (n &optional (max 100))
  (/ (iter (repeat n)
           (count
            (iter (for k1 = (decide-tosses-1 (- max player1) (- max player2)))
                  (sum (if (zerop (random (expt 2 k1))) (expt 2 (1- k1)) 0)
                       into player1)
                  (while (< player1 max))
                  (for k2 = (decide-tosses-2 (- max player1) (- max player2)))
                  (sum (if (zerop (random (expt 2 k2))) (expt 2 (1- k2)) 0)
                       into player2)
                  (while (< player2 max))
                  (finally (return (< player1 max))))))
   n))

;;; (format nil "~,8f" (test 10000))

(defun show-an-optimal-game (&optional (max 100))
  (format t "~3d     ~3d    ~%" 0 0)
  (iter (for k1 = (decide-tosses-1 (- max player1) (- max player2)))
        (sum (if (zerop (random (expt 2 k1))) (expt 2 (1- k1)) 0)
             into player1)
        (while (< player1 max))
        (for k2 = (decide-tosses-2 (- max player1) (- max player2)))
        (sum (if (zerop (random (expt 2 k2))) (expt 2 (1- k2)) 0)
             into player2)
        (while (< player2 max))
        (format t "~3d (~d) ~3d (~d)~%" player1 k1 player2 k2)
        (finally (format t "~3d (~d) ~3d (~d)~%" player1 k1 player2 k2))))