New Keyboard Layout Project: Fast Typing Combinations

It’s been a while since I posted anything about the New Keyboard Layout Project. But I recently downloaded Amphetype and have been analyzing my typing patterns, using MTGAP 2.0. So I now have some results, and will probably get more in the future.

The fastest trigraphs to type almost all are either a type of one key on one hand followed by two keys on the other hand, or they are a roll on one hand in one direction. Most of the slowest trigraphs alternate hands every time, and a good number of them are all on one hand in awkward combinations. The fastest words have easy rolls on both hands: what is currently the fastest word, “should” with an average of 176 WPM (hint: my average typing speed is about 85 WPM), uses a combination of hand alternations and easy rolls. In QWERTY, “should” would be typed as “jeaior”. The “ul”/”io” combination is very fast; also, “od”/”ar” is very fast, and the difference between the finger strokes to type “o” and “d” are very brief because the two letters in between are typed too fast. (Does that make sense?)

I will report more fast combinations after the program gets enough data for some better results.

Typing Program Release

I have made some improvements to the typing program to make it more user-friendly. You can get it at mtgap.bilfo.com/Typing.zip.

New Keyboard Layout Project: Program Release

You can find my source code at http://mtgap.bilfo.com/Typing.zip. The new and faster algorithm was written by Chris Johnson, a.k.a. Phynnboi.

The algorithm repeatedly returns this result.

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

Fitness:       2263451098
Distance:      9003112
Inward rolls:  7.04%
Outward rolls: 4.48%
Same hand:     22.80%
Same finger:   0.68%
Row change:    9.01%
Home jump:     0.34%
To center:     4.17%

This is a very good layout. Strangely enough, though, if you run the algorithm for longer it comes up with this layout, even though it has a lower score:

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

Fitness:       2263597180
Distance:      9599916
Inward rolls:  7.20%
Outward rolls: 2.20%
Same hand:     16.85%
Same finger:   0.64%
Row change:    7.64%
Home jump:     0.28%
To center:     1.74%

Which is better and why? How can improvements be made?

Biases of Genetic Algorithms and Simulated Annealing

Both genetic algorithms and simulated annealing have a serious problem: they get stuck. There are some possible layouts which could be very good, but which the algorithm will never get to since it requires getting past a certain hurdle. So how can this be solved?

1. Let a layout live and mutate for a while before you kill it. The problem with this is one of memory. You’re going to need some really huge arrays to hold all of those layouts.

2. Make one or a few keys inactive. This was inspired by a bug which led to some interesting results. The idea here is that you make a particular letter cost nothing, and run the algorithm as normal. If this letter was acting as a “wall” preventing the algorithm from getting to a good layout, the wall will be taken down. Then, after a few iterations, insert the letter again. I tried this out, and it had minimal effect. On the other hand, it didn’t slow the program down by much, either.\

3. Make one or a few scoring criteria inactive. This could more effectively break down potential walls than #2. This is tricky to implement reliably, though. If you rotate through the scoring criteria, making each one inactive in turn, then the definition of “best” changes every generation and so the program never comes to a stopping point. If you remove each criterion for a few generations but only one time, then you don’t know if it is adequately hurdle-skipping. And then there’s the added problem that the actual fitness will be reduced, and that has to be balanced somehow.

Are there any other methods that could actually work?

Simulated Annealing vs. Genetic Algorithm

When I read about simulated annealing, I considered implementing it instead of a genetic algorithm. But I decided not to. Why? Simulated annealing relies on the assumption that the best layout is next to the second best layout, which is next to the third best layout, etc. But this is likely to be untrue. The second best keyboard probably looks nothing like the best keyboard. But genetic algorithms avoid this problem, through repetition. The “all star” round contains many very good layouts, so it is more likely to converge on the best layout.

But when I saw some results, I had to reconsider. Simulated annealing is seemingly much faster. But how can we get it to converge on the best possible layout? Could we do something like simulated annealing, but then repeat it and pool all the best layouts and evolve those using a genetic algorithm?

