Imagine you have a few piles of sticks. Two players take turns picking sticks. On your turn, you must choose one pile and take at least one stick from that pile (you can take as many as you want from that pile, even all of them). The person who takes the very last stick wins!

The Board

Pile 0: ||||

Pile 1: ||

Pile 2: |||||

Pile 3: |

Pile 4: ||||||

...or more concisely: [4,2,5,1,6]

The Task

You have to encode in a function choose_move (or chooseMove, or choose-move) that takes a board, represented as a list of positive integers, and returns

(pile_index, number_of_straws)

Which refers to an index of a pile on the board, and some none-zero number of straws to draw from that pile.
The test suite is written so that your AI is expected to play 50 games and win every game it plays.

def basic_tests():
        test.assert_equals(choose_move([0,5,0,0]), (1, 5))
        test.assert_equals(choose_move([0,3,5]), (2, 2))
        test.assert_equals(choose_move([3,3,6]), (2, 6))

Solution

Python

def choose_move(game_state):
    """Chooses a move to play given a game state"""   
    # Calculate the XOR sum of all piles
    xor_sum = 0
    for pile in game_state:
        xor_sum ^= pile

    # If the XOR sum is 0, any move will lead to a loss (unless the game is already over).
    # To handle this, make a legal move (e.g., take 1 straw from the first non-empty pile).
    if xor_sum == 0:
        for i, pile in enumerate(game_state):
            if pile > 0:
                return i, 1
        # If all piles are empty, it means the game is over.  Return any valid move.
        return 0, 0 # This should not happen in a correctly implemented game.

    # Find a pile to modify to make the XOR sum 0
    for i, pile in enumerate(game_state):
        new_pile = pile ^ xor_sum
        if new_pile < pile:  # Ensure we're removing straws, not adding
            return i, pile - new_pile

    # This should never be reached if XOR sum is not 0 and a valid move exists.
    return 0, 0  # To avoid errors.  This should be improved in a real game.

Explanation

In the video, the last stick is picked by the loser. In our version, it is the winner. No worries, we can account for that.

XOR explanation

Imagine you have a light switch. It can be either ON (1) or OFF (0).

XOR is like a special rule for combining two light switches:

• If both switches are the SAME (both ON or both OFF), the result is OFF (0).
• If the switches are DIFFERENT (one ON and one OFF), the result is ON (1).

Think of it this way: XOR means “eXclusive OR”. It’s ON if either switch is ON, but not if both are ON.

Why is this useful?

XOR is really good at finding differences. If you XOR two numbers, the result will have ‘1’ bits in the places where the original numbers were different.

In the game of Nim, XOR helps us figure out the best move because it tells us how to “balance” the piles of stones. By keeping the XOR sum of the piles at 0, you can force your opponent into a losing position.

---

If you liked this article I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"