"Beggar my neighbour" is a completely deterministic card game with the following rules:
"A standard 52-card deck is divided equally between two players, and the two stacks of cards are placed on the table face down. The first player lays down their top card face up to start a central pile, and the opponent plays their top card, also face up, on it, and this goes on alternately as long as no Ace or court card (King, Queen, or Jack) appears. These cards are called "penalty cards".
If either player turns up such a card, their opponent has to pay a penalty: four cards for an Ace, three for a King, two for a Queen, or one for a Jack. They do this playing the required number of cards to the central pile. When they have done so, if all the cards are numerals, the player of the penalty card wins the hand, takes all the cards in the pile and places them under their pack. The game continues in the same fashion, the winner having the advantage of placing the first card. However, if the second player turns up another Ace or court card in the course of paying to the original penalty card, their payment ceases and the first player must pay to this new card. This changing of penalisation can continue indefinitely. When a single player has all of the cards in the deck in their stack, they have won.
For more than two players, play proceeds clockwise. If a player reveals a new penalty card while paying their penalty, the next player around pays the tax."
As explained in the Wikipedia page: https://en.m.wikipedia.org/wiki/Beggar-my-neighbour
Currently it is unknown is there exist games that go on forever, but if they do, they are extremely rare.
Overall there are about 6.54*10^20 different starting deck configurations, which means that one cannot simulate all possible games.
This problem needs to be modelled in a more formal way in order to be tackled properly, but this is much easier said than done.
How would you approach this problem?
"A standard 52-card deck is divided equally between two players, and the two stacks of cards are placed on the table face down. The first player lays down their top card face up to start a central pile, and the opponent plays their top card, also face up, on it, and this goes on alternately as long as no Ace or court card (King, Queen, or Jack) appears. These cards are called "penalty cards".
If either player turns up such a card, their opponent has to pay a penalty: four cards for an Ace, three for a King, two for a Queen, or one for a Jack. They do this playing the required number of cards to the central pile. When they have done so, if all the cards are numerals, the player of the penalty card wins the hand, takes all the cards in the pile and places them under their pack. The game continues in the same fashion, the winner having the advantage of placing the first card. However, if the second player turns up another Ace or court card in the course of paying to the original penalty card, their payment ceases and the first player must pay to this new card. This changing of penalisation can continue indefinitely. When a single player has all of the cards in the deck in their stack, they have won.
For more than two players, play proceeds clockwise. If a player reveals a new penalty card while paying their penalty, the next player around pays the tax."
As explained in the Wikipedia page: https://en.m.wikipedia.org/wiki/Beggar-my-neighbour
Currently it is unknown is there exist games that go on forever, but if they do, they are extremely rare.
Overall there are about 6.54*10^20 different starting deck configurations, which means that one cannot simulate all possible games.
This problem needs to be modelled in a more formal way in order to be tackled properly, but this is much easier said than done.
How would you approach this problem?
