Posted By

iloveitaly on 12/02/10


Tagged


Versions (?)

Basic Implementation of Game Theory's Minimax


 / Published in: JavaScript
 

  1. // pure strategy: [[2,4],[6,5]]
  2. // mixed strategy: [[3,1],[2,4]]
  3.  
  4. var gameMatrix = [[2,4],[6,5]];
  5. var rowCount = gameMatrix.length;
  6. var columnCount = gameMatrix[0].length;
  7.  
  8. // an accuracy measure; anymore than 1000 will crash modern browsers
  9. var steps = 1000;
  10.  
  11. // mutual payoff function
  12.  
  13. function M(u, s) {
  14. var expectedPayoff = 0;
  15.  
  16. for(var i = 0; i < rowCount; i++) {
  17. for(var j = 0; j < columnCount; j++) {
  18. expectedPayoff += u[i] * s[j] * gameMatrix[i][j];
  19. }
  20. }
  21.  
  22. return expectedPayoff
  23. }
  24.  
  25. var insideMin = 100000, outsideMax = -100000;
  26. var nashEquilibrium = [[], []];
  27.  
  28. // minimax implementation (i.e. finding security value)
  29.  
  30. for(x = 0; x < steps + 1; x++) {
  31. for(y = 0; y < steps; y++) {
  32. var prevMin = insideMin;
  33. var payoff = M([x/steps, 1-x/steps], [y/steps, 1-y/steps])
  34. insideMin = Math.min(insideMin, payoff);
  35.  
  36. // this is for recording the nash equilibrium value
  37. // a new local min != a global maximum; must check both
  38. if(prevMin != insideMin && outsideMax != Math.max(insideMin, outsideMax)) {
  39. nashEquilibrium[1] = [y/steps, 1-y/steps];
  40. }
  41. }
  42.  
  43. var prevMax = outsideMax;
  44. outsideMax = Math.max(insideMin, outsideMax);
  45.  
  46. if(prevMax != outsideMax || outsideMax == insideMin) {
  47. nashEquilibrium[0] = [x/steps, 1-x/steps];
  48. }
  49.  
  50. // reset the local minimum
  51. insideMin = 100000;
  52. }
  53.  
  54. document.write('minimax: ' + outsideMax + "<br/>" +
  55. 'nash eq: ((' +
  56. nashEquilibrium[0][0] + ", " + nashEquilibrium[0][1] + "), (" +
  57. nashEquilibrium[1][0] + ", " + nashEquilibrium[1][1] + "))"
  58. );

Report this snippet  

You need to login to post a comment.