I ran some empirical tests, and it turns out that simulated annealing is indeed many times faster than a comparable genetic algorithm. Chris Johnson sent me some source code, and it turns out that it is indeed much faster.

Simulated annealing works sort of like a “smart” genetic algorithm with a pool size of only one. Instead of just making any old mutation, it looks for good mutations to make. This allows much faster convergence. But this strategy, as well as the genetic algorithm strategy, can sometimes skip over very good layouts, or even the best. I will explain in a later post, coming soon.

New Keyboard Layout Project: The Hand Roll Keyboard

I greatly increased the cost for inward rolls, and got this beautiful layout:

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

Fitness:       2108634
Distance:      7859.45
Inward rolls:  10.38%
Outward rolls: 4.83%
Same hand:     25.62%
Same finger:   1.21%
Row change:    10.93%
Home jump:     0.46%
To center:     3.45%

It sacrifices on pretty much everything but inward rolls, but still. Those rolls are awesome!

New Keyboard Layout Project: INESRTAO

After toiling with the discovered bug and trying to find an applicable system, I have finally (after about 30 hours, but it feels like forever) come up with a viable layout. It looks unusual, but is actually quite amazing. Finger travel distance is great, same finger is phenomenal, rolls are fun. It places r on the index finger, which is an unusual decision, but it seems to work great.

Hands: 48% 51%
Fingers: 8% 9% 15% 14% 18% 14% 9% 8% 

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

Fitness:       2283981
Distance:      7864.37
Inward rolls:  7.02%
Outward rolls: 4.47%
Same hand:     22.73%
Same finger:   0.67%
Row change:    8.97%
Home jump:     0.33%
To center:     4.16%

New Keyboard Layout Project: This One’s Better

Remember that keyboard I posted earlier today? Well, this one’s better.

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

Fitness:       20.31
Distance:      7921.15
Inward rolls:  7.16%
Outward rolls: 5.25%
Same hand:     21.59%
Same finger:   0.76%
Row change:    8.66%
Home jump:     0.35%
To center:     3.29%

New Keyboard Layout Project: New Results

After fixing the bug, I modified the program and got a rather different (though good) result.

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

Fitness:       20.38
Distance:      7814.03
Inward rolls:  7.59%
Outward rolls: 5.49%
Same hand:     22.26%
Same finger:   0.77%
Row change:    9.10%
Home jump:     0.39%
To center:     3.55%

This layout has nice inward rolls and great same finger and distance. It has pretty low usage of the right middle finger, though, and pretty high usage of the left ring finger. Other than that, though, it’s very nice.

Also, I added a function to my program that shows what the easiest and hardest digraphs are. The theory is that more common digraphs should be easier. For this layout, the easiest digraphs are in, es, te, and ri. The hardest are ‘;, ‘a and uy. You can see why ‘; is so hard: it involves jumping over the home row on the same finger to hit two of the hardest spots.

And here’s the source code, if you want to check it out.

New Keyboard Layout Project: Serious Problem

Uh-oh. I’ve just noticed a huge bug. The inward roll scorer was not working properly. I fixed it, but now it’s getting some unusual results. I am going to have to seriously revamp the scoring system to get the results I want.

Although I did like MTGAP 3.5, it has far fewer inward rolls than I thought. It’s only 4.98% inward rolls, and not 7.66%. In fact, I had inward rolls and outward rolls switched. It’s a nice looking layout, and probably better than version 2.0, but it is certainly not optimal.

Here’s what I mean by “unusual”. This layout looks very strange to me.

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

However, after I examined it, I saw that it is actually very good. It has better distance and same finger than MTGAP 3.5, and MUCH better inward rolls. It does not perform so well on row changing, and it will probably still need tweaking, but it’s very good. Its same finger is even better than Colemak.

I also got this:

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

It scores well overall (and especially well on inward rolls) but does not do so well on same finger. But TH sure looks uncomfortable. I’m going to have to fix that. Phynnboi was right about that.