MCTS: How to deal with extreme imbalances

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

MCTS: How to deal with extreme imbalances

Post by brtzsnr » Wed Jan 16, 2019 12:32 am

Consider this position https://lichess.org/KOImYPTl#60 which is highly favorable for white.

[D] R7/2B4p/1p2k1p1/8/1Pp3p1/2Q3P1/1P2PP1P/5RK1 w - - 6 31


The game is between two instances of zurichess mcts (less_than_one). Once the game reaches this extreme imbalance the engine moves aimlessly because all moves are completely winning for white and completely losing for black. White doesn't care about dropping the queen and then a rook since it is still winning.


What are good ways to improve the engine to make some real progress in this type of positions?

Ferdy
Posts: 3645
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: MCTS: How to deal with extreme imbalances

Post by Ferdy » Wed Jan 16, 2019 7:13 am

brtzsnr wrote:
Wed Jan 16, 2019 12:32 am
What are good ways to improve the engine to make some real progress in this type of positions?
While you may have

Code: Select all

move_score = Exploit() + Explore()
where:

Code: Select all

Exploit = f(winrate)
Explore = f(visits)
Perhaps you may use

Code: Select all

Exploit = f(winrate, material)
so that moves that gives material will be discouraged

Uri Blass
Posts: 8304
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: MCTS: How to deal with extreme imbalances

Post by Uri Blass » Wed Jan 16, 2019 7:29 am

I think that the best way is to change the scoring system so mate in 200 moves is worse than mate in 100 moves.

For example winning give the winning side 1-0.0001*number of moves and the losing side 0.0001*number of moves.

In this case mate in 100 gives 0.99 points and mate in 200 gives 0.98 points.

User avatar
hgm
Posts: 22896
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: MCTS: How to deal with extreme imbalances

Post by hgm » Wed Jan 16, 2019 7:45 am

Yeah, I already raised that point in a cute-chess issue discussion as well. The purpose of the heuristic evaluation is not only to reflect winning probability, but also to reflect progress. It is very bad to let it saturate too easily. Centi-Pawn scoring doesn't suffer from such saturation, and remains sensitive to small positional terms like centralisation no matter how large the advantage. But compressing the scale pushes such contributions below the noise level.

I guess you can only make it right by training it properly, e.g. like Uri suggests. Not only on the results of the games, but also on their duration.

chrisw
Posts: 1079
Joined: Tue Apr 03, 2012 2:28 pm

Re: MCTS: How to deal with extreme imbalances

Post by chrisw » Wed Jan 16, 2019 9:25 am

brtzsnr wrote:
Wed Jan 16, 2019 12:32 am
Consider this position https://lichess.org/KOImYPTl#60 which is highly favorable for white.

[D] R7/2B4p/1p2k1p1/8/1Pp3p1/2Q3P1/1P2PP1P/5RK1 w - - 6 31


The game is between two instances of zurichess mcts (less_than_one). Once the game reaches this extreme imbalance the engine moves aimlessly because all moves are completely winning for white and completely losing for black. White doesn't care about dropping the queen and then a rook since it is still winning.


What are good ways to improve the engine to make some real progress in this type of positions?
Fold depth to win into the evaluation
Chris Whittington
Ontological Terrorist
Lead Philosopher Computer Chess
Comrade Commissar Aspergers Liberation Front
Ostranenye Catalyst
Zero tolerance personal comments
5-4-8 tritype, INTP, BCF 221
facebook: chris.whittington.522
twitter: Skool_Dog

brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: MCTS: How to deal with extreme imbalances

Post by brtzsnr » Wed Jan 16, 2019 4:02 pm

Uri Blass wrote:
Wed Jan 16, 2019 7:29 am
I think that the best way is to change the scoring system so mate in 200 moves is worse than mate in 100 moves.

For example winning give the winning side 1-0.0001*number of moves and the losing side 0.0001*number of moves.

In this case mate in 100 gives 0.99 points and mate in 200 gives 0.98 points.
This is in interesting idea. I suspect that it'll give kingsafety a larger score. It doesn't pass yet my tests. I tried: 1e-4 -> -40Elo. 5e-5 -> +2Elo, 5e-5 -> +3Elo. I will try again with higher coefficients.

What worked for about 30Elo is to multiply the score by 0.75 before sigmoid. Instead of sigmoid(evaluateCP(pos) * 1e-2) now I have sigmoid(evaluateCP(pos) * 1e-2 * 0.75).

Daniel Shawul
Posts: 3560
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: MCTS: How to deal with extreme imbalances

Post by Daniel Shawul » Wed Jan 16, 2019 5:45 pm

brtzsnr wrote:
Wed Jan 16, 2019 12:32 am
Consider this position https://lichess.org/KOImYPTl#60 which is highly favorable for white.

[D] R7/2B4p/1p2k1p1/8/1Pp3p1/2Q3P1/1P2PP1P/5RK1 w - - 6 31


The game is between two instances of zurichess mcts (less_than_one). Once the game reaches this extreme imbalance the engine moves aimlessly because all moves are completely winning for white and completely losing for black. White doesn't care about dropping the queen and then a rook since it is still winning.


What are good ways to improve the engine to make some real progress in this type of positions?
Picking the move with the maximum score instead of the with most number of visits helps.

I also do a MATE_SCORE - ply correction when mating. This is possible because i use raw scores not fractions (0...1) for mcts bookeeping

Post Reply