Reducing Strength

[kinderchocolate]

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]

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.

[kinderchocolate]

It's a bit vague. Any concrete examples such as source code or like articles?

[PK]

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)

[kinderchocolate]

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.

[Ferdy]

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: 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

[Houdini]

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

[Rebel]

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_bike_kite]

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: Select all

score = scoreMaterial() + randomInfluence(level)
if ( level < 2 ) return score

score += piecePositioning&#40;)
if ( level < 4 ) return score

score += pawnStructure&#40;)
score += mobility&#40;)
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."

[bob]

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.