Did you see and understand my image?
Could when you have time make "by hand" the same tree and say wichs leaf nodes are evaluated using alpha beta?
Sorry, I have seen it but I do not fully understand it. In which order are nodes evaluated, top-down or bottom-up? Usually we go left to right ... Also I do not understand why there are some gaps and why there is no visible root node.
There are lots of examples for alpha-beta trees which are far better than I could create so you'd better rely on these instead
You are right, better I look for an example in the web and compare my program wth it.!
I found 4 cases, with depth 4 and two branchs emerging from each node, and the nodes needed to be evaluated with my algorithm and in the image are the same.
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. However, the worst case running time is O(N^2).
...
Let me know if I understand correctly.
The idea is:
-1º: Generate moves and store them just in the same order you generate them.
-2º: Go through all moves stored one by one without change any order, just looking at its values and at the end of all the path, load the one with high value.
-3º: Make the move you just loaded.
-4º: If this move do not made a cutoff, came back to the list and go trohugh all this again and load the second best move.
-5º: Make this last loaded move.
-And so on.
Luis Babboni wrote:
-2º: Go through all moves stored one by one without change any order, just looking at its values and at the end of all the path, load the one with high value.
And swap this move to position 0 of the list. So the best move now is at position 0. The move that was at position 0 before is at the position where the best move was before.
-4º: If this move do not made a cutoff, came back to the list and go trohugh all this again and load the second best move.
Nearly. Since the best move now is at position 0 and you want the second best move, you start at position 1 with your list search. The swapping then of course is done towards position 1.
If that does not give a cut-off either, you do the same with the third-best move. Since the best and second-best moves are at position 0 and 1, you start to search the list at position 2.
This way, your list search will always be the same: search for the best move after a given starting position. Only that the starting position increases.
Luis Babboni wrote:
-2º: Go through all moves stored one by one without change any order, just looking at its values and at the end of all the path, load the one with high value.
And swap this move to position 0 of the list. So the best move now is at position 0. The move that was at position 0 before is at the position where the best move was before.
-4º: If this move do not made a cutoff, came back to the list and go trohugh all this again and load the second best move.
Nearly. Since the best move now is at position 0 and you want the second best move, you start at position 1 with your list search. The swapping then of course is done towards position 1.
If that does not give a cut-off either, you do the same with the third-best move. Since the best and second-best moves are at position 0 and 1, you start to search the list at position 2.
This way, your list search will always be the same: search for the best move after a given starting position. Only that the starting position increases.
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. However, the worst case running time is O(N^2).
...
Let me know if I understand correctly.
The idea is:
-1º: Generate moves and store them just in the same order you generate them.
-2º: Go through all moves stored one by one without change any order, just looking at its values and at the end of all the path, load the one with high value.
-3º: Make the move you just loaded.
-4º: If this move do not made a cutoff, came back to the list and go trohugh all this again and load the second best move.
-5º: Make this last loaded move.
-And so on.
I´m right?
At last, I tried a different idea* that results in between 5% and 10% faster overall engine speed but not apreciated improve in skill level.... Not sounds oddly? I was las 4 days searching for a bug but I could not found any. For my dissapointing, just seems that this around 10% more moves analyzed in the same time, are not enough to improve the engine level.
*: the idea is to store generated moves just ordered.
I could do it cause I have just 21 order levels, so after each generated move, instead of order it comparing it with all previous generated moves ordered before after each previous generated move as my previous version did, now the engine just knows where to directly store it in a 21 levels shelves.
Luis Babboni wrote:At last, I tried a different idea* that results in between 5% and 10% faster overall engine speed but not apreciated improve in skill level.... Not sounds oddly? I was las 4 days searching for a bug but I could not found any. For my dissapointing, just seems that this around 10% more moves analyzed in the same time, are not enough to improve the engine level.
Not unexpected at all. You do not improve engine strength in a measurable way by improving its raw speed by 10%. As a rule of thumb, people found out that doubling the speed (i.e. speed +100%) gives a strength improvement of about 70 to 100 Elo points, where weaker engines might get a slightly higher improvement from it than stronger engines. The reason is simple: doubling the speed lets the engine search somewhat deeper in the same time which improves move decisions to a certain degree, and weaker engines usually benefit more from searching N plies deeper than stronger engines which already have a considerably higher search depth. Speeding up by sqrt(2) = 1.414... results in gaining about half of these 70 to 100 Elo points. Now you can calculate approximately how much you can expect from a 10% speedup (not more than 10-15 Elo points), and which Elo differences you are able to measure correctly taking into account error bars based on the number of games you can play.
Therefore trying to improve speed by significantly less than 100% is a no-go for an engine at that level, in many cases it is a waste of time. There may be some exceptions in case of obvious and simple improvements ("low hanging fruits") or in case of algorithmic improvements that will also help to save testing time (like doubling perft speed by introducing the usual tricks at a remaining depth of 1). But in general you should also consider the additional risk of introducing new bugs that you take by changing your code for speed.
By far the better choice for an engine at a quite low level of strength would be to restructure code and improve its software quality (and testing methods!), since typically a large portion of strength restrictions has its origin in bugs and/or a bad program structure, and another big portion of problems is related to making more or less complex changes that do not improve playing strength (or even make the program play weaker) but not detecting that in the test. And that happens with all types of programs, not just chess engines, and with experienced as well as less experienced programmers.
