ISSN:
1572-9338
Keywords:
Minimax
;
games
;
strategy
;
matrix
;
chess
;
algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract Computer game-playing programs repeatedly calculate minimax elements μ = min i max j M ij of large pay off matricesM ij . A straightforwardrow-by-row calculation of μ scans rows ofM ij one at a time, skipping to a new row whenever an element is encountered that exceeds a current minimax. Anoptimal calculation, derived here, scans the matrix more erratically but finds μ after testing the fewest possible matrix elements. Minimizing the number of elements tested is reasonable when elements must be computed as needed by evaluating future game positions. This paper obtains the expected number of tests required when the elements are independent, identically distributed, random variables. For matrices 50 by 50 or smaller, the expected number of tests required by the row-by-row calculation can be at most 42% greater than the number for the optimal calculation. When the numbersR, C of rows and columns are very large, both calculations require an expected number of tests nearRC/InR.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02022038
Permalink
