The Money-Withdrawl Game
Two players alternately draw money from an ATM, but each time
only one coin or one bill. The player who draws the last coin
or bill from the machine wins the game.
Concerning the 1 Cent coints, they still exist, although only
Singpost seems to use them and most other stores just round them
away. See also
the
Wikipedia Page on Singapore dollars
for a list of coins and bills.
The Implementation
The game is implemented in four levels: completely random, easy, medium
and good. The last three variants have two versions, at one version the
player chooses randomly between equally good evaluated moves and in the
other version, it chooses the one with the largest win at the moment
among equally good evaluated moves. The medium player uses
precomputed data in table but relies on some estimations for
those inputs which fall outside the array "mediumdata".
The precomputed data is a table which player wins at which
starting number when playing optimally. The good player should
use an algorithm, called "goodvalue", instead of "mediumdata"
for its purposes. This algorithm should cover all possible inputs.
What has to be done
As said, the strategy data of the good player depends on a function
goodvalue(mn). It follows an easy principle which permits to
compute for all inputs mn a value which would correspond to
mediumdata[mn] provided that the value is defined. So goodvalue(mn)
should be a generalization of mediumdata[mn] beyond the boundaries
of that array. The
the field mediumdata is not large enough and so one needs some
idea how to do is. This could be best found by expecting the
values of the field mediumdata and to search for a law which
holds for the values of this field. Then one can compute goodvalue(mn)
by only inspecting a small part of these values.
Actually, it was orginally planned to go for a more complicated algorithm,
but one student from the Semester 2 in 2006 (AY 2005-2006) found the
above mentioned easy solution.
An assessment of the modified function goodvalue
can be made by calling the automatic test-routing with the
button "Compare data for medium and good player" which checks whether those
of the entries of the good player which also exist for the medium player
are correct. A further evidence on the correctness of the implementation
can be obtained by playing tournaments.
-
When playing the "Fixed Tournament",
the output should contain the following line:
Player Good and Greedy versus Player Good and Greedy is 381454:82981 and 24:16.
You can put players X and Y onto this option and play this tournament only
to check.
- Furthermore, at random tournaments, the good player should clearly
outperform the medium player in terms of number of won games. Somehow the
performance with respect to winning as much money as possible goes down,
as the medium greedy player defeats some of the random players with strategies
which risk a loss but the random players do not realize this weakness.
The following would be a typical table.
Overview of player performance.
Player Random won 248866 Dollar 13 Cent in 51 games.
Player Easy and Greedy won 631709 Dollar 71 Cent in 82 games.
Player Easy and Random won 182276 Dollar 57 Cent in 52 games.
Player Medium and Greedy won 1320537 Dollar 57 Cent in 160 games.
Player Medium and Random won 617342 Dollar 69 Cent in 163 games.
Player Good and Greedy won 1793962 Dollar 92 Cent in 240 games.
Player Good and Random won 1303435 Dollar 51 Cent in 232 games.