Homework 14. Sink the Domino.
Pledged. No prelab, No first draft, No consulation with anyone other than the two instructors.
Final Draft due 5pm Monday, December 3

On our M-by-N game board the row player lays a domino across two squares. The column player chooses one of the squares. If the domino overlaps the selected square then the column player wins, else the row player wins. Let us code, play, and analyze this game. For the 2-by-3 board below the row player has the 7 indicated pure strategies while the column player has the 6 indicated pure strategies.

The associated game matrix is 

     -1 -1  1  1  1  1
      1 -1 -1  1  1  1
      1  1  1 -1 -1  1
      1  1  1  1 -1 -1
     -1  1  1 -1  1  1
      1 -1  1  1 -1  1
      1  1 -1  1  1 -1
Your first task is to write the 

    function G = Gmat(M,N)

that builds the game matrix for an M-by-N domino board. Your G will be (2MN-M-N)-by-(MN) and (if you follow the ordering suggested above) has very simple structure. For example, if M=4 and N=7 then the interesting values in G appear like those at right.

Your next task is to evaluate and visualize optimal column and row strategies. Evaluation requires setting up and solving two linear programs, as we did in the RSP and Morra examples. If you compare these codes you will notice that we varied the options to linprog. In order to get the figures below I recommend that you NOT set any options. That is, follow the RSP example.

The visualization of the optimal strategies should be facilitated by patch and resemble this 3x7 board and this 7x7 board. Your master program should, in addition to finding and plotting the optimal strategies, return the associated row player (domino) payoff. If your master function is called 

    function pay = dom(M,N)

then we may begin to investigate the fairness of various boards. For example, the domino has no place to hide on the smallest boards, dom(1,2)=dom(1,3)=-1 while the 1-by-4 board is fair, i.e., dom(1,4)=0. For larger boards the domino player soon has the advantage. In order to quantify this you will

Graph N vs. dom(1,N) and note that dom(1,2q)=dom(1,2q+1)=1-2/q.

Graph N vs. dom(2,N) and note that dom(2,N)=1-2/N.

Graph N vs. dom(4,N) and note that dom(4,N)=1-1/N.

Graph N vs. dom(6,N) and find the value of c for which dom(6,N)=1-c/N.

Your work will be graded as follows 


   Final Draft, 110 points total

     8 pts for headers CONTAINING detailed USAGE
     8 pts for further comments in code 
     4 pts for indentation
     10 pts for correct Gmat function
     10 pts for correct dom function

     8 pts for jpeg spy plot of -1 structure for G on 3-by-5 board

     14 pts for jpeg of optimal strategies for 4-by-4 board (must use subplot and colorbar)
            and diary with numerical values for optimal strategies

     14 pts for jpeg of optimal strategies for 5-by-7 board (must use subplot and colorbar)
            and diary with numerical values for optimal strategies

     8 pts for jpeg of N vs. dom(1,N) with comparison of dom(1,2q) to 1-2/q

     8 pts for jpeg of N vs. dom(2,N) with comparison to 1-2/N

     8 pts for jpeg of N vs. dom(4,N) with comparison to 1-1/N

     10 pts for jpeg of N vs. dom(6,N) with comparison to 1-c/N. What is c?

     On these last 4 plots run N until at least 20 and be sure to carefully 
     label the axes and use legend and different line and/or marker types to 
     distinguish the results of dom from the algebraic formulas.