#Note by Dr. Z.: today the projector was down, so students #did it their own way. Below is the beautiful Maple code #of Phil Benjmain. # Experimental Math Rocks! # Class 9, Feb 21 # Phil Benjamin (free to post, post for free!) # "Bacterial" Backgammon # Two squares on board 1,2 # Position: a,b # of counters on each square (zero or more) # Roll die: 1 or 2 # Legal move: # Bearoff (google this!) # Input [a,b],i # i=1 --> [a,b] -> [a-1,b+1] or [a,b-1] (if possible) # i=2 --> [a,b] -> [a-1,b] or [0,b-1] otherwise (must do in order) # Win if [0,0] Help := proc() print(`LegalMoves(a,b,i) f(a,b,i) F(a,b) fw(a,b,i)`); end: #LegalMoves(a,b,i): inputs non-negative integers a and b and #an integer i in {1,2} and outputs the set of all legal #positions reachable in one move in a bearoff mini Backgammon #where the square distance 2 units away has a counters #and the the square distance 1 units away has b counters #and the 2-faced die landed on i LegalMoves := proc(a,b,i) local S; S := {}; if a=0 and b=0 then return S; end; if i=1 then if a >= 1 then S := S union {[a-1,b+1]}; end; if b >= 1 then S := S union {[a,b-1]}; end; return S; end; if i=2 then if a >= 1 then S := S union {[a-1,b]}; return S; end; if b >= 1 then S := S union {[0,b-1]}; return S; end; return S; end; return FAIL; end: # Objective is to arrive at [0,0] # Want to get minimal expected time # Output is [[a1,b1],t] # note: t is real # Technique is "dynamic programming" # Let f(a,b|i) = # 1 + min{F(a1,b1): legal moves from a,b} # F(a,b) = 1/2*f(a,b|1) _ 1/2*f(a,b|2) # Helper functions for BestMove # should get [3/2, 23/8, 135/32, 711/128, ...] f := proc(a,b,i) option remember; local M,SM; SM := LegalMoves(a,b,i); if SM={} then return 0; end; return 1 + min({seq(F(M[1],M[2]),M in SM)}); end: F := proc(a,b) option remember; if a=0 and b=0 then return 0; end; return (1/2)*f(a,b,1) + (1/2)*f(a,b,2); end: #BestMove(a,b,i): inputs non-negative integers a and b # and an integer i in {1,2} and outputs the pair [duration, BestMove] BestMove := proc(a,b,i) option remember; end: fw := proc(a,b,i) option remember; local M, SM, rec, t, champ; SM := LegalMoves(a,b,i); if SM={} then return [0,[]]; end; champ := SM[1]; rec := F(champ[1],champ[2]); for M in (SM minus {champ}) do t := F(M[1],M[2]); if t < rec then champ := M; rec := t; end; end; return [rec,champ]; end: # Possible projects: # Conway style games, continued, e.g. simplification # Can work in teams of 2 # Games with chance, how to play Backgammon (e.g.) # Gambling type of games # Wythoff game with two piles, what is Sprague-Grundy function for all positions # Q: analyze games in "Winning Ways" ... # Probability in Conway Games # Grundy functions with probability # Prisoner's dilemma # Game theory: negotiating, bluffing # Starting games with chance # Backgammon, history, rules, etc. # "house",