TalkChess.com
Hosted by Your Move Chess & Games

 Reducing Strength Goto page 1, 2  Next
Author Message
Ted Wong

Joined: 01 Nov 2010
Posts: 236

 Posted: Thu Mar 15, 2012 12:22 am    Post subject: Reducing Strength 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?
Edmund Moshammer

Joined: 03 Dec 2007
Posts: 598
Location: St. Gallen, Switzerland

 Posted: Thu Mar 15, 2012 2:43 am    Post subject: 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.
Ted Wong

Joined: 01 Nov 2010
Posts: 236

 Posted: Thu Mar 15, 2012 6:21 am    Post subject: Re: Reducing Strength It's a bit vague. Any concrete examples such as source code or like articles?
Pawel Koziol

Joined: 15 Jan 2007
Posts: 274
Location: Warsza

 Posted: Thu Mar 15, 2012 9:10 am    Post subject: 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)_________________Pawel Koziol http://www.pkoziol.cal24.pl/rodent/rodent.htm
Ted Wong

Joined: 01 Nov 2010
Posts: 236

 Posted: Thu Mar 15, 2012 10:04 am    Post subject: 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.
Ferdinand Mosca

Joined: 10 Aug 2008
Posts: 452
Location: Philippines

Posted: Thu Mar 15, 2012 10:34 am    Post subject: Re: Reducing Strength

 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?

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.
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: 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
Robert Houdart

Joined: 15 Mar 2010
Posts: 1251

Posted: Thu Mar 15, 2012 10:44 am    Post subject: Re: Reducing Strength

 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?

Houdini 2 uses the following techniques:

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
Ed Schroder

Joined: 18 Aug 2011
Posts: 1617

 Posted: Thu Mar 15, 2012 12:17 pm    Post subject: 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.
Mike Robinson

Joined: 25 Jul 2011
Posts: 97
Location: London

Posted: Thu Mar 15, 2012 1:55 pm    Post subject: Re: Reducing Strength

 kinderchocolate wrote: Other than limiting the number of nodes and depths, any suggestions on how to reduce the playing strength as realistic as possible?
Oddly I have the exact opposite problem to you. I suppose you could always just abandon your chess engine and use mine when playing novices

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: score = scoreMaterial() + randomInfluence(level) if ( level < 2 ) return score score += piecePositioning() if ( level < 4 ) return score score += pawnStructure() score += mobility() return score

I also increase the random factor on low levels. I also have a maximum depth allowed depending on the level - this includes any quintessent (or however you spell it) searches. I didn't like the idea of reducing the time down to fractions of a second because I think it just belittles the human opponent - you feel like the program is saying it can beat you even if it has it's hands tied.

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."
Robert Hyatt

Joined: 27 Feb 2006
Posts: 15819
Location: Birmingham, AL

Posted: Thu Mar 15, 2012 2:02 pm    Post subject: Re: Reducing Strength

 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?

I've spent a lot of time to find something that works well, as in the "skill" command in Crafty.

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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMTGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum