skill levels

[brtzsnr]

One of the feature requests I received was to implement skill levels in Zurichess. A 2500 Elo engine is too strong for most humans so in order to be useful for playing games the engine needs to lower its strength.

How can I implement skill levels? I have several ideas.

1) Implement multi-pv, order the moves and choose a weaker one. This, I think, is implemented by Stockfish. A bit harder to do but gives you multi-pv.
2) Increase LMR at root by random(Skill Level). Easy to implement and will not miss obvious tactics.
3) Disable check extension / passed pawns / king safety. Get's complicated because I need to map different combinations to the skill level.

Any other ideas with pros and cons?

[PK]

Currently I'm doing the combination of slowdown (forcing the engine to play with low nodes per second) and adding pseudo-random value to evaluation function (pseudo-random, because it is derived from hash key and therefore the value is connected to the position). I learned this approach from Crafty. The obvious benefit is that strength of weakened personalities is the same on every machine. The downside is that You have two parameters to tune instead of one. Rodent with NPS 1000 and evaluation blur 100 (which means the random component is between -50 to 50) still performs somewhere in 1600-1800 Elo range. NPS 100 and EvalBlur 100 is a beginner that can hang pieces. NPS 32000 with no blur performed at about 2400 Elo.

In the past, I had elaborate Blunder function, deciding which moves will not be searched. This approach needed a lot of tweaking (like not blundering while in check, not blundering on recaptures etc.) and still led to unrealistic moves at about 1600 Elo.

[Ajedrecista]

Hello Alexandru:

One of the feature requests I received was to implement skill levels in Zurichess. A 2500 Elo engine is too strong for most humans so in order to be useful for playing games the engine needs to lower its strength.

How can I implement skill levels? I have several ideas.

1) Implement multi-pv, order the moves and choose a weaker one. This, I think, is implemented by Stockfish. A bit harder to do but gives you multi-pv.
2) Increase LMR at root by random(Skill Level). Easy to implement and will not miss obvious tactics.
3) Disable check extension / passed pawns / king safety. Get's complicated because I need to map different combinations to the skill level.

Any other ideas with pros and cons?

In your first suggestion, there could be extreme positions where not chosing the best move is horrible:

[pgn]1. e4 e5 2. Bc4 Nf6 3. d4 c6 4. dxe5 Nxe4 5. Ne2 Nxf2 6. O-O Nxd1[/pgn]

Multi-PV = 7 of SF 7:

Code: Select all

19/39	01:08	  23.005.573	337.845	-11,30	h2h3 d7d5 Rf1xd1 Qd8b6+ Ne2d4 d5xc4 Nb1c3 Nb8d7 Bc1f4 Bf8c5 Bf4e3 Qb6c7 Kg1h1 Qc7xe5 Rd1e1 OO Ra1d1 Qe5h5 Nd4f3 Qh5f5 Nf3d4 Qf5g6 Be3f4 Qg6h5 Nd4f3
19/39	01:08	  23.005.573	337.845	-10,65	g2g3 Bf8c5+ Kg1g2 Nd1f2 Rf1xf2 Bc5xf2 Kg2xf2 f7f6 e5e6 d7d5 Bc4d3 Bc8xe6 Bc1e3 OO Kf2g2 Rf8e8 Be3f2 d5d4 Nb1d2 c6c5 Bd3b5 Be6d5+ Kg2g1 Bd5c6 Bb5c4+ Kg8h8 Ne2f4 Nb8d7 Nf4e6 Qd8b6
19/39	01:08	  23.005.573	337.845	-8,93	c2c3 Qd8b6+ Ne2d4 Nd1xb2 Bc4xf7+ Ke8d8 Nb1d2 Nb2d3 Nd2c4 Qb6a6 Bc1g5+ Kd8c7 a2a4 b7b6 Bg5h4 Bf8c5 Bh4g3 Kc7b7 a4a5 b6b5 Nc4d6+ Bc5xd6 e5xd6 Rh8f8 Ra1d1 Nd3c5 Bg3e5
19/39	01:08	  23.005.573	337.845	-8,29	Rf1xd1 Qd8h4 Bc4d3 d7d5 Bc1f4 Bc8g4 Bf4g3 Bf8c5+ Kg1h1 Qh4h5 Rd1e1 OO c2c4 d5xc4 Ne2f4 Qh5h6 Bd3xc4 Rf8e8 Nb1c3 Nb8d7
19/39	01:08	  23.005.573	337.845	-8,05	Kg1h1 Bf8c5 Rf1xd1 Qd8h4 Ne2f4 d7d5 e5xd6/ep Bc5xd6 g2g3 Qh4e7 Nb1c3 OO Bc1d2 Nb8d7 Rd1f1 Nd7e5 Ra1e1 b7b5 Bc4b3 Bc8g4 Nf4d3 Ra8e8 Nd3xe5 Bd6xe5 Bd2f4
19/39	01:08	  23.005.573	337.845	-7,77	Ne2d4 d7d5 e5xd6/ep Bc8e6 Bc4xe6 f7xe6 Rf1xd1 Bf8xd6 Nb1c3 Bd6c5 Bc1e3 e6e5 Nd4f5 Bc5xe3+ Nf5xe3 Qd8b6 Rd1e1 OO Ra1b1 Qb6b4 h2h3 Nb8d7 Re1d1 Nd7c5 Kg1h1 Qb4f4 Ne3g4 Nc5e4
19/39	01:08	  23.005.573	337.845	+M2	Bc4xf7+ Ke8e7 Bc1g5+

