LMR in micro-Max

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michael Sherwin
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: LMR in micro-Max

Post by Michael Sherwin » Tue Apr 10, 2007 3:38 pm

Dann Corbit wrote:IID can be as simple as 3-4 lines of code and should give you good move ordering.
Grrrrrrr :evil:
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Peter Fendrich

Re: LMR in micro-Max

Post by Peter Fendrich » Tue Apr 10, 2007 6:05 pm

The most simple move ordering system I know about is piece-from-to tables. Ed uses them instead of LMR if I understand him right. Depending on how you count your 2000 characters, maybe it can be used. If you read in the table it needs a few lines.
BTW. I looked into your site and found some interesting stuff. The Evolution experiment, Genetic Programming, is in my taste!
Even more your elaboration about EGDB generation is interesting as I have started to look at bitbase generation and probing.
Thanks!

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: LMR in micro-Max

Post by Bill Rogers » Tue Apr 10, 2007 8:27 pm

JP wrote:The most simple move ordering system I know about is piece-from-to tables. Ed uses them instead of LMR if I understand him right. Thanks!
I may be wrong but the above tables only help to generate moves faster while the main thought here is how to select the best move from all those generated. Ed talked about using piece square tables along with captures to do a preliminary sort. He said that this gretely speeded up his program.
If I am missing the point here then I am sorry. I am vry tired.
Bill

Peter Fendrich

Re: LMR in micro-Max

Post by Peter Fendrich » Tue Apr 10, 2007 8:43 pm

I may as well have missed something but if he have some kind of move ordering after the hash move he can start to use LMR in a more "normal" way.
A "few lines" in this program seems to be too much, however...

/Peter

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: LMR in micro-Max

Post by Bill Rogers » Tue Apr 10, 2007 9:26 pm

Hi Peter
Well in his old web page he mentioned this and pointed it out as a contributing factor to not only the speed of his progam but to adding to its strength.
I have looked at his 'new' web page with only a passing glance and am not sure what he talks about now.
Bill

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

Re: LMR in micro-Max

Post by hgm » Thu Apr 12, 2007 10:44 am

JP wrote:The most simple move ordering system I know about is piece-from-to tables. Ed uses them instead of LMR if I understand him right. Depending on how you count your 2000 characters, maybe it can be used. If you read in the table it needs a few lines.
BTW. I looked into your site and found some interesting stuff. The Evolution experiment, Genetic Programming, is in my taste!
Even more your elaboration about EGDB generation is interesting as I have started to look at bitbase generation and probing.
Thanks!
Well, thank you for your interest. Alas, I put a temporary stop on the evolution experiment as I needed the laptop on which I was running it for other purposes, and progress on evolving a Chess engine from scratch was rather slow. In addition the program was very inefficient (comparing interpreted code, rather than compiled code), so I figured that if I would have to run it for 10 years, I would somewhere before that find the time to speed it up 10 times, and still produce a result earlier...

As for uMax, the problem is not so much that I have no criterion to sort the moves by, but that the bare storing and sorting of the moves already causes a major increase of the code. In cut-moves IID provides uMax with very good move ordering as far as finding cut-moves is concerned. Better static move ordering would hardly improve that.

The problem, however, is that shallower searches do not help you to order moves in an all-node, as the scores were spoiled by alpha-beta pruning. So you have to fall back on static criteria, which are normally much less reliable than search scores, but at least are free of corruption by alpha-beta pruning.

I have my doubts, though, that it would be worth it to invest a lot of effort in move ordering just to be able to make the LMR decisions a little bit better. Especially since using order-independent criteria, such as the simple fact if the move is a capture or not, already seem to give you most of the advantage that LMR brings.

How many ELO does your engine gain from LMR?

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

Re: LMR in micro-Max

Post by Uri Blass » Thu Apr 12, 2007 11:26 am

hgm wrote:
JP wrote:The most simple move ordering system I know about is piece-from-to tables. Ed uses them instead of LMR if I understand him right. Depending on how you count your 2000 characters, maybe it can be used. If you read in the table it needs a few lines.
BTW. I looked into your site and found some interesting stuff. The Evolution experiment, Genetic Programming, is in my taste!
Even more your elaboration about EGDB generation is interesting as I have started to look at bitbase generation and probing.
Thanks!
Well, thank you for your interest. Alas, I put a temporary stop on the evolution experiment as I needed the laptop on which I was running it for other purposes, and progress on evolving a Chess engine from scratch was rather slow. In addition the program was very inefficient (comparing interpreted code, rather than compiled code), so I figured that if I would have to run it for 10 years, I would somewhere before that find the time to speed it up 10 times, and still produce a result earlier...

As for uMax, the problem is not so much that I have no criterion to sort the moves by, but that the bare storing and sorting of the moves already causes a major increase of the code. In cut-moves IID provides uMax with very good move ordering as far as finding cut-moves is concerned. Better static move ordering would hardly improve that.

The problem, however, is that shallower searches do not help you to order moves in an all-node, as the scores were spoiled by alpha-beta pruning. So you have to fall back on static criteria, which are normally much less reliable than search scores, but at least are free of corruption by alpha-beta pruning.

I have my doubts, though, that it would be worth it to invest a lot of effort in move ordering just to be able to make the LMR decisions a little bit better. Especially since using order-independent criteria, such as the simple fact if the move is a capture or not, already seem to give you most of the advantage that LMR brings.

How many ELO does your engine gain from LMR?
I do not know.
it may be dependent on other pruning and extensions that people use.

I think that it is important to test it against different engines in order to know how much you earn from it.

It is possible that you get misleading results by testing micromax against itself.

Uri

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

Re: LMR in micro-Max

Post by hgm » Thu Apr 12, 2007 11:37 am

I agree with that, and I will certainly perform such tests in the future, when I am set up better to do this. (I would have to obtain a sufficiently large number of suitable opponents, for instance.)

Nevertheless, comparing two differently shaped search trees against each other at equal (average) number of nodes, using the same eval in both, still seems a meaningful test for how well a pruning method is able to discriminate between useful and useless parts of the tree. Even if you cannot directly translate it into an ELO number.

It still would help, though, to know what is the best one can expect from a technique like LMR. So I would still be curious to how many ELO points others have been able to gain through LMR, and how advanced they had to make it to get there.

Post Reply