I have recently been reading the book Game Theory and Strategy by Phillip Straffin. It was suggested to me by my mathematics teacher Patroklos Benatos. He suggested I read this book for an introduction to the study of Game Theory. It has been excellent reading and inspired me to develop an application that aids one in finding a solution to a zero sum game matrix. So lets take a look at the code. The constructor of the application sets up some TextFields that will be used throughout the calculation of the matrix game solution. These text fields will be filled with the cells of the matrix that hold the largest column entry, the smallest row entry, and any saddle points present in the matrix. A for() loop ( Line 45 ) is used to generate random entries in the cells of the matrix such that -10< n < 10 where n is the payoff of that cell. I chose a 4x4 matrix for the size of this matrix. I am planning to allow the user to alter the mxn dimensions in a future iteration of this application, but for now the size of the generated matrix is static. After generating the payoffs for the 16 cells of the matrix at random the code runs the function checkForSaddlePoints().
The first thing performed in the execution of checkForSaddlePoints() is the TextFields ( Line 99 ) that identify the Greatest Column Payoffs , the Least Row Payoffs, and the Saddle Points are restored to their original forms. At this point the TextFields do not identify any entries in the matrix. As the loops and calculations ahead in the code execute. The for() loop ( line 110 ) begins by extracting each key from the Dictionary object.
Each key object is a TextField which was stored in the Dictionary ( line 65 ). The object at d[ key ] stores the column and row index for this TextField. Now that the code has identified one TextField, its column index, and its row index, its time to start storing and the largest column and least row entries in the matrix. The aColumn array is used to keep track of which columns have been already checked for their largest entries. The aRow Array is used to keep track of which rows have been already checked for their least entries. If for example a certain column has not been checked for its largest entry the code inside the if( aColumn[c] != true ) will execute ( line 120 ), in turn running the method findGreatestEntryInColumn() which evaluates every entry in this particular column c. After identifying this entry in said column, it will be differentiated by coloring its text red. Its entry information will also be stored on greatestColumns Array for later use when checking for the existence of saddle points. The evaluation of if( aRow[r] != true ) works in exactly the same way ( line 132 ). After this evaluation is complete, the code can then determine if a saddle point is present in the matrix by checking if any of the Greatest Column entries coincide the with Least Row entries. ( line 150 ).
And here is the code that make this whole thing work ::
/** * This class is the controlling entity of Game Theory Matrix Solver * * Copyright (c) 2008 Gregory Sogorka. */ package { import flash.display.Sprite; import flash.events.Event; import flash.text.TextField; import flash.text.TextFieldType; import flash.utils.Dictionary; public class Gametheory_Experiment extends Sprite { private var d : Dictionary; private var columnAlert : TextField; private var rowAlert : TextField; private var saddlePointAlert : TextField; private var totalColumns : int; private var totalRows : int; private var xPos : int = 100; public function Gametheory_Experiment() { d = new Dictionary(); columnAlert = new TextField(); columnAlert.x = xPos; columnAlert.y = 20; columnAlert.width = 350; addChild( columnAlert ); rowAlert = new TextField(); rowAlert.x = xPos; rowAlert.y = 40; rowAlert.width = 350; addChild( rowAlert ); saddlePointAlert = new TextField(); saddlePointAlert.x = xPos; saddlePointAlert.y = 60; saddlePointAlert.width = 350; addChild( saddlePointAlert ); for( var i : int = 0; i<4; i++ ){ for( var j : int = 0; j<4; j++ ){ var t : TextField = new TextField(); var num : Number = Math.floor( Math.random() * 10 ); t.text = ( Math.random() > .5 )?String(num):String(-1*num); t.border = true; t.borderColor = 0x00000000; addChild( t ); t.x = j*20.5; t.y = i*20.5; t.width = 20; t.height = 20; t.type = TextFieldType.INPUT; t.addEventListener( Event.CHANGE, textChange ); d[t]= { row : i, column : j }; } } totalColumns = j; totalRows = i; checkForSaddlePoints(); } private function textChange( e : Event ) : void { checkForSaddlePoints(); } private function getAllValuesInColumn( i : int ) : Array { var a : Array= new Array(); for( var key : Object in d ) { if( d[key]["column"] == i ) a.push( { column : d[key]["column"], row : d[key]["row"], value : TextField( key ).text } ); } return a; } private function checkForSaddlePoints() : void { columnAlert.htmlText = "<font size='8' color='#ff0000'>Greatest Column Entry</font> at : "; rowAlert.htmlText = "<font size='8' color='#0000ff'>Least Row Entry</font> at : "; saddlePointAlert.htmlText = "<font size='8' color='#A2627A'>Saddle Points</font> at : "; resetTextFieldColors(); var aColumn : Array = new Array(); var aRow : Array = new Array(); var greatestColumns : Array = new Array(); var lowestRows : Array = new Array(); for( var key : Object in d ) { //key is a textfield; //c is TextField( key ) column index; //r is TextField( key ) row index; var c : Number = d[key]["column"]; var r : Number = d[key]["row"]; var t : TextField = TextField( key ); //If we've not encountered this column before lets decide what its greatest entry is an object holding that info to o if( aColumn[c] != true ) { var o : Object = findGreatestEntryInColumn( c, t ); //Change the color of the largest column entry getTextFieldByCoordinate( o["row"], o["column"] ).textColor = 0xffff0000; columnAlert.htmlText += "<font size='8'> ["+o["row"]+" , "+o["column"] +"] </font>" //So further interations of our for() loop don't reevaluate this column aColumn[c] = true; greatestColumns.push( o ); } //If we've not encountered this row before lets decide what its least entry is an object holding that info to or if( aRow[r] != true ) { var or : Object = findLowestEntryInRow( r, t ); //Change the color of the lowest row entry cell. getTextFieldByCoordinate( or["row"], or["column"] ).textColor = 0xff0000ff; rowAlert.htmlText += "<font size='8'> ["+or["row"]+" , "+or["column"] +"] </font>"; aRow[r] = true; lowestRows.push( or ); } } // Basically the dimensions of our MxN matrix var cLength : int = greatestColumns.length; var rLength : int = lowestRows.length; for( var i : Number =0;i< cLength; i++ ){ var oCol : Object = greatestColumns[i]; for( var j : Number=0; j< lowestRows.length; j++ ) { var oRow : Object = lowestRows[j]; //Check if the greatest column entry is the same as any of the least row entries if( oCol["row"] == oRow["row"] && oCol["column"] == oRow["column"] ) { // saddlePointAlert.htmlText += "<font size='8'> ["+oCol["row"]+" , "+oCol["column"]+"] </font>"; //Change the color of the saddle point cell to purple getTextFieldByCoordinate( oCol["row"],oCol["column"]).textColor= 0xffA2627A; } } } } private function findLowestEntryInRow( row : Number, changed : TextField ) : Object { var o : Object = { column : d[changed]["column"], row : d[changed]["row"] }; var least : Number= Number( changed.text ); for( var key : Object in d ) { if( d[key]["row"] == row ) { var t : TextField = TextField( key ); var n : Number = Number( t.text ); if( n < least ){ least = n; o= { row : d[key]["row"], column : d[key]["column"] }; } } } return o; } private function findGreatestEntryInColumn( col : Number, changed : TextField ) : Object { var o : Object = { column : d[changed]["column"], row : d[changed]["row"] }; var greatest : Number = Number( changed.text ); for( var key : Object in d ) { if( d[key]["column"] == col ) { var t : TextField = TextField( key ); var n : Number = Number( t.text ); if( n > greatest ){ greatest = n; o = { column : d[key]["column"], row : d[key]["row"] }; } } } return o; } private function getTextFieldByCoordinate( row : int, column : int ) : TextField { var t : TextField; for( var key : Object in d ) { if( d[key]["column"] == column && d[key]["row"] == row ) t= TextField( key ); } return t; } private function resetTextFieldColors() : void { for( var key : Object in d ) { TextField( key ).textColor =0; } } } }
Here is a link to the source code. Feel free to send me any comments, suggestions, or optimizations for this code. Source