MadChess UCI_LimitStrength Algorithm

[emadsen]

I spent time writing an algorithm to reduce the playing strength of my chess engine. Thought I'd share it here and ask my fellow programmers what they think.

• What do you think of the technique?
  How have you implemented UCI_LimitStrength?

To summarize, playing strength is reduced by...

• Removing positional knowledge.
  Reducing search speed.
  Performing a MultiPV search and selecting a weaker move, within a configurable error range.

ELO calibration is done by interpolating engine parameters between the two personalities that bound the given ELO. Details are on my website. See The MadChess UCI_LimitStrength Algorithm.

[PK]

To cut the long story short, my approach is to prune random moves in the search. This, however, requires some precautions, like different algorithm for out of check moves. Heavily commented code is available here:

https://github.com/nescitus/rodent_code ... /blunder.c

[hgm]

I once proposed to consistently prune moves from the search, to simulate human oversight. So basically make a history table that keeps track of moves that have already occurred in the tree at previous iterations, and then for each new move that appears in the current iteration decide whether you will overlook that move, with a probability that increases with depth. And when you decide to overlook it, mark it as such in the table, and suppress thus marked moves in future move generations (or discard them during move sorting).

[Edmund]

I once proposed to consistently prune moves from the search, to simulate human oversight. So basically make a history table that keeps track of moves that have already occurred in the tree at previous iterations, and then for each new move that appears in the current iteration decide whether you will overlook that move, with a probability that increases with depth. And when you decide to overlook it, mark it as such in the table, and suppress thus marked moves in future move generations (or discard them during move sorting).

Make the decision for pruning a function of the positions hash key and you avoid the history table alltogether.

[Ferdy]

I spent time writing an algorithm to reduce the playing strength of my chess engine. Thought I'd share it here and ask my fellow programmers what they think.

• What do you think of the technique?
  How have you implemented UCI_LimitStrength?

To summarize, playing strength is reduced by...

• Removing positional knowledge.
  Reducing search speed.
  Performing a MultiPV search and selecting a weaker move, within a configurable error range.

ELO calibration is done by interpolating engine parameters between the two personalities that bound the given ELO. Details are on my website. See The MadChess UCI_LimitStrength Algorithm.

Thank you for sharing.
I have questions here, when doing multi-pv (when move/blunder error is greater than 0) do you use the full strength personality? Also do you track or have some control that the engine will not select best moves from every position successively (even though you have blunder percent protection)?

I have tried reducing the strength in my engine too to approximate human play (just trying to match the human player elo), and I use the multi-pv approach, but always using its full strength. I just control what move to play depending on the opponent's move score and a longer successive selection of best move should be controlled. I found out that using weak personality to generate multi-pv will deteriorate engine play move after move, which could no longer approximate human strength play.

Your blunder percent is very nice and I plan to use it when I will be working on elo calibration .

[hgm]

Make the decision for pruning a function of the positions hash key and you avoid the history table alltogether.

That is not what I mean by consistent. It would prune different moves in each node. I want it to prune the same move in the entire tree. When humans overlook a move, they overlook it anywhere.

[jdart]

This is a hard problem in general.

I reduce strength through ply limits, search speed reduction, and by adding some randomness into the eval. At very low strengths this practically amounts to making random moves. In addition I limit the opening book so only very frequent moves are selected, at low strength settings.

IMO it would be better if some positional knowledge were held constant like center control, and king shelter while the more sophisticated stuff was reduced at low strength. Because even beginning players know something about this stuff.

In addition I have had the problem that even at moderate strength levels the program was having problems executing elementary mates (like K + R vs K) due to very low depth in the search. There are various ways to fix this including having recognizers for such endgames (I have some now) or increasing the allowed depth slightly in the endgame.

--Jon

[emadsen]

my approach is to prune random moves in the search

Thanks Pawel. I like the idea of overlooking moves. Seems like a good simulation of human limitations. I was concerned though about making a mess of the hash table. To simulate higher ELO levels I need a coherent hash table so the engine can search deep enough to see tactics. If the engine overlooks random moves, different moves will be overlooked on depth 1, depth 2, depth 3, etc. So scores returned by the hash table are meaningless and will mislead the search- slowing it down. Does the hash score represent searching 30 moves on ply 1, 36 on ply 2... or does it represent searching 28 moves, then 34 moves? Which moves?

