An Idea Of speeding up MTD-f

[bob]

Hi Bob!

The thread is http://www.talkchess.com/forum/viewtopi ... ht=#452797

The most relevant post for crafty is this post I guess.

Hi all of you!

I am comming back with a faster but a less accurate simplification extension idea. Of course my idea might not work but I think and hope it can make a difference since the additional computational cost is a constant and the gain in search tree exponential. I guess therfore if you want to see any gains of my idea you would have to test the idea on different time controls and then extrapolate the result to longer time controls to see if it might be a gain.

If you think it is to expensive counting the number of opponents moves you could do an approximation by counting the opponents average mobility based on the opponents pieces instead.

For example you could count the average mobility for the pieces maybe as averagePawnMobility = 1, averageKnightMobility = 6, averageBishopMobility = 7, averageRookMobility = 9, averageQueenMobility = averageBishopMobility + averageRookMobility = 16 and averageKingMobility = 4 and finally take the logarithm of the sum of the opponents averageMobilities multiplied with some constant multiplied with the depth you usually would consider your move as. You could precalculate the logarithms and put them in an array and the averageMobility could easily be incrementally updated when moving or undoing a move.

The benifit of this type of reduction/extension it is that you will look deeper into lines where you simplify the game by removing pieces and thus more easily could see if a move is good or not.

If you want to improve the idea even more you could use two types of averageMobilityValues depending on the game stage and then interpolating between opening (give bonus to knights) and endgame (give bonus to bishops, rooks, queens and king) and then round the value to use the precalculated logarithms.

Good luck with your engines!!!

It seems that the idea is to extend to simplify. Isn't that similar to just extending any capture, since any capture reduces opponent mobility and the resulting size of the tree? I'm not real big on extensions myself, and after a ton of testing, the only one I have left is extending safe moves that give check (checks that do not lose material more precisely).

[Pio]

Hi Bob!

The thread is http://www.talkchess.com/forum/viewtopi ... ht=#452797

The most relevant post for crafty is this post I guess.

Hi all of you!

I am comming back with a faster but a less accurate simplification extension idea. Of course my idea might not work but I think and hope it can make a difference since the additional computational cost is a constant and the gain in search tree exponential. I guess therfore if you want to see any gains of my idea you would have to test the idea on different time controls and then extrapolate the result to longer time controls to see if it might be a gain.

If you think it is to expensive counting the number of opponents moves you could do an approximation by counting the opponents average mobility based on the opponents pieces instead.

For example you could count the average mobility for the pieces maybe as averagePawnMobility = 1, averageKnightMobility = 6, averageBishopMobility = 7, averageRookMobility = 9, averageQueenMobility = averageBishopMobility + averageRookMobility = 16 and averageKingMobility = 4 and finally take the logarithm of the sum of the opponents averageMobilities multiplied with some constant multiplied with the depth you usually would consider your move as. You could precalculate the logarithms and put them in an array and the averageMobility could easily be incrementally updated when moving or undoing a move.

The benifit of this type of reduction/extension it is that you will look deeper into lines where you simplify the game by removing pieces and thus more easily could see if a move is good or not.

If you want to improve the idea even more you could use two types of averageMobilityValues depending on the game stage and then interpolating between opening (give bonus to knights) and endgame (give bonus to bishops, rooks, queens and king) and then round the value to use the precalculated logarithms.

Good luck with your engines!!!

It seems that the idea is to extend to simplify. Isn't that similar to just extending any capture, since any capture reduces opponent mobility and the resulting size of the tree? I'm not real big on extensions myself, and after a ton of testing, the only one I have left is extending safe moves that give check (checks that do not lose material more precisely).

Hi Bob!

You are absolutely right that my simplified idea is similar to extend captures but with some advantages:

1) If the capture is close to the root the normal capture extension will extend the move too little and if the capture move is close to the leaves the normal extension will extend the move too much.

2) My idea will work much better when moving from example a position with many pawns and queens to only pawns endgame and will replace any illogical extension of such moves that suffer from the problems described in 1)

If you look at my first post in the thread http://www.talkchess.com/forum/viewtopi ... ht=#452797 you will see that my more general idea of looking at all possible opponent moves will make you be able to skip your extension of safe moves that give checks, will look into forced moves much deeper and with some code in the transposition table recording how many possible moves that are not lost for the opponent, will make you to prove checkmate faster. My original idea will scale better but has a big additional computing cost and will not work with existing check extensions that my simplified idea will.

