New Keyboard Layout Project: Overview

New Keyboard Layout Project: Efficient Genetic Algorithm Optimization

For p = 48, b = 16, k = 1, o = 1024, q = 2048, the program got the best layout possible in just over fifteen minutes. Considering that to find the best layout by brute force would take a billion times longer than the universe has existed for, that’s a pretty impressive feat.

Even more impressive is q = 64. You might say, “Why in the heck was q so large in the first place?” My rationale was this: it’s the final round. You want to get the best possible layout. And even in the worst-case scenario, if q = 2048 the keyboard has a 99% chance of improvement. But it looks like that was excessive, because q = 64 has about a 50% chance of getting the best possible layout, and in only about ten minutes. (I ran it twice: one time it got the best layout, and the other time it got a layout that is very very close to the best, but not quite.) That all-star round with 1024 layouts and 2048 iterations was gobbling up a lot of time.

I am currently using this cost distribution. See my keyboarding page for an explanation of what these mean.

Inward roll:  -14
Outward roll:  -4
Same hand:      2
Same finger on...
    pinky:    100
    ring:      90
    middle:    70
    index:     55
Row change:    10
Home row jump: 40
	index: -30
To center:     10

Also, each position on the keyboard has a cost based on its difficulty to reach. These costs are not just based on my own assessment, but also on the placement of keys on some of the better keyboards out there.

 70 40 30 30 60   80 30 30 40 70
 10  4  0  0 30   30  0  0  4 10
 90 85 60 50 95   70 40 60 80 90

Normally the ring finger and pinky would cost 0 since no movement is required, but I wanted to keep E and T off of the pinky and E off of the ring finger. Those letters are far more common than any other, and it would put too much stress on those fingers.

And the best possible layout under this scoring system is:

k c f p b  j h u w .
o s a t d  l n e r i
q v , g z  ; m y x '

By the way, this layout is officially called MTGAP 3.2. You don’t have to worry about the version-numbering system; it’s a little erratic.

Is this really the best possible layout, or is the scoring system flawed? Let’s look at some of the problems with this layout.

-The fa/af digraph is fairly common. I assume that the program made it because the middle finger can handle same finger usage rather well (at least according to the scoring system). Also, if you’ve ever tried, it is exceptionally hard to find stuff to put on the same finger as ‘a’. It is usually placed on the pinky and then put with either a really rare letter like q or j, or with punctuation. But the algorithm thought it better to put a on the middle finger. Why?

To find out, I worked with rearranging some parts of the layout.

-You can’t switch i and a. i can only be paired with u, y, and punctuation. The spot above the middle finger is too good for y, so that won’t work. e is already using u and there isn’t really anything else for e to go with, so u is out. That just leaves punctuation. But the spot above the middle finger is still too good for punctuation. What does that leave? Pretty much nothing. f, though, is common enough that it can be placed in that spot. (By the way, if all this talk about letter frequency is confusing you, check out this graph.

-You can’t switch a and s. You end up with the exact same problem as you had initially: what do you put over the a?

-You can’t switch o and a. o has the same problem as a and i, only worse. Remember when I said that a is exceptionally hard to pair with other letters? Well, o and i have it even worse, and e has it worst of all.

So how have other layouts coped with this problem? By making sacrifices.

q w f p g  j l u y ;
a r s t d  h n e i o
z x c v b  k m , . /

Colemak copes with the problem by sacrificing some finger travel distance. Colemak has the lowest same finger usage of any layout I’ve seen, but it can only do this by making sacrifices. c is placed in a hard-to-reach position, for one.

Colemak actually copes remarkably well. Capewell and Arensito do not cope very well at all. They end up placing punctuation and rare letters where they shouldn’t be. Dvorak is even worse. So it looks like having the fa/af combination on the same finger is the best choice after all.

I will look for more potential problems later. Right now I’ve got some other fish to fry. As always, I welcome comments and feedback.