All these advice usually never work. Just like explaining minority attack to a beginner.
Better implement your own stupid engine first and try to improve it all by yourself.
Starting with move ordering.
Moderators: hgm, Rebel, chrisw
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Starting with move ordering.
So probably you go through the array over and over, swapping neighbouring values until you go through the whole array without any further swap. That is called "bubble sort", and it is the slowest sorting algorithm. It looks like this in Basic:Luis Babboni wrote:I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".
https://rosettacode.org/wiki/Sorting_al ... sort#BASIC
Shellsort is a different sorting algorithm, it looks like this:
https://en.wikipedia.org/wiki/Shellsort#Pseudocode
If you still have the choice, I agree with Alvaro (option 1), at least for a first try. You might add in a sorting algorithm later and compare what is faster.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
Mmm, I´m not sure is like this.Henk wrote:All these advice usually never work. Just like explaining minority attack to a beginner.
Better implement your own stupid engine first and try to improve it all by yourself.
I must give you that I did not follow most of the suggestions, but I followed not few.
Of course I prefer to solve problems by myself (there is the fun, I´m not doing it for money ), but when I reached a no exit way, many people here helped me.
Last edited by Luis Babboni on Sat Sep 17, 2016 3:37 am, edited 3 times in total.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
Definitevely yes!Ras wrote:So probably you go through the array over and over, swapping neighbouring values until you go through the whole array without any further swap. That is called "bubble sort", and it is the slowest sorting algorithm. It looks like this in Basic:Luis Babboni wrote:I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".
https://rosettacode.org/wiki/Sorting_al ... sort#BASIC
...
Ras wrote: If you still have the choice, I agree with Alvaro (option 1), at least for a first try. You might add in a sorting algorithm later and compare what is faster.
This is the idea now... a suggested by people here idea!
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Starting with move ordering.
If you are not yet using alpha-beta for cutting down the search tree, that should be the next thing to do. Once you do that, move ordering will make a huge difference.Luis Babboni wrote:Remember I still not use two values, alpha and beta.... at least explicitly.
See here: https://chessprogramming.wikispaces.com/Alpha-Beta
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Starting with move ordering.
Correct. The extreme case is that you only have one legal move.Luis Babboni wrote: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?
The problem is that in the initial position, you have 20 moves available. But during the middle game, that goes up to something like 80 different moves.
Imagine the kind of middle game positions I mentioned, with 80 different moves. Obviously, if you were to search all of them, then going one ply deeper in your search would take 80 times longer. The factor by which the time goes up when going one ply deeper is called "branching factor".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?
If you have a branching factor of B and you search D plies deep, then the formula for the computing time is t=c*B^D. c is some constant factor, more or less the time of your static evaluation function. As you see, the branching factor is in the basis of a power function.
The move ordering plus alpha-beta aims at reducing the branching factor by cutting away large parts of the search tree. If you have a good move ordering, that will cut down the branching factor. So some time for having a good move ordering is well spent.
You can check this by benchmarking how your computing time goes up when going deeper.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
My with move ordering version is better than my without move ordering verison in middle game but worst in end games.Ras wrote:Correct. The extreme case is that you only have one legal move.Luis Babboni wrote: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?
The problem is that in the initial position, you have 20 moves available. But during the middle game, that goes up to something like 80 different moves.
Imagine the kind of middle game positions I mentioned, with 80 different moves. Obviously, if you were to search all of them, then going one ply deeper in your search would take 80 times longer. The factor by which the time goes up when going one ply deeper is called "branching factor".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?
If you have a branching factor of B and you search D plies deep, then the formula for the computing time is t=c*B^D. c is some constant factor, more or less the time of your static evaluation function. As you see, the branching factor is in the basis of a power function.
The move ordering plus alpha-beta aims at reducing the branching factor by cutting away large parts of the search tree. If you have a good move ordering, that will cut down the branching factor. So some time for having a good move ordering is well spent.
You can check this by benchmarking how your computing time goes up when going deeper.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
I´m in fault here. I think I use an algorithm that gives the same results as Alpha Beta but in a way that do not use, at least explicitly, two values.Ras wrote:If you are not yet using alpha-beta for cutting down the search tree, that should be the next thing to do. Once you do that, move ordering will make a huge difference.Luis Babboni wrote:Remember I still not use two values, alpha and beta.... at least explicitly.
See here: https://chessprogramming.wikispaces.com/Alpha-Beta
I said I´m in fault because I still do not have a good proof of what I´m saying.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with move ordering.
I´ll try to explain again my one value algorithm that works like Alpha Beta two values works (I think):Luis Babboni wrote:I´m in fault here. I think I use an algorithm that gives the same results as Alpha Beta but in a way that do not use, at least explicitly, two values.Ras wrote:If you are not yet using alpha-beta for cutting down the search tree, that should be the next thing to do. Once you do that, move ordering will make a huge difference.Luis Babboni wrote:Remember I still not use two values, alpha and beta.... at least explicitly.
See here: https://chessprogramming.wikispaces.com/Alpha-Beta
I said I´m in fault because I still do not have a good proof of what I´m saying.
Counting score always from white side, I spare the problem in 4 different situations:
1-The engine plays whites and is searching till depth d and in ply d plays whites.
2-The engine plays whites and is searching till depth d and in ply d plays black.
3-The engine plays blacks and is searching till depth d and in ply d plays whites.
4-The engine plays blacks and is searching till depth d and in ply d plays blacks.
Imagine the first branch you evaluate using minimax, gives an score of 100 (whites better).
In case 1, any branch where I found a move by blacks in ply d-1 that gives an score of more than 100 after whites move in ply d will be cut and not be considered cause black never will choice it cause have other option where the best score whites could reach is 100.
In case 2, any branch where I found a move by whites in ply d-1 that gives an score of less than 100 after blacks move in ply d will be cut and not be considered cause whites have other option where whites could reach an score of 100.
In case 3, any branch where I found a move by blacks in ply d-1 that gives an score of more than 100 after whites move in ply d will be cut and not be considered cause blacks have other option where whites could reach a maximum score of 100.
In case 4, any branch where I found a move by whites in ply d-1 that gives an score of less than 100 after blacks move in ply d will be cut and not be considered cause whites never will choice it cause have other option where whites could asure an score of 100.
The only value I considered all the time, is the same single "100" (in fact could be changing while the search but is always just one value). Not two differents values (alpha and beta).
Once I have the value at d-1, I´ll do the same for d-2 depth and so on till reach d=1.
In case you have time to read and try to understand it, seems to be a wrong algorithm or just more complicated one than alpha beta?
-
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: Starting with move ordering.
It looks to me that you are doing only a shallow cutoff (or something very similar - which is far from optimal).Luis Babboni wrote:I´ll try to explain again my one value algorithm that works like Alpha Beta two values works (I think):Luis Babboni wrote:I´m in fault here. I think I use an algorithm that gives the same results as Alpha Beta but in a way that do not use, at least explicitly, two values.Ras wrote:If you are not yet using alpha-beta for cutting down the search tree, that should be the next thing to do. Once you do that, move ordering will make a huge difference.Luis Babboni wrote:Remember I still not use two values, alpha and beta.... at least explicitly.
See here: https://chessprogramming.wikispaces.com/Alpha-Beta
I said I´m in fault because I still do not have a good proof of what I´m saying.
Counting score always from white side, I spare the problem in 4 different situations:
1-The engine plays whites and is searching till depth d and in ply d plays whites.
2-The engine plays whites and is searching till depth d and in ply d plays black.
3-The engine plays blacks and is searching till depth d and in ply d plays whites.
4-The engine plays blacks and is searching till depth d and in ply d plays blacks.
Imagine the first branch you evaluate using minimax, gives an score of 100 (whites better).
In case 1, any branch where I found a move by blacks in ply d-1 that gives an score of more than 100 after whites move in ply d will be cut and not be considered cause black never will choice it cause have other option where the best score whites could reach is 100.
In case 2, any branch where I found a move by whites in ply d-1 that gives an score of less than 100 after blacks move in ply d will be cut and not be considered cause whites have other option where whites could reach an score of 100.
In case 3, any branch where I found a move by blacks in ply d-1 that gives an score of more than 100 after whites move in ply d will be cut and not be considered cause blacks have other option where whites could reach a maximum score of 100.
In case 4, any branch where I found a move by whites in ply d-1 that gives an score of less than 100 after blacks move in ply d will be cut and not be considered cause whites never will choice it cause have other option where whites could asure an score of 100.
The only value I considered all the time, is the same single "100" (in fact could be changing while the search but is always just one value). Not two differents values (alpha and beta).
Once I have the value at d-1, I´ll do the same for d-2 depth and so on till reach d=1.
In case you have time to read and try to understand it, seems to be a wrong algorithm or just more complicated one than alpha beta?
https://chessprogramming.wikispaces.com/Beta-Cutoff
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.