20150308

Picking up Backgammon

The links to Amazon and The Book Depository are affiliate links. If you purchase like 50 copies I may afford a coffee :D

From Flickr
It all started after reading If you can’t choose, pick at random at Aeon.co. It delves into how choosing at random can be best in some cases. Give it a read, it is interesting. Among the HackerNews comments about this submission there were some mentions about choosing at random in real life, and to the novel The Dice Man (Amazon | Book Depository). I got interested in the idea.

My late afternoon routine usually consists of reading and probably playing with some iPad game. Since I’ve worked as an editor in an app review site, I have quite a wide array of games always installed on my iPad (current count: 106 games.) I ended up playing mostly the same games though, which is kind of stupid with such a wide array of options. Here randomisation entered: I generated a random number to choose a folder (well, a sheet in the “games” folder) and another one to choose a game within that folder. This way I got more varied entertainment (nice) and one day I picked up a backgammon app. And why not? Let’s play some backgammon, if it was good enough for Conway, I’m sure I can enjoy it eventually.

Exactly at the same time I was reading a lot of literature on improvement, to see what I could do to improve my go playing abilities. Anything from chess improvement books, psychology of practice, calculation when playing draughts. So a natural next step was to pick a few backgammon books and see if there was some lesson I could cross-reference to go. I could always just improve my backgammon and have some good games.

I quickly found out that backgammon is in the “same” set as chess. Even though not formally solved, the best computer opponents can slice through human players like a hot knife through butter. More interesting for me, backgammon engines are self-trained time-difference neural nets. You can read about seminal paper on this method by Tesauro, here. An advantage of having ultra-strong computers is that they can analyse your games and pinpoint which moves were good and also how bad the move was compared to perfect (well, computer-perfect) play.

So, I downloaded one of the best apps in the app store and started playing, all the while reading Bill Robertie’s Backgammon for Winners (Amazon | Book Depository). It works as a good introduction to the game all the while giving a lot of great pointers about strategy. At this point I should tell a little about how backgammon is played.

In backgammon your goal is to move all your 15 checkers to your “home.” The starting position has them spread out in a specific patter over the 24 positions of the board. Here you can see a diagram of the starting position. Black moves from 24 towards 1, white moves from 1 towards 24 (of course white sees it otherwise!)

If you want to create diagrams with TeX, check this package
The 6 places closest to your home are known as your home board, and correspondingly the 6 further away are your opponents’ home board.

To move your checkers you throw two dice, and can use either number on any checker (or both to one.) A lone checker on the board is named a blot, and if an opponent lands a checker on it (lands directly, not jumping) makes it go back to the bar. Then you need to re-enter the playing field, from the bar to the inner board of your opponent. If a position has more than one checker, it is known as a point (short of made point) and your opponent can’t land on it, needing to jump over it. So, the main strategy involves making points strategically, so you reduce your opponent mobility, and knowing when it is worth leaving a blot somewhere. A row of 2 or more points in succession are known as primes, and prime-making is a fundamental strategy. The best of course is to make all points in your home board and then hitting your opponent: since all points are closed there is no way to re-enter from the bar. But strategies are varying depending on how the rolls go, and as such several kind of “games” (in chess lingo they have open and closed games, in go we have moyo games and territory games… backgammon has also different kinds depending on strategy picked.)

Rules are simple (verbalising them is the hardest part, I have just found :D) but make up for a very interesting and fast-paced game. Oh, before I forget there are two more things. Backgammon is played in matches for points, because a backgammon game can end with 3 different results: A normal win is scored when you just get all your checkers to home and your opponent also got some to hers. A gammon (which scores twice) happens when you get all and your opponent got none to home, and a backgammon (scores thrice) when there are still enemy checkers in your home board when you finish. In addition to the different game results, a game changer (and something I really like about backgammon) is the doubling cube. The game starts with a dube numbered in powers of 2 from 2 to 64 between the players. When a player feels ahead, he can pick it up and offer a double. Then, the opponent can accept (hence, they play the game for 2–4–6 points instead of 1–2–3 points) or reject it (resigning for just 1 point.) The player who accepts now owns the cube and can double at her own discretion. The process could go up indefinitely, but of course it doesn’t. The doubling cube just works perfectly to shorten matches and games, greatly speeding play.

Back to reading suggestions, Bill Robertie’s Backgammon for Winners (Amazon | Book Depository) has enough strategy to get you covered, but eventually you’ll find yourself needing something more, and I can heartily recommend Magriel’s Backgammon (Amazon). Huge book, very interesting and well-written. I have read it 1.5 times already, and there’s still lots of things I get wrong in my games.

If you have never played backgammon I recommend you pick some free app and start playing in your computer, tablet or smartphone. I personally can recommend Backgammon NJ which is available for Android and iOS and GNU Backgammon for Mac (or Windows, or Linux.) I actually don’t recommend playing on a real board. You’ll get slogged by counting where 6 goes from here to there, computers make it easier by showing all valid moves. It took me 4 months and several hundred quick games against computers until I got good at “moving” so I know by sight where moves go.

If you are looking to play with real people, once you have picked up rules and have some knowledge, head over to Dailygammon. It is 100% free, turn-based play, and has an awesome feature that lets you play much faster than usual. You roll and move, and then the computer assumes your opponent did the best move for their roll, gives it to you and lets you enter more moves. If your opponent is good (so, he actually picks the best move when offered) games are really fast, since you are effectively playing in parallel. And if he does not, the game is “as slow” as any turn-based. Neat, isn’t it?
Written by Ruben Berenguel

20140102

The Mandelbrot set in one line of APL

Is this line noise?
⍉' *'[⍎'1+0<|z',(∊150⍴⊂'←c+m×m'),'←c←(¯2.1J¯1.3+(((2.6÷b-1)×(¯1+⍳b))∘.+(0J1×(2.6÷b-1)×(¯1+⍳b←51))))']

NOTE: if you are not seeing several Greek looking letters and arrows in the line above, some UTF8 stuff got wrong. Sorry, I'll try to fix it, drop me a tweet!