I think your approach combined with H.G's may work. I think H.G. is correct to point out the same moves should be overlooked at the same depth as the iterative search progresses. This keeps the hash coherent (for a given ELO level).

Though, I can't see what's wrong with my approach of limiting NPS and selecting a sub-optimal move from a MultiPV search.

[emadsen]

I once proposed to consistently prune moves from the search, to simulate human oversight. So basically make a history table that keeps track of moves that have already occurred in the tree at previous iterations, and then for each new move that appears in the current iteration decide whether you will overlook that move, with a probability that increases with depth. And when you decide to overlook it, mark it as such in the table, and suppress thus marked moves in future move generations (or discard them during move sorting).

I want it to prune the same move in the entire tree. When humans overlook a move, they overlook it anywhere.

I agree. This addresses my concern about hash table coherence. If the same moves always are overlooked, scores from the hash table are valid (for a given ELO).

[Ferdy]

I played a game against a setting with elo 1600, using winboard gui which supports the uci limit strength and uci elo. Here is the game with light personal annotation. TC 10min + 5sec inc.

[pgn][Event "?"]
[Site "UU-PC"]
[Date "2014.04.13"]
[Round "?"]
[White "Me"]
[Black "MadChess 1.4 elo1600"]
[Result "1-0"]
[Annotator "1... -0.37"]
[ECO "E32"]
[TimeControl "600+5"]