What would the modified Zurichess play? Specially if you have skills level from 0 (the weaker, even a random mover) to N (the strongest available) and you are playing against (N - 1) skill level. I think that you must do a choice algorithm that takes into account eval(move_i) - eval(best move). FWIW, SF 7 with skill level = 0 (it can be chosen from 0 t 20) plays Bxf7+, which is the best move in this special position.

Other examples are immediate recaptures with no mate threats. Your second suggestion does not miss obvious tactics like my example position, according to your explanation. I do not know if a combination of 1) and 2) would work, but I think that in case 1) chosing always (the important word here is always) the second or third best move is not realistic. Why a player like me (unrated, but I think that I would be rated less than 1800 FIDE) can not play the best moves sometimes?

What about the following?

Code: Select all

Imagine a position where the evals of all the possible moves from the side to move are:

(In pawns): d(i) = eval(i) - eval(best move) = {0, -0.1, -0.2, -0.2, -0.6, -2.9, -4, -4, -4, -9}

Prob(i) = 10^[d(i)/K]/SUM{10^[d(i)/K]}, with K > 0

// i = 1, 2, ..., moves - 1, moves; with moves = perft(1) of the position

F(0) = 0
F&#40;i&#41; = Prob&#40;i&#41; + SUM&#91;Prob&#40;j&#41;&#93;, with j < i
// Of course&#58; F&#40;moves&#41; = 1

Get r = a random number from a PRNG.

if &#91;F&#40;i-1&#41; < r =< F&#40;i&#41;&#93; then
  pick move i
end if

/*
Choose wisely. If I am right&#58;
0 < r =< 1 ==> condition&#58; F&#40;i-1&#41; < r =< F&#40;i&#41;
0 =< r < 1 ==> condition&#58; F&#40;i-1&#41; =< r < F&#40;i&#41;
*/

I have written in basis 10 but you can choose e or whatever you want. The key would be K = K(skill level): lower level <--> higher K, and viceversa. The hard thing is tune K with different d(i) and number of moves. In my example:

Code: Select all

Rounding up to 1e-4:

-----------------------------

K = 1, basis 10:

Move   d(i)    P(i)     F(i)
  1     0.0   0.3276   0.3276
  2    -0.1   0.2457   0.5732
  3    -0.2   0.1842   0.7574
  4    -0.2   0.1842   0.9417
  5    -0.6   0.0583   0.9999
  6    -2.9   0.0001   1.0000
  7    -4.0   0.0000   1.0000
  8    -4.0   0.0000   1.0000
  9    -4.0   0.0000   1.0000
 10    -9.0   0.0000   1.0000

-----------------------------

K = 4, basis 10:

Move   d(i)    P(i)     F(i)
  1     0.0   0.2029   0.2029
  2    -0.1   0.1916   0.3945
  3    -0.2   0.1808   0.5753
  4    -0.2   0.1808   0.7561
  5    -0.6   0.1436   0.8998
  6    -2.9   0.0382   0.9380
  7    -4.0   0.0203   0.9583
  8    -4.0   0.0203   0.9786
  9    -4.0   0.0203   0.9989
 10    -9.0   0.0011   1.0000

-----------------------------

K = 0.5, basis 10:

Move   d(i)    P(i)     F(i)
  1     0.0   0.4016   0.4016
  2    -0.1   0.2534   0.6549
  3    -0.2   0.1599   0.8148
  4    -0.2   0.1599   0.9747
  5    -0.6   0.0253   1.0000
  6    -2.9   0.0000   1.0000
  7    -4.0   0.0000   1.0000
  8    -4.0   0.0000   1.0000
  9    -4.0   0.0000   1.0000
 10    -9.0   0.0000   1.0000

K --> 0+ would lead to F(0) = 0, F(1) --> 1-, so the best move (move 1) would be picked almost for sure (the highest possible skill level with your eval function).
K --> + infinity would lead to F(0) = 0, F(i) ~ i/moves, that is, a random mover (the lowest possible skill level with your eval function).

Regards from Spain.

Ajedrecista.

[yurikvelo]

There are 2 approaches:
- at each move play suboptimal moves. Limit calculating resources: time, CPU usage, depth, disable some features (Null, LMR, Hash etc). Engine select best move of searched, but because resources and techniques were limited - this best moves are suboptimal.

- play/analyze at full strength using all possible techniques and resources (as in engine tournament) and inform as correct evaluation as possible, but behave as human IM - randomly deep blunder.


I like second approach better
I would define sets of human like skills. E.g. "Master level": 5% probability -2.5 blunder, 10% probability -0.5 blunder etc.

