calculations

The Nim Game calculation functions

This module defines the functions that are needed to calculate moves and decisions in a Mixin for the Nim class.

class calculations.Mixin

Class to implement the Nim game calculations

This Mixin is used as an ancestor class for Nim, so that we can define methods here, in a separate module.

The term “nimsum” (Grundy value or nim-value), used here, is the Nimber that the game is equivalent to. This number represents the current state of the game.

The importance of nimsum is whether it is zero or not. If nimsum is not zero, it can be changed to zero by the right move of the next player. If the nimsum is zero, the next move will change it to non-zero, whatever the move is. This way, the player who moves in a way to create zero nimsum is the one who drives the game and can win it.

In case of “misère” type of game, there is a point in the course of the game where the strategy must reverse, because we want to opponent to take the last coin. This point is the beginning of the “end-game”. In the end-game, all moves alternate the nimsum between 0 and 1. The winning player changes the nimsum to 1 and the losing player has no other choise but changing it to zero and ultimately taking the last coin.

all_one_heaps() → bool

Checks whether all non-zero heaps have 1 single coin

It uses the functools.reduce() on the heaps list, with a True initializing value and keep it true as long as the number of coins is at most one.

Returns

Whether all relevant heaps have 1 single coin

figure_out_best_move() → Move

Figure out what to move so that we get into a winning position

First handle the situation when all heaps only have 1 coin. If so, there is nothing to think about, just take that 1 coin from a heap randomly.

Then check whether there is only 1 heap with more than 1 coins. This is the indicator for the end-game reversal in the “misère” type. The winning strategy here is to leave odd numbers of 1-coin heaps for the opponent. So, if the number of heaps with 1 coin is odd, take all coins from the heap that has more than 1 coin. If it is even, take all but 1 coin. Either way, this makes sure that odd number of 1-coin heaps are left for the opponent.

Otherwise, we are in the middle of the game, so figure out the all-heap nimsum. If it is zero, the player in this current turn is in a losing position, because whatever we do we create a non-zero nimsum that the opponent can change to zero nimsum again in its turn. So, having no better option, we just take a random number of coins from a random heap and hope that the opponent makes a mistake.

If nimsum is not zero, it can be made zero by removing a cretain number of coins from the right heap. Check each heap and calculate the “target” number of coins, to null the nimsum. E.g. if the nimsum is 7 (binary 111), we need to remove all 3 binary digits, i.e. the 4, 2 and 1, without changing any other binary digits, e.g. the 8. If a given heap contains e.g. 9 coins (binary 1001), the “target” would be the 7 \(\oplus\) 9:

1001
0111
----
1110 => decimal 14

As we cannot remove 14 coins from a heap where there are 9 coins, this is not a suitable heap to remove coins from. So, go on until finding a suitable heap. Theoretically, there must be at least 1 suitable heap.

Returns

From which heap and how many coins are to be removed in the coming move

get_nimsum() → int

Calcualte the nimsum of the set of heaps

It uses the functools.reduce() on the heaps list, with a 0 initializing value and uses XOR for the coin counts of the heaps.

Returns

The nimsum of the heap-set

get_random_move() → Move

Figure out a random but valid move

This method is used when the algorithm does not care what to move. Just figure out a random but valid move.

Returns

From which heap and how many coins are to be removed in the coming move

is_winning_for_next() → bool

Is the current status good for the player having the next turn?

Usually non-zero nimsum is the winning status, so that the player can change it to zero nimsum. This way this player can force the other player to make non-winning move, i.e. creating non-zero nimsum, which this player can change to zero nimsum again, end so on.

However, in “misère” type game, the strategy changes in the end-game moves. When all heaps only have 1 coin left, the winning status is when nimsum is zero. I.e. the all-heaps-has-one-coin reverses the bool nimsum. The boolean reversal is done with an XOR.

Returns

Whether the current status is good for the player having the next turn

make_good_choice() → bool

Figures out whether to make a good decision or make an error

The required error rate indicates how bad decisions the Computer is to make. The higher the error rate percentage the higher the possibility that the Computer makes a bad move/decision. If error_rate is 0, this function always returns True, i.e. the Computer always makes a good decision. If error_rate is 100, the Computer always makes a bad decision.

Returns

False forces to make the bad choise