next up previous contents
Next: 5.3 Hand Potential Up: 5.2 Hand Strength Previous: 5.2 Hand Strength   Contents

5.2.1 Multi-Player Considerations

The above description of the weighted enumeration system for hand strength is intended for one opponent. When the system was first put to use, the weight array was common to all opponents (either uniform or some fixed `typical' distribution) so HSn was easily extrapolated by using Equation 5.3. However, our opponent modeling system will be computing a different set of weights for each specific opponent.

The correct approach would be to treat each possible case independently. For example, one possible case is that player 1 holds A$\heartsuit $-Q$\diamondsuit $ and player 2 holds Q$\heartsuit $-J$\clubsuit $. To handle this distinction, the function would need an extra iteration layer for each opponent (and would still be dependent on the order of the iteration). For each possible case it would then use a weight w[x] = w1[x1] * w2[x2] * ... * wn[xn] (where x is the complex subcase, xi is the subcase for the cards held by player i and wi[xi] is the weight of that subcase for player i). The weight of the complex subcase given in the example is w[A$\heartsuit $-Q$\diamondsuit $-Q$\heartsuit $-J$\clubsuit $] = w1[A$\heartsuit $-Q$\diamondsuit $] * w2[Q$\heartsuit $-J$\clubsuit $]. The increase in computational complexity is substantial (approximately a factor of 1,000 for each additional player) and becomes infeasible with only 3 opponents.

There are two simpler methods to approach this problem and obtain good estimates of HSn. The first calculates HSpi for all opponents pi (such that i = 1..n) given each respective weight array. It then uses the equation

HSn = HSp1 * HSp2 * ... * HSpn. (5.4)

The second method calculates HS1 using a special weight array, called the field array, computed by combining the weight arrays of all active players. HSn is then calculated with Equation 5.3. The use of the field array as an estimate is a compromise between computational cost and accuracy. It represents the entire table by giving the average weights of the opponents. The process of obtaining hand weights and generating this array is described in Chapter 7.

Both of these methods are only estimates because they ignore the interdependencies arising from the fact that two players cannot hold the same card. Several situations were examined from data gathered during play against human opponents. For both methods, the absolute error was measured with respect to the correct full enumeration but only against two or three active opponents (four opponents was too expensive to compute). For the first method (Equation 5.4), this testing revealed the error never exceeded 2.19%. The average error was 0.307% with two opponents and 0.502% with three opponents. For the second method (using the field array and Equation 5.3), the error never exceeded 5.79% for two opponents and 4.15% for three opponents. In fact, for two opponents only 59 out of 888 cases had an error larger than 2% (and 20 out of 390 three opponent cases). The average errors were 0.671% and 0.751%. The estimated values were usually slight overestimates.

This isolated test scenario suggests that the first method is better but the difference is small. The error also appears to get slightly worse with additional opponents. Loki uses the second method due to the faster computation and ease of introduction into the present framework (particularly with respect to multi-player considerations for hand potential, as will be discussed later). We have not invested the time to further explore the error arising from these interdependencies, however we believe it is minor in comparison to the extra work that would be required for a very accurate measure of HSn. Also, this amount of error is considered to be negligible given that the error introduced by other components of the system tends to be greater in magnitude.

next up previous contents
Next: 5.3 Hand Potential Up: 5.2 Hand Strength Previous: 5.2 Hand Strength   Contents
Denis Papp