Happy UnBirthday Ken
Mad Hatter: Now, statistics prove, prove that you’ve one birthday.
March Hare: Imagine, just one birthday every year.
Mad Hatter: Ah, but there are three hundred and sixty four unbirthdays!
March Hare: Precisely why we’re gathered here to cheer.
Ken Regan just had his birthday the other day. Today is another unbirthday.
Please join me in wishing Ken many more happy birthdays as well as many many more unbirthdays.
Ken is a Mathematician
Ken is of course a co-author of this blog. We try to cover computer science and mathematics, but we are open to other areas. Ken started his career in Mathematics; he obtained a PhD in math from Oxford University in 1986. It was under Dominic Welsh and was tilted: On the separation of complexity classes. Welsh’s family tree is here.
Ken is a Programmer
Ken is of course famous for being one of the world’s top chess cheating detectors. Recall to cheat at chess is to use a computer program to make your moves in a game against a human opponent. This is strictly illegal.
Ken was featured on the cover in chess review. His work gets critic review here by David Barnes and Julio Hernandez-Castro in the 2015 article On the limits of engine analysis for cheating detection in chess in the journal Computers and Security.
Ken is Unique
Ken is special in many ways. He is smart, he is a wonderful partner, and he is a great friend. I would claim that he is one of the few people that have the following three properties:
- He is an international master in chess of rating
;
- He is a strong researcher in complexity theory;
- He is a terrific programmer.
The last I would claim is pretty remarkable. There are many strong chess players, there are many of us working in complexity theory. But few have written as much production quality code as Ken has. For his work on chess cheating he has had to write thousands of lines of code. This code must run fast, and be correct. The latter, correctness, is really important. This since his work on detecting cheating has led players to be suspended from chess for years. It also has helped protect players who did not cheat, even though many thought they had.
Open Problems
Again I wish him a wonderful unbirthday day.
Thank you very much, Dick. This surprise happens to fit in well with (chess-)delayed workings on my part including some facts of millennial arithmetic.
Regarding the paper by Barnes and Hernandez-Castro, it more properly describes the initial “screening stage” of my system, not the predictive analytics that go into my full model as described in the AAAI 2011 paper with the late Guy Haworth. It uses the term “false positive” at the level of games and misses how the full model’s results come with confidence intervals that determine its judgments—not to mention the model’s providing various cross-checks that enter consideration under manual review by the International Chess Federation and other bodies that use my work. On its own terms, however, the paper is fine, and Haworth and I decided not to press an objection. Moreover, it induced me to include its “CV” metric (which I had already named EV for “equal-optimal value”) alongside my move-match metric (MM, also called T1-match) in my official test suite. I measure my full model’s version of MM and EV as over 0.96 correlated but having both gives a more effective weighting to the suite.
The authors created software based on their paper which led to a tool called PGN Spy. Neither does full predictive analytics—in particular, neither adequately reflects the element of difficulty of positions in the tested games, accounting for the kinds of positions that players of different styles tend to face. The advice early on the PGN Spy page—“Before using this software to analyse the games of suspected cheaters, it is recommended that you first analyse a large number of games from elite grandmasters. This will give you appropriate baselines for comparison. It is important that your analysis of suspected cheaters is done with the same settings as those for your baselines, or the results cannot be compared meaningfully.”—is insufficient and dangerous, as is the use of the “T2” and “T3” tests without expressly calibrating them as unbiased estimators.
Happy n-day plus birthday Ken.
Another board game: GO, or 围棋 （pronounced WeiQi in Chinese), is also world popular.
Given that there have been numerous programs after AlphaZero that can easily beat human players, how easy it is to structure Ken’s full model into two layers so that the upper layer represents the body of all rules that would apply to a bigger class of games including GO?
My model would indeed carry over directly to Go. The essential needed ingredient is mostly-correct objective values for each move in a given position. The lack of reliable computer evaluations was an obstacle in Go, but now AlphaGo/Zero could provide them. In my article https://rjlipton.wpcomstaging.com/2016/01/21/a-chess-firewall-at-zero/ I made a specific prediction that a strong phenomenon in chess would be absent in Go, owing to the near-total lack of draws.
Nice to know this. Thanks! Just that I have not heard of anti-cheating programs for Go from news.
By the way, the game of Go does allow board repetitions, and hence allow draws in rare special cases.
See here
https://en.wikipedia.org/wiki/Rules_of_Go#Repetition
Ken, you appear in today’s Agadmator video too! (Thanks to playing in a tournament where Gaprindashvili did well.)
Wow, thanks Ryan! Indeed, I have mentioned that tournament in comments to items on Facebook about Gaprindashvili’s defamation suit against The Queen’s Gambit.
Happy birthday, Ken!
I like Ken’s work in Structural complexity.