As I promised it is time to answer the question, how to live… I mean to play. If you happen to win the game about subtracting balls, I congratulate you. If you win every time, I compliment you even more but why didn’t you try to push the green button? Yes, when the computer plays first, you cannot win this game. The computer doesn’t make mistakes and his first move determines the result. So, you have to start the game with good first move and consequently make all proper next moves.
What does it mean proper, should you ask?
The answer refers to interesting issue, which always was subconsciously interesting to me. I mean the process of discovering the solution to some mystery, exercise or problem and the extent to which we really understand found solution. I will only touch the surface of this subject but I’m sure it will be coming back in the very next posts.
I was that lucky, that I showed Subtraction Game to a few people and could look at how they cope with the problem the game introduces. Some of them I didn’t even know earlier so I really didn’t have any presumptions of their approach. First way of doing it was of course trial and error method. After some observations about what moves lead to what consequences and after testing some edge cases, the person applying this method came to conclusion that for example one should always take two balls. Which sometimes lead to the success and sometimes didn’t. Only a few trials were enough to satisfy the player with the win. This method was, of course, harder to be successful for players more eager to take the option where computer played first. Unless…
There was one player, who noticed that if computer always wins if it starts the game, it is easier in this mode to find what computer chooses to play and mimick it in own game when he initiates the play. And after couple of trials it certainly appeared that computer probably always begins with subtracting two balls and then if the player takes one ball, it chooses two balls and if the player chooses one ball, it chooses two balls. Always the opposite or saying it differently, that except first move, player and computer take 3 balls together in one turn. And this is a quite right solution!
But why is it so and do we really understand it?
We can check it out, for instance, by increasing the number of balls by 2. The game is near the same then, but if we take away two balls at the beginning we shift the game as if the computer starts with twelve balls. Additionally we can make it harder by raising the number of balls we can remove in one turn. For example, what if you eliminate one, two or three balls at once. I encourage you to experiment below in specially prepared version of the game where you can initialize both parameters as you like, if it is the starting balls number or balls-to-take-in-a-move number alike. In this way you can create your own variant of the game from whole class of games about subtracting the balls.
OK. We’ve experimented – was it helpul to understand the problem or made it even more confusing? Let’s note how important it is who starts the game. First move determines who takes the twelfth ball after at least five turns more. How, on the other hand, does the endgame look like? If you want to win you have to leave the last ball for your opponent. If there are two balls – you take one, if there are three balls – you take two. So what if there are four balls left, which means you cannot leave only one ball after your move, what should you do? Unfortunately in this situation you have no option, whatever you do, the opponent is the one who has a chance to leave you with one ball at the end because we give him more than one but less than four balls.
At this very moment we should get enlightened that we not only win by leaving the last ball for opponent but also, in a way, when we leave the forth ball to him. We win a stage which enables us to win the next one.
Therefore we can look at the problem from different angle. If we must make an opponent to take the forth ball from the end to win the last one, we could, in our imagination, remove 3 last balls and to this moment play as if the forth from the end would be the last ball. And here comes simple idea to do such things with the next groups of 3 balls until the first three or less balls remain. From these first balls we leave just one for opponent ensuring he takes it and leaves us more than one from the next group.
We execute this strategy until the happy end. See how I divided the balls into groups on the picture below. The same should be done during the game, leaving the last ball of every group for the opponent.
Pic. 1 – Division into groups
Now try again to play the above version of the game and check if you can generalize this strategy for any numbers of balls. For easing the counting and dividing into groups I added informations during the game about how many balls are left and how many of them are chosen by the player or the computer.
I think that, at this moment, we are a little bit tired of the subject of balls and this game, so I will let myself stop it for the time being, despite my plan of describing the decision tree and elegant mathematical formula of the game’s algorithm. I’ll do it when other opportunity occurs, in the meantime I should go forward!
As usual all comments and discussions are kindly welcome 🙂