Nope. This is not line noise, but a complete APL program to display the Mandelbrot set in glorious ASCII, with asterisks and spaces just like Brooks and Matelski did a long time ago while studying Kleinian groups (it's a short paper, read it someday). I'll explain in (a lot, I hope) detail this line in a few moments. So, what's APL first?



APL is literally A Programming Language. Funny, isn't it? Its origins can be traced back to a way to formalise algorithms created by Kenneth Iverson while at Harvard. It is famed as a very cryptic language, for a reason. Its fundamental functions are unicode chars, and at first it feels extremely weird.

I got interested in it after finding an iOS interpreter for J, a programming language developed as a successor to APL, also by K.I. It just got away without Unicode, leaving only cryptic dygraphs, like <.@o. (from a Wikipedia example of high precision computing.) J is very cool, in that it offers a terse syntax to operate with matrices and vectors, very much like Matlab (Octave in my case) or R. But I felt I'd rather check the first idea, before diving into the even weirder syntax of J. So, it was APL.

The first problem was finding a good APL interpreter. Most were paid (and extremely expensive) and I could only find 2 APL interpreters working in Mac OS. One is NGN APL an implementation focused on node.js Also usable on a browser, so it is cool. But I'd rather get a little closer to the system... And decided to use Gnu APL instead. Of course, using an emacs mode for gnu-apl. Caveat: make sure to add

export LC_ALL=es_ES.UTF-8
export LANG=es_ES.UTF-8


to your .zshrc or similar, without it you'll need to add a hook to gnu-apl mode reading

(set-buffer-process-coding-system 'utf-8 'utf-8)

to make sure emacs and apl talk in utf-8. Without it, there are no commands to send to the interpreter!

Since I'm also a heavy acme user, and acme is well-known in its unicode support, I used it instead to develop that line above. But emacs works correctly, I just like having things to tinker with acme.

Getting back to the line-noisiness of APL, first you need to know that precedence is right-to-left, so

3×3+1

in APL yields 12 instead of the expected 10. You can change this with parentheses. Now that I have taken this out, we can analyse the line above. Instead of explaining it from right to left, I'll explain how I proceeded to develop it.

Iterating the quadratic polynomial

(∊150⍴⊂'←c+m×m')

Put it succintly (I could explain a lot of the mathematics behind, but I just want to do a picture today) to draw the Mandelbrot set we need to find complex points c=x+iy (remember: you can think of a complex point as a point in a plane, like a screen: it has an x coordinate and a y coordinate) such that computing

f(z)=z^2+c

a lot of times with z=c is eventually a point outside a circle of radius 2. For instance, if c=1 this would be:
  1. f(1)=1^2+1=2
  2. f(f(1))=f(2)=2^2+1=5
  3. f(f(f(1)))=f(5)=25+1=26
And so on. In this particular case, after the first iterate we could stop. Remember that to do so, the product c·c is the product of complex numbers.

So the first part I wanted to get out of my way was generating this iteration. There are several ways to do it in APL, but a very cool way I found was to first generate the required computation like above. How?

'c+m×m'

computes exactly this, if m=c or if m is any other iterate, like m=f(f(f(c))). In APL speak, making m hold the same as c would be

m←c

and since right-to-left priority,

c+m×m←c

means "assign to m the value of c, multiply m by m (remember: it's the same as c) and add c." Likewise,

c+m×m←c+m×m←c

ends is computing the 2nd term in the list above, if c 1. So we have a pretty clear idea of how it should look like:

something←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c+m×m←c

This is essentially "many times" the string " c+m×m" There's a very very easy way to repeat stuff in APL. For instance, 3 ⍴ 1 (read 3 reshape 1) creates a vector with three ones, 1 1 1. Reshape essentially multiplies or trims vectors. But... 3 ⍴ 'tomato' is 'tom'. The reshaping also cuts, of course! What we need is to make APL treat the string ' c+m×m' as one element. This is done with the next instruction in the Mandelbrot line, as you may guess: encapsulate.

⊂'←c+m×m'

ensures APL treats it as one element, so

20⍴⊂'←c+m×m'

generates a neat and long string of what the iterates should look like. To make sure the final string makes APL-sense, first we "enlist" with ∊. Turn the vector of repeated iterates into just one iterated element, like a long string all together. This could actually be removed, but it allowed me to learn a new function and I think it's pretty interesting. To end in a proper way, we add to the string a receiver variable 'z' and fuse the strings with comma.

I know this was long, but the iteration was the trickiest part!

Generating the grid of points

'←c←(¯2.1J¯1.3+(((2.6÷b-1)×(¯1+⍳b))∘.+(0J1×(2.6÷b-1)×(¯1+⍳b←51))))'

Since APL is cool with matrices (and complex numbers!) we can assign to the initial c a whole matrix of complex points (our screen pixels) and then we'll have all the stuff required for the picture.

This weird piece is just a compact way of generating a grid. To make it easier to understand, ⍳5 (that's iota 10) generates the sequence 1 2 3 4 5. To create a matrix we need two sequences (one for the x coordinates and another for the y coordinates.) For the complex numbers we can do 0J1 ⍳× 5 which yields 0J1 0J2 0J3 0J4 0J5. As you may guess, 0J1 is just the complex number i. For some weird reason APL uses the j letter instead of i. No big issue. Now we have the x's which go from 1 to 5 and the y's which go from i to 5i Now we need to find all the complex points in the plane. This means adding one of each x to each y, to get a grid. Similar to a multiplication table, but with sums instead of products. APL magic to the rescue!

(⍳5) .+ (0J1×(⍳5))

yields

1J1 1J2 1J3 1J4 1J5
2J1 2J2 2J3 2J4 2J5
3J1 3J2 3J3 3J4 3J5
4J1 4J2 4J3 4J4 4J5
5J1 5J2 5J3 5J4 5J5


which is pretty close to what we need. To plot the Mandelbrot set we are only interested (mostly, and in this particular instance) in points with real coordinate x between -2.1 and 0.5 and complex coordinate between -1.3 and 1.3 (just to make it square which is easier.) This long blurb just adds a matrix similar to the one above to a complex point, generating the grid of points we want, and assigns it to c. Almost done!

Computing and plotting

⍉' *'[⍎'1+0<|z',

After we have the set of points in c, we merge this string (with comma) to the iteration we developed above. At the far right of the iteration we find this piece
'1+0<|z',

As you may guess, this adds to the string 1+0<|z which from right to left does:

  1. Compute the norm (distance to the origin) of the final iterate, which was assigned to z at the end of the iteration with |
  2. Check if this is larger than 4. This generates a matrix of 1s and 0s
  3. Add 1 to all entries of this matrix (so we have a matrix full of 1s and 2s

NOTE: The first version of this code had 0<|z, which works well for rough images of the Mandelbrot set, since most iterates are eventually INFNAN, which is a funny number in programming, since it is positive, smaller than 0, different from itself... Almost anything :D

We have a neat string which can generate a matrix of 1s and 2s and represent the Mandelbrot set. How do we make this string compute something? Magic!

⍎ (known as execute) takes a string and computes it as an APL function. Magic! (just like eval in Lisp or Javascript, actually)

Represent it neatly

⍉' *'[stuff]

Since a matrix can be used to index a vector, we use this newly computed matrix as indexes (i.e. between square bracket) with the vector ' *' so we get almost a Mandelbrot set. But since I was slightly lazy when generating the grid of points, it is transposed. ⍉ (transpose) fixes it and finishes the program.

Conclusion

Writing this line of code took me quite a long time, mostly because I was getting used to APL and I didn't know my way around the language. Now that I'm done I'm quite impressed, and I'm looking forward to doing some more fun stuff with it. And if possible, some useful stuff.
Written by Ruben Berenguel

20131102

My Russian KL-1 Circular Slide Rule (and a small intro to slide rules)

A few months ago (woah, so long already!) I had an impulse buy: I purchased a circular slide rule from Etsy. It was cheap, and I had always wanted one, so... I just bought it (a neat addition to my Addiator.)

I guess if you are geeky enough to read mostlymaths.net, you know how a slide rule works. Although I knew how to use it, getting to grips with it took a little while. Just to make sure you follow along here's a brief explanation.

In a normal rule (as pictured below) you can measure a distance, add the distance to another one and get a new distance. 4 and 4 are 8, see?


A slide rule works exactly the same, but the scale on the rule is logarithmic. This means that if you measure the distance between 1 and 3, and add it to the point 3, you get 9 (which is 3 times 3.) This is because in a linear scale distance measures the difference (b-a) and in a logarithmic scale it measure ratios (b/a)

Usually you will do this using a piece labeled the same as the slide rule:


In a normal slide rule (the long wooden or aluminium thing) you have several scales, all placed together with an indicator to know where to measure. In the simplest setting a slide rule is basically what is shown above: a way to fix a distance and displace it along. You could do it with your fingers, even!

In a basic model of circular slide rule (like the KL-1) you have something that works much like this. See the picture below:


If you look carefully you'll see a marker (which is place just below a knob, and fixed in the glass cover) and a red marking needle (it's hard to see, but it's red.) In this picture you'll also see the logarithmic scale (below, from 1 to 9) and a square scale just on top (from 1 to 90.)

The black knob (on top of the fixed marker) displaces the scale, leaving the red marking needle wherever it is (it moves the paper where the scale is written!) and the red knob (the other one) moves just the needle, hovering above the paper.


If you set the black marker on 1 by moving the black knob and then the red marker on (for example) sqrt(2) (which is the number just below 2 in the square scale!) you are fixing the ratio 1-sqrt(2) (roughly 1-1.4)


If you now twist the black knob, you are moving the scale while the distance black-red remains perfectly fixed. So if you place the black marker above 2, you are "adding" the ratio of sqrt(2) and 2, which means 2 times sqrt(2) (roughly 2.8):


So, no mysteries in how this works! In the back there are a few trigonometric scales (known in the slide rule lingo as the S and T scales, for sin and tan):


For the sin and tan scales, you place the cursor (the red marker) in the degrees scale (the one from 10 to 90) and you read the sin of it on top. For the tan, you need to check the degrees in the spiraling scale in the center, and read the tan of the angle also on top.

What's it good for?

Such a small circular slide rule has a very low precision (2 digits more or less.) This essentially makes it pretty much useless for me, since I have more or less the same precision in mental division or multiplication. 

Anyway, I have used it several times when checking traffic numbers for websites, when estimating daily visits from monthly or bimonthly numbers. Once you set the number of days as ratio, it's pretty fast.

An interesting use would be for quick currency conversions while abroad (you fix the ratio and can easily convert from currencies) but since I travel mostly in Europe, I can't use it for this (Norway, Iceland, Great Britain and Denmark are good targets still.)

People still use slide rules though: nomographs (what the sin and tan scales are, actually) are a quick way to compute things, and are used in aviation, electric engineering and other fields where speed is interesting and 5 digit precision is not as important.
Written by Ruben Berenguel