Than implement counter of intentionnaly made mistakes and random dice roller. All moves play at full strength, but when random generator says: "it is time to make -3.0 blunder" engine run multiPV=20 and select line which is at least 3 points below best line.
Increment mistake-counter and prevent too frequent mistakes (e.g. not more than 2 -3.0 mistakes in first 40 moves if probability set to 5%)

If there is no such move (e.g. even last is not -3.0, or even 2nd is -5) than skip "blunder" and do not increment counter.


With traditional 1st approach all moves are still strong, no obvious mistakes. Game is like arm-wrestling or rope pulling - you have to slowly progress advantage, combined of minor subotimal engine moves. It is slow positional progress. More like GM-games.

With second approach game will be more tactical - human have to identify mistake was actually made and make a plan how to convert it. It is more like Master and weaker ranked games look like.

[cdani]

Another idea is for example make it bad defender, disabling king safety stuff. People can have fun trying to win by attack.

[jdart]

I both slowdown the search and randomly choose a suboptimal move (at low skill levels).

UCI actually has a standard UCI_Elo option that is supposed to set the strength in ELO units. So ideally you should try to scale so that this is at least remotely close. I think the best way to do this is to play a match against an engine of the strength you are targeting and try to set it so UCI_ELO = 2200 for example matches a 2200 engine.

For very low strengths I think random blunder is actually a good feature. Real human chessplayers blunder all the time. Even GMs do it but amateurs do it a lot.

To implement this I do "easy move" detection at low search depths, so I actually have scores for all the moves. Then I randomly choose a suboptimal move - how often depends on the strength, and I also weight the choice so that there is less chance of making a really big blunder (very low score).

I also limit the opening book to less depth at lower strength (but only in Winboard mode, where I have control over that).

--Jon

[brtzsnr]

One of the feature requests I received was to implement skill levels in Zurichess. A 2500 Elo engine is too strong for most humans so in order to be useful for playing games the engine needs to lower its strength.

How can I implement skill levels? I have several ideas.

1) Implement multi-pv, order the moves and choose a weaker one. This, I think, is implemented by Stockfish. A bit harder to do but gives you multi-pv.
2) Increase LMR at root by random(Skill Level). Easy to implement and will not miss obvious tactics.
3) Disable check extension / passed pawns / king safety. Get's complicated because I need to map different combinations to the skill level.

Any other ideas with pros and cons?

short update:
2) Increasing LMR didn't work that well. It at most dropped the Elo by 200.
3) A bit too complicated and some interesting surprizes: disable check extension beats a tournament of 8 versions of Zurichess.

I'm left with multi-pv. I think that's a fair choice given that I wanted to have multi-pv at some point anyhow.

[hgm]

3) A bit too complicated and some interesting surprizes: disable check extension beats a tournament of 8 versions of Zurichess.

I had asimilar experience with micro-Max: the check extension made it weaker. It turned out it was mainly damaging in the end-game. When I only applied a check extension in the middle-game (i.e. when the King-Safety term is still switched on, in micro-Max mainly a penalty on King moves), it was still a winner.

I also limit the opening book to less depth at lower strength (but only in Winboard mode, where I have control over that).

Wouldn't UCI give you exactly as much control over book use as CECP? It is true that switching off the engine's own book is a standard option in UCI, but you are not obliged to implement it. And anyway it would make more sense to have that option in WB mode too.

It seems to me that engines are always in full control how they handle their own book, and never whether the GUI handles the book, in UCI and WB mode alike.

[Ferdy]

One of the feature requests I received was to implement skill levels in Zurichess. A 2500 Elo engine is too strong for most humans so in order to be useful for playing games the engine needs to lower its strength.

How can I implement skill levels? I have several ideas.

1) Implement multi-pv, order the moves and choose a weaker one. This, I think, is implemented by Stockfish. A bit harder to do but gives you multi-pv.
2) Increase LMR at root by random(Skill Level). Easy to implement and will not miss obvious tactics.
3) Disable check extension / passed pawns / king safety. Get's complicated because I need to map different combinations to the skill level.

Any other ideas with pros and cons?

short update:
2) Increasing LMR didn't work that well. It at most dropped the Elo by 200.
3) A bit too complicated and some interesting surprizes: disable check extension beats a tournament of 8 versions of Zurichess.

I'm left with multi-pv. I think that's a fair choice given that I wanted to have multi-pv at some point anyhow.

Deuterium Engine_LimitStrength is mainly based on multipv. But there are other things that are considered such as the score of first pv, and the score difference between the first pv and second pv and so on.
Division of rating range (RR) is applied for different blunder percentage (BP).
RR1: 2450 - 2500, BP1: 3, MPV1: 5
RR2: 2400 - 2449, BP2: 6, MPV2: 7
and so on.

BP could be tuned.
MultiPv value (MPV) can also be tuned, at lower RR the MPV would be increased.

When done you may test your engine with some engines capable of adjusting elo, there could be new engines that are capable too.
http://www.talkchess.com/forum/viewtopi ... ew=threads

[Henk]

Implement minimax and winning from a chess engine becomes easy.