Probability tree for a game

Python Help
1

Hi !
For my studies, I have to create a python program and I decided to create a game.
The game comes from a french TV show, 2 players have 16 wooden stick in front of them and the goal of the game is to not be the player who takes the last wooden stick.
In each turn, one player can choose to take 1,2 or 3 sticks, the other one chooses as well and the game continues until one stick remains.
We’d like to make the computer play with someone.

We started but we have a problem : we don’t know how to create an algorithm in which the computer chooses how many sticks it takes, considering the next move of the other player, to win. We know we have to create a probability tree to see what are the best moves and we did it on paper…
If you have any idea how to do it it would help us a lot !

Have a nice dayy

2

Is there only one pile of sticks and both players take from the pile? If so, any time it is your opponent’s turn and the number of sticks is 4k + 1, you can make it 4(k-1) + 1 after your next turn. Eventually k becomes zero and your opponent has one remaining stick (which they are forced to take).

So your goal is to make the pile have 4k+1 sticks after your play whenever possible. If it’s not possible, there’s no difference between picking 1, 2, or 3. For 16 sticks, the first person to move can always win (by starting with a pick of 3).

3

This is called “a subtraction game”, and is a form of the game of Nim.

If you google for “Nim” and “subtraction game” you should find a
lot of information.

Hint: if the computer player is unbeatable, the game will be boring. I
would consider either having at least two different computer players,
such as:

  • a player that always makes the worst move;
  • a player that always makes the best move;
  • a player that moves randomly;
  • a player that that makes the best move with some probability;

and the probability depends on the level of difficulty.

4

Yes exactly !
Thanks for the answer

5

Okay thanks a lot for the link and your advice !