Ken Turns 40

Ken Regan started his Ph.D. 40 years ago from Oxford, in complexity theory, advised by Dominic Welsh. Ken continues to be a researcher in complexity theory, a teacher of computer science, a mentor of graduate students, a writer of books and more. He has long been on the faculty of the Department of Computer Science and Engineering at Buffalo.

Today I thought I would thank Ken for his many wonderful accomplishments.

Ken is a great friend and long time co-author of mine. We also write this blog together. He has done many things—one colorful thing is the poster. Ken is a strong chess player—a chess International Master just below the grandmaster level and rated at 2372—roughly.

We will highlight his continued work in complexity theory and his work in detecting chess cheating.

Complexity Theory

Ken and I have just released a second edition of our book on quantum algorithms: Introduction to Quantum Algorithms Via Linear Algebra, Second Edition

Quantum computing explained in terms of elementary linear algebra, emphasizing computation and algorithms and requiring no background in physics. This introduction to quantum algorithms is concise but comprehensive, covering many key algorithms. It is mathematically rigorous but requires minimal background and assumes no knowledge of quantum theory or quantum mechanics.

I must add that Ken did the lion share of the work on writing this second edition.

Please note a special offer: Buy one, get another for full price.

In another part of complexity theory, Ken has just had a paper accepted: Multi-Structural Games and Number of Quantifiers with Ronald Fagin, Jonathan Lenchner, and Nikhil Vyas. This will appear at LICS 2021 this summer.

The paper defines a new type of game that captures the number of quantifies needed for certain properties. This is neat—see the paper for details.

Chess Cheating—How?

The area of detecting chess cheating is one that Ken works in. Moreover he is perhaps the leader in the world. That is the leader in detecting when a player cheated at playing chess.

What is this? In games like poker, games that rely on cards, it is long been an issue that people can cheat. Cards can be marked for example. The dealer can try and control what cards a player gets. These are ancient issues for card games.

What is this for chess? The pieces cannot be marked to any advantage: a king is king, a pawn is a pawn and so on. But a player can cheat in a simple manner. They can use the moves of a computer program instead of their own. The problem in chess is that computer programs currently play at a level vastly higher than even a strong player. Stockfish, a top program, plays at around 3551.

Recall Ken is around 2372. That places him via the Elo rating at IM:

• 2500-2700 most Grandmasters (GM)

• 2400-2500 most International Masters (IM) and some Grandmasters (GM)

• 2300-2400 most FIDE Masters (FM) and some International Masters (IM)

• 2200-2300 FIDE Candidate Masters (CM), most national masters

Note: the computer therefore plays much better than all known GM’s.

Chess Cheating—Detecting?

Enter Ken. He has been studying how to detect whether or not a player is using a computer’s moves rather than their own moves. He has worked on this for many years, with good success. Note: this is a real problem:

In one chess tournament, five of the top six were disqualified for cheating. In another, the doting parents of 10-year-old competitors furiously rejected evidence that their darlings were playing at the level of the world No 1.

An obvious idea is to not let a player have access to any computer. This is naive for several reasons:

1. A player can use their cellphone secretly—in the toilet?

2. A player could conceal the computer on themselves—computers are small?

3. A player could be playing chess online—impossible to stop them?

Chess Cheating—How to Detect

This led Ken to consider the following problem: Suppose that some player makes a series of moves during a game. Check how well their moves agree with Stockfish or some other computer program. Then claim the player cheated provided they agree too often with the program.

This sounds simple. Compare the computer’s move and the player’s moves. If these agree too often then say the player has cheated.

Simple. Unfortunately not. There are many complications:

1. In chess sometimes moves are “in book”. Especially at the beginning the best move may be well known.

2. In chess sometimes moves are “forced”. There may be a unique legal move.

3. A player may only use the computer when the position is “hard”.

4. The computer may suggest several moves. These moves may all be about the same quality.

Clearly all these make the problem—did the player cheat—complex. Difficult. A further complicating factor is that even a weak player will sometimes randomly agree with the computer. That is even a weaker player can make a great move.

Perhaps the shock is that Ken has been able to build software that is able to correctly decide when a player cheated or not. His method is good enough that it is used in practice on real players. It has led to actual penalties on players, and has saved others from false claims.

I must add that his software is quite impressive. The test to see if a player cheated involves the running of chess computer programs. These programs like Stockfish were made to be used by one player. They were not designed to be used as a subroutine in an automated search. Perhaps for a complexity theorist Ken might have a top ranking for writing the most real programs.

Open Problems

Correction: Ken is 40th from Princeton as an undergrad. Ken is 35th from Oxford for Ph.D. See Ken on a 40th Reunion for Princeton Class of ’81 panel [Ken: A one-word fix did the trick, changing “obtained” to “started” in the first sentence. It’s a Trans-Pond-er difference: I count as ’81 both at Princeton and Oxford (Merton College) because the latter goes by the starting year. The photo is from Glenveagh Castle, Ireland, on a June 2019 trip with my family.]

Ken says: “The pandemic has brought me as much work in a single day as I have had in a year previously,” said Prof Kenneth Regan, an international chess master and computer scientist whose model is relied on by the sport’s governing body, FIDE, to detect suspicious patterns of play. “It has ruined my sabbatical.”

See this article for more detail on Ken’s work. This is by Howard Goldowsky.