Thans Matthew and Rasmus!!
Need to read you more carefully now.
Starting with move ordering.
Moderators: hgm, Rebel, chrisw
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
Sorry for my ignorance. What is a fail high?ZirconiumX wrote: ...
I would suggest you add two counters to your program. One measures the total number of fail highs, and the other measures the number of fail highs on the first legal move searched. Dividing the second by the first gives you a measure of how efficiently you are searching.
A move searched that at last was not the move choiced?
In case is that, cause the iterative deepening, I´m not sure at wich depth do that count. For all depths together?
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
not sure about the question.ZirconiumX wrote:Your move sorting shouldn't slow you down too much - how do you sort your moves?
...
First I use the same method I use to make moves less test for legality cause checks; en passant states changes; 50 moves rule, 3rd repetition rule; stalemate; etc.
And I´m ordering it one by one on a ladder where the new move is climbing pushing others down one by one till reach a move with same order value.
Is this the question?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Starting with move ordering.
Using the NegaMax convention, the alpha-beta search aborts the search whenever a successor is found with a score that is beta or higher. That is known as a "beta cut" or as a "fail high".Luis Babboni wrote:Sorry for my ignorance. What is a fail high?ZirconiumX wrote: ...
I would suggest you add two counters to your program. One measures the total number of fail highs, and the other measures the number of fail highs on the first legal move searched. Dividing the second by the first gives you a measure of how efficiently you are searching.
A move searched that at last was not the move choiced?
In case is that, cause the iterative deepening, I´m not sure at wich depth do that count. For all depths together?
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
Sounds interesting! I´ll try!Ras wrote:Some notes on the move sorting:
1) many programs don't actually sort the moves in the sense that they would generate a sorted move list from the previously unsorted one. Instead, they do a selection sort. Means, they:
- go through the full unsorted move list
- pick up the move with the highest associated value
- swap that move to movelist position 0
- for the second move, they do the same, but start scanning the list at position 1 instead of position 0
That can be faster as long as one of the first few tried moves gives a cutoff so that the rest isn't tried out...
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
At the end the numbers are not the same as if I do what I said?AlvaroBegue wrote:Using the NegaMax convention, the alpha-beta search aborts the search whenever a successor is found with a score that is beta or higher. That is known as a "beta cut" or as a "fail high".Luis Babboni wrote:Sorry for my ignorance. What is a fail high?ZirconiumX wrote: ...
I would suggest you add two counters to your program. One measures the total number of fail highs, and the other measures the number of fail highs on the first legal move searched. Dividing the second by the first gives you a measure of how efficiently you are searching.
A move searched that at last was not the move choiced?
In case is that, cause the iterative deepening, I´m not sure at wich depth do that count. For all depths together?
Remember I still not use two values, alpha and beta.... at least explicitly.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
Sorry, not understand this.Ras wrote:Some notes on the move sorting:
...
2) for those that do actually sort the list, the worst ones really use "bubble sort". This is total nonsense, of course.
3) the next best ones use whatever sorting algorithm their programming language offers. This is especially slow in case of C with the qsort because every comparison results in a function call. That can be a huge waste of time.
4) for lists of not more than (typically) 80 elements, quicksort is slow due to the overhead. See here: http://embeddedgurus.com/stack-overflow ... d-systems/
For the CT800, I got a considerable speedup when I changed NG-Play from the C library qsort to a self-written shellsort. Still, the program spends around 12% of its time in the sorting routine. I can confirm Jones' observation that shellsort is faster than heapsort, which I had also tried and benchmarked.
5) conclusion: if your program actually sorts the list, use shellsort as sorting algorithm. It is fast, easy to implement, non-recursive. Use the Ciura sequence (1, 4, 10, 23, 57, 132, 301, 701, 1750) - 57 is the maximum useful value.
I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
If then numbers are not exactly the same, the numbers I said: "how many moves searched at the end are not the choiced", do not works for Matthew´s suggested idea?Luis Babboni wrote:At the end the numbers are not the same as if I do what I said?AlvaroBegue wrote:Using the NegaMax convention, the alpha-beta search aborts the search whenever a successor is found with a score that is beta or higher. That is known as a "beta cut" or as a "fail high".Luis Babboni wrote:Sorry for my ignorance. What is a fail high?ZirconiumX wrote: ...
I would suggest you add two counters to your program. One measures the total number of fail highs, and the other measures the number of fail highs on the first legal move searched. Dividing the second by the first gives you a measure of how efficiently you are searching.
A move searched that at last was not the move choiced?
In case is that, cause the iterative deepening, I´m not sure at wich depth do that count. For all depths together?
Remember I still not use two values, alpha and beta.... at least explicitly.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
I insist with my first question.
No matter how good the move ordering is, with few pieces on board the advantage against no ordering moves at all is less than with many pieces on board, I´m right?
So if your method to order moves is too bad, it seems logical that you lost more time ordering moves than the time doing it allows you to save?
I just want to be sure the problem could be just in my way to sort moves.
Of course may be is in other place, but I want to know that if COULD be there.
Thanks again for your time guys!
No matter how good the move ordering is, with few pieces on board the advantage against no ordering moves at all is less than with many pieces on board, I´m right?
So if your method to order moves is too bad, it seems logical that you lost more time ordering moves than the time doing it allows you to save?
I just want to be sure the problem could be just in my way to sort moves.
Of course may be is in other place, but I want to know that if COULD be there.
Thanks again for your time guys!
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Starting with move ordering.
Try with option 1, where you find the move that should be searched next without worrying about the order of the others, then search it immediately.Luis Babboni wrote:Sorry, not understand this.Ras wrote:Some notes on the move sorting:
...
2) for those that do actually sort the list, the worst ones really use "bubble sort". This is total nonsense, of course.
3) the next best ones use whatever sorting algorithm their programming language offers. This is especially slow in case of C with the qsort because every comparison results in a function call. That can be a huge waste of time.
4) for lists of not more than (typically) 80 elements, quicksort is slow due to the overhead. See here: http://embeddedgurus.com/stack-overflow ... d-systems/
For the CT800, I got a considerable speedup when I changed NG-Play from the C library qsort to a self-written shellsort. Still, the program spends around 12% of its time in the sorting routine. I can confirm Jones' observation that shellsort is faster than heapsort, which I had also tried and benchmarked.
5) conclusion: if your program actually sorts the list, use shellsort as sorting algorithm. It is fast, easy to implement, non-recursive. Use the Ciura sequence (1, 4, 10, 23, 57, 132, 301, 701, 1750) - 57 is the maximum useful value.
I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".