Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible? I've found that limiting the number of nodes isn't working very well.
Also, what'd be the best way to tune the parameters?
Reducing Strength
Moderators: hgm, Rebel, chrisw
-
- Posts: 454
- Joined: Mon Nov 01, 2010 6:55 am
- Full name: Ted Wong
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Reducing Strength
1) weaken the evaluation
a) Add a random factor to the value returned by the evaluation function. You should chose a distribution that on average returns the true value.
b) Remove knowledge
2) weaken the search
a) with a certain probability don't continue the search but fail high/low depending on the side the engine is playing and the current side to move.
b) bias certain moves (e.g. always add a bonus of 10 to the evaluation of any king-move)
You will find that 1.a) becomes increasingly useless for higher depths.
Note: any random choices you take should be deterministic. This ensures that a certain position is weakened exactly the same way at every iteration and is necessary for a stable search. A possible way to achieve that is through basing any random values used on the hash value of the position.
Regarding parameter-optimization, the latest state of the art is Rémi Coulom's great program CLOP.
a) Add a random factor to the value returned by the evaluation function. You should chose a distribution that on average returns the true value.
b) Remove knowledge
2) weaken the search
a) with a certain probability don't continue the search but fail high/low depending on the side the engine is playing and the current side to move.
b) bias certain moves (e.g. always add a bonus of 10 to the evaluation of any king-move)
You will find that 1.a) becomes increasingly useless for higher depths.
Note: any random choices you take should be deterministic. This ensures that a certain position is weakened exactly the same way at every iteration and is necessary for a stable search. A possible way to achieve that is through basing any random values used on the hash value of the position.
Regarding parameter-optimization, the latest state of the art is Rémi Coulom's great program CLOP.
-
- Posts: 454
- Joined: Mon Nov 01, 2010 6:55 am
- Full name: Ted Wong
Re: Reducing Strength
It's a bit vague. Any concrete examples such as source code or like articles?
-
- Posts: 893
- Joined: Mon Jan 15, 2007 11:23 am
- Location: Warsza
Re: Reducing Strength
We have implemented the stuff Edmund described in Glass and it works reasonably well, except that it doesn't scale with time control. Thus, an engine that performs as about 2000 Elo at blitz feels like 1800 in a longer game.
Edmund is right that it's better to get pseudorandom values from position hash ( randomPercentage = hashKey % 100 rather than randomPercentage = rand() % 100 )
later You can code something like
for all moves
{
if ( randomPercentage < errorPercentage
&& ply > canErrFromPly ) newScore = alpha;
else newScore = Search(...)
}
be sure, though, that engine actually tries at least one legal move, otherwhise You might get a false mate score.
Another useful thing is slowing the engine down - humans tend to move faster when an engine replies instantly, and thus they play much weaker chess. Also, the algorithm described here results in engine reporting intimidating (if fake) depth, which looks plain ugly without a slowdown.
You might also want to look at the Phalanx source code - it also has a routine that allows forgetting about certain moves during search, depending on the move properties (for example longer moves and backward moves tend to be omitted more often)
Edmund is right that it's better to get pseudorandom values from position hash ( randomPercentage = hashKey % 100 rather than randomPercentage = rand() % 100 )
later You can code something like
for all moves
{
if ( randomPercentage < errorPercentage
&& ply > canErrFromPly ) newScore = alpha;
else newScore = Search(...)
}
be sure, though, that engine actually tries at least one legal move, otherwhise You might get a false mate score.
Another useful thing is slowing the engine down - humans tend to move faster when an engine replies instantly, and thus they play much weaker chess. Also, the algorithm described here results in engine reporting intimidating (if fake) depth, which looks plain ugly without a slowdown.
You might also want to look at the Phalanx source code - it also has a routine that allows forgetting about certain moves during search, depending on the move properties (for example longer moves and backward moves tend to be omitted more often)
Pawel Koziol
http://www.pkoziol.cal24.pl/rodent/rodent.htm
http://www.pkoziol.cal24.pl/rodent/rodent.htm
-
- Posts: 454
- Joined: Mon Nov 01, 2010 6:55 am
- Full name: Ted Wong
Re: Reducing Strength
Would that be possible to distribute a copy of the source for Glass? Reducing strength is one last thing I can't seem to do properly before my initial release.
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Reducing Strength
I am planning to implement also this feature, what I have in mind is simply to generate multipv, sort it and you may choose the moves depending on the pv score. Sample 30 pv, +0.69 f2-f4 is best and -1.06 Nd4-e2 is worst. If you want the user to equalize use, 0.00 Nb1-d2.kinderchocolate wrote:Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible? I've found that limiting the number of nodes isn't working very well.
Also, what'd be the best way to tune the parameters?
If you want to scale the strength probably choose the moves based on the pv score. Scaling is better if you are able to reach higher depths in your multipv. The pv's below are from a search of 14 plies.
[d]r1bqk1nr/pppp1ppp/8/2b1n3/3NP3/4B3/PPP2PPP/RN1QKB1R w KQkq - 3 6
Code: Select all
14 03:32 147,115,522 690,978 -1.06 Nd4-e2 Bc5xe3 f2xe3 Ng8-f6 Ne2-g3 d7-d6 Bf1-e2 O-O O-O Nf6-g4 Be2xg4 Ne5xg4 Qd1-d4 Qd8-h4 h2-h3 Ng4-e5
14 03:32 142,520,806 690,180 -0.75 g2-g3 Ng8-f6 Bf1-e2 d7-d6 Nb1-c3 Bc8-h3 Be2-f1 Bh3-g4 Bf1-b5+ Ke8-f8 Bb5-e2 Bg4-h3 Be3-g5 Kf8-g8 Nc3-d5
14 03:32 140,484,939 689,489 -0.64 Nd4-b5 Bc5xe3 f2xe3 Ng8-f6 Bf1-e2 a7-a6 Nb5-c3 O-O O-O d7-d6 Nb1-d2 Bc8-e6 Nd2-f3 Nf6-g4 Nf3xe5 Ng4xe5
14 03:32 143,047,626 690,231 -0.64 Rh1-g1 Ng8-f6 Nb1-c3 Nf6-g4 Be3-f4 O-O Bf1-e2 Ne5-g6 Bf4-g3 Ng4-e5 Nc3-d5 d7-d6 Nd4-b3 Bc5-b6 Nd5xb6 a7xb6
14 03:32 141,339,175 689,826 -0.62 Qd1-h5 d7-d6 Qh5-e2 Ng8-f6 Nb1-c3 O-O O-O-O Nf6-g4 Kc1-b1 Ng4xe3 Qe2xe3 Bc8-d7 Bf1-e2 c7-c6 h2-h4
14 03:32 138,950,767 689,243 -0.61 a2-a3 Ng8-f6 Bf1-e2 Nf6xe4 O-O O-O Nb1-d2 Ne4xd2 Qd1xd2 Rf8-e8 b2-b4 Bc5-b6 Rf1-e1 d7-d6 c2-c3
14 03:32 131,094,466 688,246 -0.47 Be3-c1 Ng8-f6 Nb1-c3 Bc5-b4 Nd4-f3 Ne5xf3+ Qd1xf3 O-O Bf1-d3 Bb4xc3+ b2xc3 d7-d5 O-O d5xe4
14 03:32 127,711,527 688,297 -0.39 Qd1-c1 Ng8-f6 Nb1-c3 O-O Bf1-e2 d7-d5 e4xd5 Nf6xd5 O-O Nd5xe3 f2xe3 Kg8-h8 Rf1-d1 Bc5-d6 Nc3-e4 Bd6-b4
14 03:32 126,819,862 688,179 -0.37 h2-h4 Ng8-f6 f2-f3 O-O Nb1-c3 d7-d6 Bf1-e2 Qd8-e7 O-O Bc8-d7 Kg1-h2 a7-a6 Qd1-d2 Bd7-e6 Nd4xe6 Bc5xe3
14 03:32 144,362,633 690,700 -0.33 b2-b3 Ng8-f6 f2-f3 O-O Bf1-e2 d7-d5 Nd4-c6 Ne5xc6 Be3xc5 Rf8-e8 O-O d5xe4 Nb1-c3 Bc8-f5 f3xe4 Bf5xe4 Nc3xe4 Re8xe4
14 03:32 122,379,845 687,299 -0.33 a2-a4 Ng8-f6 f2-f3 O-O Nb1-c3 d7-d6 Bf1-e2 c7-c6 O-O Qd8-b6 b2-b3 Bc8-e6 Kg1-h1 Rf8-e8
14 03:32 133,017,454 688,638 -0.30 c2-c4 Ng8-f6 f2-f3 d7-d6 Bf1-e2 O-O Nb1-c3 Bc5xd4 Be3xd4 Bc8-e6 Qd1-b3 c7-c5 Bd4xe5 d6xe5 O-O Qd8-c7
14 03:32 118,162,108 686,589 -0.29 h2-h3 Ng8-f6 Nb1-c3 O-O f2-f4 Ne5-g6 Nd4-c6 b7xc6 Be3xc5 d7-d6 Bc5-e3 Rf8-e8 Bf1-d3 Ra8-b8
14 03:32 136,034,251 688,903 -0.27 Nb1-a3 Ng8-f6 Na3-c4 Ne5-g4 e4-e5 Ng4xe3 Nc4xe3 Nf6-e4 c2-c3 O-O Bf1-d3 d7-d5 O-O Rf8-e8 Bd3xe4 d5xe4
14 03:32 108,754,456 685,490 -0.22 b2-b4 Bc5xb4+ c2-c3 Bb4-e7 Nd4-f5 Ng8-f6 Nf5xg7+ Ke8-f8 Be3-h6 Kf8-g8 Ng7-f5 d7-d5 Nf5xe7+
14 03:32 100,081,793 684,685 -0.21 Be3-f4 Ne5-g6 Bf4-e3 Ng8-f6 Bf1-d3 Ng6-e5 Nd4-c6 b7xc6 Be3xc5 d7-d6 Bc5-d4 Ne5xd3+ Qd1xd3 O-O O-O Bc8-e6
14 03:32 98,085,328 684,465 -0.21 c2-c3 Ng8-f6 Nb1-d2 d7-d5 Bf1-b5+ c7-c6 Bb5-e2 Nf6-g4 O-O O-O Be3-f4 Qd8-f6 Bf4-g3 Bc8-d7 f2-f4
14 03:32 101,842,157 684,740 -0.14 Qd1-e2 Ng8-f6 Nb1-c3 d7-d6 O-O-O O-O Kc1-b1 Bc8-d7 f2-f3 a7-a5 Qe2-f2 c7-c6 Bf1-e2 b7-b5
14 03:32 97,157,363 684,245 -0.04 Bf1-d3 Ng8-f6 Nd4-c6 b7xc6 Be3xc5 d7-d6 Bc5-d4 Ra8-b8 O-O O-O Nb1-d2 Bc8-g4 Qd1-c1 Ne5xd3 c2xd3
14 03:32 94,689,886 684,313 -0.03 Bf1-b5 Ng8-f6 O-O O-O Nb1-c3 d7-d6 Qd1-d2 Bc8-d7 Bb5-e2 c7-c6 a2-a3 Nf6-g4 Be3-g5 Qd8-c7
14 03:32 115,908,711 686,630 -0.02 Qd1-d2 Ng8-f6 Nb1-c3 Nf6-g4 Be3-f4 O-O O-O-O Ne5-d3+ Bf1xd3 Bc5xd4 Nc3-b5 Bd4-b6 Bf4-g5 f7-f6 Bd3-c4+ Kg8-h8
14 03:32 77,371,544 685,043 0.00 Nb1-d2 Ng8-f6 Bf1-e2 d7-d6 O-O O-O c2-c3 a7-a5 h2-h3 Bc8-d7 f2-f4 Ne5-c6 Kg1-h2 Nc6xd4 Be3xd4 Bc5xd4 c3xd4
14 03:32 85,379,151 685,583 +0.01 f2-f3 Ng8-f6 Bf1-e2 O-O Nb1-c3 d7-d6 O-O a7-a6 Qd1-e1 Bc8-d7 Kg1-h1 Qd8-e7 Qe1-g3 Kg8-h8
14 03:32 78,795,428 685,433 +0.03 Nd4-f3 Bc5xe3 f2xe3 Ne5xf3+ Qd1xf3 Qd8-h4+ g2-g3 Qh4-f6 Qf3xf6 Ng8xf6 Nb1-c3 O-O Nc3-b5 c7-c6 Nb5-d6 Nf6-g4
14 03:32 81,475,369 685,669 +0.11 Nd4-f5 Bc5xe3 Nf5xe3 Ng8-f6 Bf1-e2 O-O O-O d7-d6 Nb1-c3 Bc8-e6 f2-f4 Ne5-c6 Qd1-d2 Qd8-e7 Kg1-h1
14 03:32 71,829,506 685,186 +0.13 Nb1-c3 Ng8-f6 Bf1-e2 d7-d6 O-O O-O h2-h3 a7-a6 Qd1-d2 Bc5-b4 Be3-g5 Bc8-d7 f2-f4 Ne5-c6
14 03:32 91,711,569 684,869 +0.15 Nd4-c6 Ne5xc6 Be3xc5 d7-d6 Bc5-a3 Ng8-f6 Bf1-d3 O-O O-O Bc8-e6 Nb1-c3 Nc6-e5 Bd3-b5 Qd8-e7
14 03:32 75,278,351 685,245 +0.18 Bf1-e2 Ng8-f6 O-O d7-d6 Nb1-c3 O-O h2-h3 Bc8-d7 f2-f4 Ne5-c6 Kg1-h2 Nc6xd4 Be3xd4 Bd7-e6 Qd1-d2 Bc5xd4 Qd2xd4
14 03:32 89,353,657 684,812 +0.33 Nd4-e6 Bc5-b4+ c2-c3 f7xe6 c3xb4 Ng8-f6 Bf1-e2 O-O Nb1-c3 a7-a5 b4xa5 Ra8xa5 O-O Kg8-h8 f2-f4 Ne5-c6
14 03:32 67,132,666 685,139 +0.69 f2-f4 Ne5-g6 Nb1-c3 d7-d6 Bf1-b5+ c7-c6 Bb5-a4 Ng8-e7 O-O O-O Kg1-h1 Bc8-d7 Ba4-b3 Qd8-b6 a2-a3
-
- Posts: 1471
- Joined: Tue Mar 16, 2010 12:00 am
Re: Reducing Strength
Houdini 2 uses the following techniques:kinderchocolate wrote:Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible? I've found that limiting the number of nodes isn't working very well.
Also, what'd be the best way to tune the parameters?
1) Limit the number of positions searched - this reduces mostly the tactical strength of the engine and makes the behavior independent of time control or hardware.
2) Run a hidden multi-PV analysis and purposely pick a move the engine knows is not optimal - this reduces mostly the positional strength of the engine.
This idea comes from Stockfish.
The combination of the two produces a game with both tactical and positional flaws, making Houdini 2 play human-like even at low strength levels.
Here's a reaction I got from a user: "I've played a couple of games against it and am impressed with it's play. It seems more "human" than most other programs I've played. I didn't really notice any dumb computer moves that other programs make when playing at reduced levels. It really felt like I was playing another person down at the local chess club. Now I just need to find a level that's appropriate for me."
Robert
-
- Posts: 6993
- Joined: Thu Aug 18, 2011 12:04 pm
Re: Reducing Strength
A couple of ideas I have used.
1. Cripple the piece values. If a queen has a similar value as a pawn then even a beginner makes a chance to win. Disadvantage: it still will find mates.
2. Force pawns to move by giving it a (random) bonus at the root.
3. A more advanced technique (I called it Club Player) is to give a random bonus / penalty for all root moves in such a way it only occasionally makes a blunder, just like most of us poor chess players like to do.
1. Cripple the piece values. If a queen has a similar value as a pawn then even a beginner makes a chance to win. Disadvantage: it still will find mates.
2. Force pawns to move by giving it a (random) bonus at the root.
3. A more advanced technique (I called it Club Player) is to give a random bonus / penalty for all root moves in such a way it only occasionally makes a blunder, just like most of us poor chess players like to do.
-
- Posts: 98
- Joined: Tue Jul 26, 2011 12:18 am
- Location: London
Re: Reducing Strength
Oddly I have the exact opposite problem to you. I suppose you could always just abandon your chess engine and use mine when playing noviceskinderchocolate wrote:Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible?
For what it's worth I split the evaluation routine so that the basic stuff is at the top. Then I test to see if the level is greater than x before doing the following parts of the evaluation ie
Code: Select all
score = scoreMaterial() + randomInfluence(level)
if ( level < 2 ) return score
score += piecePositioning()
if ( level < 4 ) return score
score += pawnStructure()
score += mobility()
return score
I believe the chess program on the chess.com site does something like this but it occasionally does some very unlikely moves ie it's up about 20 pawns against a lone king and then randomly does the only bad move on the board that produces a stalemate (see here). It looked less like the user had beaten the program and more like the program had just become bored of playing. One quote on that thread stood out "Simulating mediocrity is very difficult."
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Reducing Strength
I've spent a lot of time to find something that works well, as in the "skill" command in Crafty.kinderchocolate wrote:Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible? I've found that limiting the number of nodes isn't working very well.
Also, what'd be the best way to tune the parameters?
1. I use a skill level between 0 and 100, where 0 is bad, and 100 is optimal. In eval, there is something like this:
final score = skill * eval_score / 100 + (100 - skill) * random_score / 100;
Net effect is that skill 50 uses 50% of normal eval, 50% random eval, combined.
2. selective search parameters are reduced proportional to skill. For example, for skill 50, null-move R value is cut 50%, check extension is cut but since it is 1, it gets cut to zero for any skill reduction. LMR reduction values (upper and lower bound) are reduced in the same way.
3. A "time burner" loop in the eval is activated to slow the program down, without making it play unnaturally fast. The lower the skill setting, the larger the loop, which reduces the tactical skill at about the same rate as the positional knowledge is phased out.
Doing the above produces a pretty natural-feeling weak opponent. If you just whack the eval, you still get a tactical genius at times. If you just whack the search, you still get a positionally strong player. And a pure random eval, by itself, still plays way too strongly due to "the Beal effect". Doing the above, one can tune the program down to 1000 or less, if desired.