How to test if MCTS is working?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

chessica
Posts: 672
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: How to test if MCTS is working?

Post by chessica »

JacquesRW wrote: Fri May 31, 2024 4:08 pm
chessica wrote: Fri May 31, 2024 3:24 pm "works" ---> means that the engine does exactly what it is supposed to do, and does it correctly.
This is the emptiest statement ever made. You can't give an answer to a question like that. What exactly, in your view, is the MCTS engine meant to do?
No, no.

Here: https://www.chessprogramming.org/Monte- ... ree_Search it says what MCTS should do.
There is no ambiguity.

Pure Monte-Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. A game is called “Monte Carlo perfect” when this procedure converges to perfect play for each position, when T goes to infinity. However, with limited time per move, increasing T does not guarantee to find a better move

But how do I check whether the engine is sticking to it?
JacquesRW
Posts: 69
Joined: Sat Jul 30, 2022 12:12 pm
Full name: Jamie Whiting

Re: How to test if MCTS is working?

Post by JacquesRW »

chessica wrote: Fri May 31, 2024 5:47 pm
JacquesRW wrote: Fri May 31, 2024 4:08 pm
chessica wrote: Fri May 31, 2024 3:24 pm "works" ---> means that the engine does exactly what it is supposed to do, and does it correctly.
This is the emptiest statement ever made. You can't give an answer to a question like that. What exactly, in your view, is the MCTS engine meant to do?
No, no.

Here: https://www.chessprogramming.org/Monte- ... ree_Search it says what MCTS should do.
There is no ambiguity.

Pure Monte-Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. A game is called “Monte Carlo perfect” when this procedure converges to perfect play for each position, when T goes to infinity. However, with limited time per move, increasing T does not guarantee to find a better move

But how do I check whether the engine is sticking to it?
You might want to read your source there, because that is referring to Monte-Carlo Search (MCS), not MCTS.
There absolutely is ambiguity in what you may mean by "works", because convergence properties have little practical relevance to a chess engine that has a decidedly finite amount of compute available. E.g. you can trivially edit a strong MCTS engine to no longer have these convergence properties without any noticeable impact on playing strength, would you say the search no longer works then?
The only way for you to verify that an MCTS engine "works" by your definition is to verify the code formally.
chessica
Posts: 672
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: How to test if MCTS is working?

Post by chessica »

JacquesRW wrote: Fri May 31, 2024 6:33 pm
chessica wrote: Fri May 31, 2024 5:47 pm
JacquesRW wrote: Fri May 31, 2024 4:08 pm
chessica wrote: Fri May 31, 2024 3:24 pm "works" ---> means that the engine does exactly what it is supposed to do, and does it correctly.
This is the emptiest statement ever made. You can't give an answer to a question like that. What exactly, in your view, is the MCTS engine meant to do?
No, no.

Here: https://www.chessprogramming.org/Monte- ... ree_Search it says what MCTS should do.
There is no ambiguity.

Pure Monte-Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. A game is called “Monte Carlo perfect” when this procedure converges to perfect play for each position, when T goes to infinity. However, with limited time per move, increasing T does not guarantee to find a better move

But how do I check whether the engine is sticking to it?
You might want to read your source there, because that is referring to Monte-Carlo Search (MCS), not MCTS.
There absolutely is ambiguity in what you may mean by "works", because convergence properties have little practical relevance to a chess engine that has a decidedly finite amount of compute available. E.g. you can trivially edit a strong MCTS engine to no longer have these convergence properties without any noticeable impact on playing strength, would you say the search no longer works then?
The only way for you to verify that an MCTS engine "works" by your definition is to verify the code formally.
Oh, I'm just a user and not a programmer, so I can't check the code.

From WIKI:

Four Phases

MCTS consists of four strategic phases, repeated as long as there is time left [13] :

1.) In the Selection phase the tree is traversed from the root node until it selects a leaf node that is not added to the tree yet
2.) The Expansion strategy adds the leaf node to the tree
3.) --->>> The Simulation strategy plays moves in self-play until the end of the game. The result is either 1, 0 ,-1
4.) The Backpropagation strategy propagates the results through the tree


Regarding 3.) I meant the question: can you watch the games played internally? And whether all possible games were really played?
JacquesRW
Posts: 69
Joined: Sat Jul 30, 2022 12:12 pm
Full name: Jamie Whiting

Re: How to test if MCTS is working?

Post by JacquesRW »

chessica wrote: Fri May 31, 2024 8:13 pm Regarding 3.) I meant the question: can you watch the games played internally? And whether all possible games were really played?
Well, maybe a specific MCTS engine would provide the ability to write simulations to a PGN (note that there would be some thousands of these per second). The thing is that simulations are (relatively) slow and inaccurate, so in every MCTS engine that I'm aware of that's of some reasonable strength, the simulations are replaced with an evaluation function.

Not all possible games would be played because you generally only run 1 simulation per iteration of MCTS.
chesskobra
Posts: 194
Joined: Thu Jul 21, 2022 12:30 am
Full name: Chesskobra

Re: How to test if MCTS is working?

Post by chesskobra »

Are you sure that it is a pure MCTS engine? What engine is it? If it is not a pure MCTS engine, then your task of verifying if MCTS is working (that too without even looking at the code) is even more difficult. I would instead implement pure MCTS for some other task (not necessarily a game), and see how it performs relative to other algorithms for that task.
chessica
Posts: 672
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: How to test if MCTS is working?

Post by chessica »

JacquesRW wrote: Fri May 31, 2024 8:22 pm
chessica wrote: Fri May 31, 2024 8:13 pm Regarding 3.) I meant the question: can you watch the games played internally? And whether all possible games were really played?
Well, maybe a specific MCTS engine would provide the ability to write simulations to a PGN (note that there would be some thousands of these per second). The thing is that simulations are (relatively) slow and inaccurate, so in every MCTS engine that I'm aware of that's of some reasonable strength, the simulations are replaced with an evaluation function.

Not all possible games would be played because you generally only run 1 simulation per iteration of MCTS.
Good morning, you could try it out in a position test so that it doesn't get out of hand.
chessica
Posts: 672
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: How to test if MCTS is working?

Post by chessica »

JacquesRW wrote: Fri May 31, 2024 8:22 pm
chessica wrote: Fri May 31, 2024 8:13 pm Regarding 3.) I meant the question: can you watch the games played internally? And whether all possible games were really played?
Well, maybe a specific MCTS engine would provide the ability to write simulations to a PGN (note that there would be some thousands of these per second). The thing is that simulations are (relatively) slow and inaccurate, so in every MCTS engine that I'm aware of that's of some reasonable strength, the simulations are replaced with an evaluation function.

Not all possible games would be played because you generally only run 1 simulation per iteration of MCTS.
Do you know a suitable position where the advantages of an MCTS engine can be particularly well recognized as a test position?
User avatar
hgm
Posts: 27892
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How to test if MCTS is working?

Post by hgm »

An engine is supposed to produce a leag move in any conceivable position. Nothing more, nothing less. When correctly implemented MCTS is guaranteed to do that.
User avatar
Antihelion
Posts: 30
Joined: Tue Mar 26, 2024 8:21 pm
Full name: Lyndon S. Sears

Re: How to test if MCTS is working?

Post by Antihelion »

How to test if oxygen is working?
chessica
Posts: 672
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: How to test if MCTS is working?

Post by chessica »

You're in the wrong forum, joker.