I just added a Nim game called Abacan to the Grey Matters Store. The main piece is a triangular shape with 25 beads in it, distributed as rows of 1, 3, 5, 7, and 9.
Abacan has rules that are slightly different from the previous versions of Nim discussed here on Grey Matters. To make this simpler, I'll review some previous versions of Nim before moving on to Abacan's peculiarities.
Let's start with single-pile Misère Nim (last player to move loses), using 25 objects, and each player is only allowed to remove 1, 2, or 3 objects on their turn. With your previous knowledge and a little practice, or the use of the Single-Pile Nim Strategy Calculator, you should have no problem determining that the other person should go first, and you need to hit the key numbers of 21, 17, 13, 9, 5, and 1.
For multi-pile Misère Nim, with rows of 1, 3, 5, 7, and 9, you'll need the binary understanding of multi-pile Nim taught here (and made easy to visualize here) and the endgame play knowledge of multi-pile Misère Nim taught here. The Multi-Pile Nim Strategy Calculator can help you learn the ideal strategy for this version.
If Abacan went by either of these rules, you'd be all set. However, as you'll see in the video review below, there's a subtle difference. You're only allowed to move 1, 2, or 3 beads, all from the same row, on each turn. The last player to move a bead loses.
Reducing the problem: The first step in Abacan strategy is, not surprisingly, treating each row as if it only had 0, 1, 2, or 3 beads in it, regardless of the actual number of beads in each row. This works out as follows:
Actual number of beads: 1 2 3 4 5 6 7 8 9
Reduced number of beads: 1 2 3 0 1 2 3 0 1
So, a row of 4 beads would be treated as if it had 0 beads, 5 beads would be treated as 1 bead, and so on. Effectively, you're simply subtracting the nearest multiple of 4 equal to or less than the number of beads in a given row. 9 becomes 1 because 9 - 8 (the nearest multiple of 4 less than or equal to 9) = 1.The mathematical term for this process would be taking modulo 4, or “mod 4.” You can learn more about modular arithmetic via this fun and clear post at BetterExplained.
Abacan strategy 1: Toward the end of multi-pile Misère Nim, the ideal strategy is to leave your opponent an odd number of row, such as 1, 3, or 5, that each contain a single object. That will also work in Abacan, except that row you're treating as a single object may actually contain 1, 5, or even 9 beads! Let's examine various types of Abacan arrangements to see how we can do this.
All 4s and 8s: The simplest situation is when all the rows in play are multiples of 4. Let's say it's your turn, and there are rows of 4, 4, and 8 beads. You start by reducing the problem as discussed above, so the rows translate into rows of 0, 0, and 0 beads. In a normal game of Nim, every row consisting of 0 beads would be the end of the game, but not in Abacan!
If we slide 1 bead from the row of 8, leaving 7 beads, we see that 7 reduces to 3, so by moving 1, we effectively added 3 to one of the piles. This is also true of the moving 1 from the 4 pile, which also creates a row of 3.
Similarly, moving 2 beads from any row of 4 or 8 effectively adds 2 beads to that row, and moving 3 beads in a row of 4 or 8, effectively adds 1 to that row.
Remember strategy 1 above. If we can create an odd number of rows containing a single object (or a number can be reduced to a single object), we're a step closer to winning!
So, with our example rows of 4, 4, and 8 (again, this reduces to 0, 0, and 0), sliding 3 from the first row would give us 1, 4, and 8, which reduced to 1, 0, and 0 - an odd number of 1s!
Yes, you could slide 3 from the middle row instead, resulting in 4, 1, and 8 (reduces to 0, 1, and 0), with the same result. What happens if you slide 3 from the row of 8? You'd wind up with 4, 4, and 5, which reduces to 0, 0, and 1 - still resulting in the odd number of 1s needed to satisfy the strategy!
Mixed 1s, 4s, 5s, 8s, and 9s: If all the rows in play reduce to 1s (1, 5, and 9 beads) and 0s (4 and 8 beads), this strategy will still work. As an example, let's try rows of 1, 4, 5, and 8, which reduces to rows of 1, 0, 1, and 0 respectively.
The obvious move here would be to remove 1 bead from either the row of 1 or 5, resulting in either rows of 4, 5, and 8 (reduces to 0, 1, and 0) or 1, 4, 4, and 8 (reduces to 1, 0, 0, and 0), giving us an effective single row of 1.
There's another less obvious option here, as well. Remember that you can take rows reduced to 0, and effectively add 1 to them by removing 3 beads. If we take 3 from the row containing 4 beads, we're left with 1, 1, 5, and 8 beads, which reduces to 1, 1, 1, and 0 beads. There are now 3 rows which reduce to a single bead, which still satisfies strategy 1.
Removing 3 beads from the row of 8 would also have the same effect. The resulting piles would be 1, 4, 5, and 5, which reduce to 1, 0, 1, and 1, giving us another 3 piles of single objects. In other words, there's often more than one way to get to a safe position.
Mixed 1s, 4s, 5s, 8s, and 9s with a single 2, 3, 6, or 7: 2 and 6, as explained under Reducing the problem above, both reduce to 2, and 3 and 7 both reduce to 3. If there's just a single row consisting of 2, 3, 6, or 7 beads, and all the rest reduce to 1s and 0s, the same strategy will still work.
Let's assume that you turn leaves you with rows of 1, 4, 6, and 8 beads. As always, the first step is to reduce the problem, which gives us 1, 0, 2, and 0 beads. We're looking for a way to get to an odd number of 1s, and so the simplest solution is remove 2, leaving us with a single 1. So, we slide 2 from the row of 6, leaving rows of 1, 4, 4, and 8, which reduces to 1, 0, 0, and 0 beads!
You can practice your skill at reducing the problem by having Wolfram|Alpha generate random bead arrangements for you. If a randomly-generated arrangement happens to satisfy the situations I've already explained, you can also practice finding the best move. Keep in mind, Wolfram|Alpha may also generate an arrangement from which there is no winning move for you. This is valuable, as you'll start learning how to discern arrangements you can win from ones you can't.
If there are several rows, each with 2, 3, 6, and/or 7 beads, however, you'll need to learn and use a different strategy. We'll cover that strategy in the next post.
Posts
No Response to "Secrets of Nim (Abacan 1)"
Post a Comment