Colonial Blotto

;; Everyone's heard of the Prisoner's Dilemma, but I hadn't heard
;; until recently of Colonel Blotto, which was another foundation of
;; Game Theory.

;; Colonel Blotto and his opponent each have 100 troops, and between
;; them are 10 hills.

;; They must allocate troops to the hills, without knowing each
;; other's decisions.

;; On each hill, the larger number of troops wins, and the side which
;; wins the most battles wins overall.

;; Imagine that Blotto sends ten troops to each hill, but his cunning
;; enemy sends 11 troops to nine hills, and sends one poor soldier on
;; a suicide mission to the tenth.

;; Blotto loses 9-1, which is a pearl-handled revolver performance.

;; In the next battle, his successor cunningly sends 12 troops to the
;; first eight hills, four to hill nine, and none to hill 10.

;; The enemy, however, has anticipated this, and sent one man to claim
;; the undefended hill ten, five to the lightly defended hill nine,
;; and thirteen to most of the others. Another stunning victory.

;; Even though it was originally thought of as a simple war game,
;; Blotto is a better model for election campaigning!

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Suppose that a colonial empire (let us without loss of generality
;; call them "The British") is desperately trying to hang on to its
;; last foreign possession against the heroic guerilla tactics of a
;; bunch of terrorists (the "Rebels"). The terrorists are badly
;; outnumbered, but agile.

;; The British are a slow moving bunch, who will divide their large
;; force equally among the strategic targets that they need to
;; protect.

;; The Rebels have, as well as the second mover advantage of getting
;; to see their enemy's troop distribution, the choice of how many
;; fronts to fight on.

;; They win if they manage to win on a majority of fronts.

;; Suppose that the British have four thousand men
(def colonial-troops 4000)
;; And the rebels have 1500 
(def rebel-troops 1500)

;; How many fronts should the rebels choose to fight on?

;; Suppose 7 is the rebel commander's lucky number
(def fronts 7)

;; The British send 571 men to each front
(quot colonial-troops fronts) ;-> 571

;; Which we might choose to represent as:
(repeat fronts (quot colonial-troops fronts))

;; Which leaves them with a reserve of three
(- colonial-troops (* fronts min-colonial)) ;-> 3

;; Which we might choose to represent as: 
(set! *print-length* 25)
(concat (repeat 3 1) (repeat 0))

;; They distribute their reserve also:
(def colonial-dist (map + 
                        (repeat fronts (quot colonial-troops fronts))
                        (concat (repeat 3 1) (repeat 0))))

;; To leave a final distribution:
colonial-dist ;-> (572 572 572 571 571 571 571)

(assert (= (reduce + colonial-dist) colonial-troops) "grr")

;; We can summarize this in the following function:
(defn colonial-troop-allocation[troops fronts]
  (let [min-colonial (quot troops fronts)
        excess (- troops (* min-colonial fronts))
        excess-dist (concat (repeat excess 1) (repeat 0))
        min-dist (repeat fronts min-colonial)
        colonial-dist (map + min-dist excess-dist)]
    (assert (= (reduce + colonial-dist) troops) "grr")
    colonial-dist))

(colonial-troop-allocation 120 1) ;-> (120)
(colonial-troop-allocation 120 2) ;-> (60 60)
(colonial-troop-allocation 120 3) ;-> (40 40 40)

(colonial-troop-allocation 225 3) ;-> (75 75 75)
(colonial-troop-allocation 225 5) ;-> (45 45 45 45 45)
(colonial-troop-allocation 225 7) ;-> (33 32 32 32 32 32 32)
(colonial-troop-allocation 225 8) ;-> (29 28 28 28 28 28 28 28)

(colonial-troop-allocation 7 8) ;-> (1 1 1 1 1 1 1 0)

;; Now the rebels have an easier task. They know how many fronts they
;; have to win on, and they only have to win by one soldier on each
;; front, so they can work out a winning allocation so:

(defn rebels-allocation [colonial-allocation]
  (let [majority (inc (quot (count colonial-allocation) 2))]
    (map inc (take majority (sort colonial-allocation)))))
        
    
(defn rebels-needed-for-rebellion [colonial-troops fronts]
  (let [ca (colonial-troop-allocation colonial-troops fronts)
        rn (rebels-allocation ca)]
    (reduce + rn)))

(map (partial rebels-needed-for-rebellion colonial-troops) (iterate inc 1)) 
;-> (4001 4002 2668 3003 2403 2670 2288 2505 2225 2406 2186 2338 2159 2292 2139 2259 2124 2230 2111 2211 2101 2192 2098 2176 2093 ...)

;; To win on one front, they need 4001 brave comrades. 
;; To win on two, they need 4002 (one win and one draw doesn't quite cut it).  
;; To win on three, they only need 2668.
;; As the number of fronts goes up, the number appears to be settling down 
;; to around 2000, which is a nice result.

;; "A perfectly informed flexible force fighting an enemy with a
;; uniform order-of-battle needs more than half as many troops to win"

;; How would you advise the rebel commander?

;; What advice would you give the Brits?