1.d4 e6 { -0.37/8 27 } 2.c4 Nf6 { +0.09/7 17 } 3.Nc3 Bb4 { +0.04/8 38 } 4.Qc2
{ (Classic nimzo-indian, white does not allow doubled pawn in case black will exchange Bxc3, just recapture with Qxc3.) }
4...Bd6
{ -0.22/7 30 (Not in my repertoire, probably the idea is to pressure my h2 pawn by playing Ng4 next.) }
5.e4
{ (Normal developing move but threatens to fork a bishop and knight by pawn move to e5.) }
5...Nc6
{ -0.27/7 16 (A strong move from a 1600 elo player, if I play e5? now I probably get refuted by Nxd4 and my queen in c2 has to move somewhere, after which black will capture my now unsupported pawn at e5 by Bxe5.) }
6.Nf3
{ (There's not much time to look deeper a simple developing move is available.) }
6...e5
{ -0.47/6 18 (Nice resource, now my d4 pawn is compromised, If I play 7. Be3, black can play Ng4 attempting to get the 2 bishop advantage. I will not play 7. d5 because black can play Nd4. So I exchange pawn, the black pawn I am exchanging to is a center pawn anyway.) }
7.dxe5 Nxe5 { -0.12/9 32 } 8.Be2 a6 { -0.43/7 20 } 9.O-O Nfg4
{ -0.50/7 31 (This is a nice tactical shot, I spend more time here. Can a 1600 player play this? I say yes. The idea is to weaken my pawn structure by say 10. h3 Nxf3 11. Bxf3 Nh2 12. Re1 Nxf3 13. gxf3 and I got a doubled pawn.) }
10.Bf4 Nxf3+ { +0.17/7 18 } 11.Bxf3 Bxf4 { -0.02/9 16 } 12.Bxg4
{ (The point of my Bf4, I get his dangerous g4 knight.) } 12...Qg5
{ -0.11/8 30 } 13.Bf3 O-O { -0.15/7 19 } 14.Rad1 c6 { +0.33/7 28 } 15.g3 Re8
{ -0.22/7 26 } 16.Bg2 Bc7 { +0.27/7 11 } 17.Qd3
{ (Protects the c4 pawn, since I am planning to play pawn to f4 dominating the center. Black has check on Qc5 if I play f4 immediately.) }
17...d6 { +0.46/6 15 (Good for me, the dangerous bishop is blocked.) } 18.f4
Qc5+ { +0.85/6 10 } 19.Kh1 Be6 { +0.80/7 16 } 20.b3 Qh5 { +0.67/6 13 } 21.f5
{ (I don't allow Bh3 from Black.) } 21...Bc8 { +0.37/7 14 } 22.Ne2
{ (Re-positioning the knight since the d5 sq is no longer accessible.) }
22...Qg5 { +0.40/6 16 } 23.Bf3 a5 { +0.49/6 13 } 24.h4 Qh6 { +0.40/7 18 }
25.Kg2 Kh8 { +0.33/6 17 } 26.Rh1 b6 { +0.28/5 9 } 27.g4 f6 { -0.03/7 12 }
28.Qd2
{ (It is difficult to make progress now when black's queen is in control of my dark squares.) }
28...Qxd2 { -0.03/8 10 } 29.Rxd2 Bd7 { -0.02/7 17 } 30.g5 Kg8 { -0.09/6 11 }
31.Rhd1 b5 { -0.17/6 13 } 32.Ng3
{ (Planning to attack the f6 by playing Nh5.) } 32...bxc4 { +0.06/6 13 }
33.bxc4 fxg5 { -0.25/6 14 } 34.hxg5 Rac8 { -0.59/7 13 } 35.Rb1 c5
{ -0.15/7 12 } 36.Rdb2 Ba4 { +0.04/6 8 } 37.Rb7 Re5 { +0.22/6 7 } 38.R1b2 Be8
{ +0.19/7 11 } 39.Ra7 a4 { +0.00/7 15 } 40.Rbb7
{ (I am now in time pressure with less than a minute in my clock.) } 40...Re7
{ -1.85/9 11 } 41.f6 Rf7 { -2.06/8 9 } 42.Bg4 Bb8
{ -2.55/8 10 (Computer is giving me an exercise in time pressure.) } 43.Rxf7
{ (I guess I found the best exchange sequence in time pressure.) } 43...Bxf7
{ -3.37/10 13 } 44.Rxf7 Kxf7 { -2.35/10 6 } 45.Bxc8
{ (After the complication, I can now handle this even with less time.) }
45...gxf6 { -2.20/10 7 } 46.gxf6 Kxf6 { -2.27/10 14 } 47.Kf3 Bc7
{ -2.43/9 8 } 48.Ne2 { (Prevents Black's king access to d4 sq.) } 48...Ke5
{ -2.64/8 9 } 49.a3 Bb6 { -2.99/8 5 } 50.Bd7 Bd8 { -3.06/8 6 } 51.Bxa4 h5
{ -3.19/8 6 } 52.Bd7 Kf6 { -3.28/9 9 } 53.a4 Ke5 { -3.28/8 6 } 54.Be8 h4
{ -3.23/11 10 } 55.Bd7 Bb6 { -3.23/9 4 } 56.Bf5 Ba5 { -3.43/10 9 } 57.Kg4 Bb6
{ -4.75/9 8 } 58.Kxh4 Bd8+ { -4.92/9 5 } 59.Kg4 Be7 { -5.53/9 5 } 60.a5 Bd8
{ -6.76/10 5 } 61.a6 Bb6 { -7.15/10 4 } 62.Kf3 Kf6 { -7.57/10 5 } 63.Ke3 Ba7
{ -7.27/9 10 } 64.Kd3 Kf7 { -7.67/10 11 } 65.Kc3 Ke7 { -6.46/8 6 } 66.Kb3 Kd8
{ -5.89/9 9 } 67.Ka4 Bb8 { -6.94/10 9 } 68.Kb5 Kc7 { -8.24/10 3 } 69.Nc3 d5
{ -10.64/11 9 } 70.Nxd5+ Kd6 { -15.87/10 8 } 71.Kb6 Ke5 { -17.99/10 3 }
72.Kb7 Bd6 { -18.86/10 9 } 73.a7 Kd4 { -28.08/10 8 } 74.Nb6 Ke5
{ -16.39/7 6 } 75.a8=Q Kf4 { -19.60/8 4 } 76.Qe8 Ke3 { -20.37/8 4 } 77.Nc8
Bg3 { -16.98/7 3 } 78.e5 Bh2 { -17.09/7 8 } 79.e6 Bf4 { -20.69/6 8 } 80.Qh5
Bg3 { -24.13/7 4 } 81.Qg4 Be1 { -29.49/8 8 } 82.Qe4+ Kf2 { -29.37/8 5 } 83.e7
Ba5 { -29.37/6 3 } 84.e8=Q Bd2 { -99.94/6 4 } 85.Qe2+ Kg1 { -99.96/6 4 }
86.Qg6+ Kh1 { -99.98/6 4 } 87.Be4# { Xboard adjudication: Checkmate } 1-0[/pgn]

Another thing to consider is time pressure, let the computer get weaker when time is low, I don't know how low is this but it should be factored in, perhaps just increase the blunder percent.