I think if you want to introduce my idea you will have to do lots of matches on different time controls and extrapolate the results to really long matches since the computing cost is expensive but the scaling is better and should probably show an improvement on long games.

Good luck!

[Henk]

I tried out MTD-f today (again). I disabled all reductions like LMR, Null-move and futility pruning. Disabling them was not a big step for I doubt if they give any profit in my engine. Perhaps the conditions for applying them are not right in my engine, for I see my engine making blunders sometimes.

But MTD-f was far too slow. Changing step size did not help much. Making evaluation more coarse did not help enough too.

Good bye MTD-f.

[bob]

This is not new. There have been several attempts to increase the speed of convergence. Fail-soft alpha/beta was the first where you get a score outside the a-b window, and use that for the next cycle. Others have tried various forms of accelerating convergence by non-linear methods of shifting the window, as you propose.

The real problem today is that most programs have very sensitive evaluation terms, and one extra ply can shift the score significantly, which is a killer for mtd(f).

[bob]

Hi Bob!

The thread is http://www.talkchess.com/forum/viewtopi ... ht=#452797

The most relevant post for crafty is this post I guess.

Hi all of you!

I am comming back with a faster but a less accurate simplification extension idea. Of course my idea might not work but I think and hope it can make a difference since the additional computational cost is a constant and the gain in search tree exponential. I guess therfore if you want to see any gains of my idea you would have to test the idea on different time controls and then extrapolate the result to longer time controls to see if it might be a gain.

If you think it is to expensive counting the number of opponents moves you could do an approximation by counting the opponents average mobility based on the opponents pieces instead.

For example you could count the average mobility for the pieces maybe as averagePawnMobility = 1, averageKnightMobility = 6, averageBishopMobility = 7, averageRookMobility = 9, averageQueenMobility = averageBishopMobility + averageRookMobility = 16 and averageKingMobility = 4 and finally take the logarithm of the sum of the opponents averageMobilities multiplied with some constant multiplied with the depth you usually would consider your move as. You could precalculate the logarithms and put them in an array and the averageMobility could easily be incrementally updated when moving or undoing a move.

The benifit of this type of reduction/extension it is that you will look deeper into lines where you simplify the game by removing pieces and thus more easily could see if a move is good or not.

If you want to improve the idea even more you could use two types of averageMobilityValues depending on the game stage and then interpolating between opening (give bonus to knights) and endgame (give bonus to bishops, rooks, queens and king) and then round the value to use the precalculated logarithms.

Good luck with your engines!!!

It seems that the idea is to extend to simplify. Isn't that similar to just extending any capture, since any capture reduces opponent mobility and the resulting size of the tree? I'm not real big on extensions myself, and after a ton of testing, the only one I have left is extending safe moves that give check (checks that do not lose material more precisely).

Hi Bob!

You are absolutely right that my simplified idea is similar to extend captures but with some advantages:

1) If the capture is close to the root the normal capture extension will extend the move too little and if the capture move is close to the leaves the normal extension will extend the move too much.

2) My idea will work much better when moving from example a position with many pawns and queens to only pawns endgame and will replace any illogical extension of such moves that suffer from the problems described in 1)

If you look at my first post in the thread http://www.talkchess.com/forum/viewtopi ... ht=#452797 you will see that my more general idea of looking at all possible opponent moves will make you be able to skip your extension of safe moves that give checks, will look into forced moves much deeper and with some code in the transposition table recording how many possible moves that are not lost for the opponent, will make you to prove checkmate faster. My original idea will scale better but has a big additional computing cost and will not work with existing check extensions that my simplified idea will.

I think if you want to introduce my idea you will have to do lots of matches on different time controls and extrapolate the results to really long matches since the computing cost is expensive but the scaling is better and should probably show an improvement on long games.

Good luck!

I posted a reply to the wrong thread point. I'll try again. The biggest problem I see with mtd(f) is that it is so sensitive to evaluation changes. And evaluation functions are very sensitive to position changes. Adding one more ply can shift the final score by 10-20-50 or beyond centipawns. Which makes convergence a pain. Also, with today's ordering tricks and reductions/pruning based on position in the move list, you don't search the same tree each time, given the same root position, because different moves will be reduced or pruned in different ways since the history counters constantly change.

I think this really is hopeless with the search trickery being used today. Might have been fine back in the more consistent days..