# Combinatris: How to Play

#### Dirk van Deun, dirk at dinf.vub.ac.be

Combinatris is played with four combinators, represented by the letters I, K, S and Y. These always appear at the left side of the playing field and move to the right. You use the up and down arrow keys to distribute them over the five available lines. This way you build five sequences of combinators at the right side of the playing field, sequences which we will call combinations. Each time you add an extra combinator, the resulting combination will be reduced automatically according to the rules below. The game ends when one of your combinations fills a whole line and cannot be reduced.

Which reduction rule applies to a combination is determined by its leftmost combinator. For instance, the rule for K says that you keep the first combinator following it, but the second one disappears; and the K itself is also "used up" during the reduction. Three examples will make that clear. Example 1: KSI reduces to S. Example 2: KS cannot be reduced: K is followed by only one other combinator, so the rule cannot be applied. Example 3: KSKI reduces to SI: the I at the end is not involved. As it does not matter to the rule what the second and the third combinator are, we can write the rule as Kxy → x. Now let's take a look at all four reduction rules. Do not spend too much time studying them though: you will get a much better feel for the rules by playing.

Ix → x
The I combinator is pretty harmless by itself. An I combinator added to another combination just disappears.

Kxy → x
The K combinator is the one you want to get often. It shortens combinations as explained above.

Sxyz → xz(yz)
The S combinator is the one you actually get often (and more and more often as you reach higher levels). The S combinator rule needs three more combinators to work: it rearranges them as shown, and you will have noticed that it introduces parentheses. So even though it is said to reduce the combination, it actually makes it longer: for instance, SSKI becomes SI(KI). This ugly rule was not made up as arbitrarily as it may seem: there is symmetry to it if you think of it as Sxyz → (xz)(yz). The first pair of parentheses are never written, however, as they would be dropped immediately anyway.
A pair of matching parentheses and everything in between counts as one big combinator. If such a composite combinator is in leftmost position however, its parentheses disappear. For example: K(IK)S reduces to (IK), which becomes IK as the parentheses are dropped, so the combination can reduce further to K.

Yx → x(Yx)
Y is the most powerful and also the most dangerous combinator, because reducing a combination that starts with Y immediately introduces a new Y. For instance, according to this rule, YI becomes I(YI); after which, according to the I rule, I(YI) reduces to (YI), which is simplified to YI by dropping the parentheses, which brings us back to our point of departure; which means that the whole thing can start over again.
This could go on and on and earn endless points, but it doesn't. If the game detects such an endless repetition going on, it will end and you get no more points at all. A combination with a Y combinator can also keep expanding endlessly, which is why the game will immediately end if a combination grows wider than the playing field, even if the combination can still be reduced.

Parentheses do not only occur in the game as the result of S and Y reductions: they also appear as new elements for you to find a good spot for. They then come as matched pairs with two or three spaces in between. Combinators that bump into such pairs of parentheses will slide into them, until there is no room left in between. Other pairs of parentheses will too. Combinations with parentheses that still contain spaces are incomplete and can never be reduced. That is a good thing if you are building a long and complex combination and you do not want it to start reducing yet. It is a bad thing if you have too many of them and you cannot get rid of them fast enough.

Why you would build long and complex combinations on purpose brings us to scoring and strategy. Each reduction is good for 10 points, and so is the elimination of a pair of parentheses. For every 500 points you will go up one level, and the game will get harder, until you reach level 5. The challenge for the novice player is to reach level 5 (i.e. 2000 points); the challenge for the advanced player is to reserve one or two lines during the easier levels for building one or two long and complex combinations, in such a manner that adding one extra combinator during level 5 can set off a chain reaction of reductions, earning hundreds of points in one stroke during this otherwise almost unplayable level. Such a strategy makes the earlier levels harder, but it can give you a boost of up to some 1000 points at level 5. After that, even skilled players will usually not last much longer. So for an advanced player, good scores start at 3000 points.

When you have already moved a new combinator or pair of parentheses to the line where you want them, you can use the right arrow key to speed things up. The space bar will pause the game. Pausing the game to take some time to think should be considered cheating during a competition for a top score.

You might wonder why the letters I, K, S and Y were chosen as names for the combinators. They are taken from combinatory logic, which is a branch of mathematics. Our combinators I, K and S are exactly the same as in combinatory logic; but our Y combinator cheats a bit in the interest of gameplay, as in combinatory logic Yx is indeed equivalent with x(Yx), but does not directly reduce to it.

Play the game