Starting with move ordering.

[Henk]

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.

[Ras]

I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".

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:

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.

[Luis Babboni]

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.

Mmm, I´m not sure is like this.
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.

[Luis Babboni]

I´m programming in Free Basic and I do not use any "premade" method. I just make the list and sort it "by hand".

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:

https://rosettacode.org/wiki/Sorting_al ... sort#BASIC
...

Definitevely yes!

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!

[Ras]

Remember I still not use two values, alpha and beta.... at least explicitly.

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.

See here: https://chessprogramming.wikispaces.com/Alpha-Beta

[Ras]

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?

Correct. The extreme case is that you only have one legal move.

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.

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?

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".

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.

[Luis Babboni]

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?

Correct. The extreme case is that you only have one legal move.

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.

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?

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".

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.

My with move ordering version is better than my without move ordering verison in middle game but worst in end games.

[Luis Babboni]

Remember I still not use two values, alpha and beta.... at least explicitly.

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.

See here: https://chessprogramming.wikispaces.com/Alpha-Beta

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.
I said I´m in fault because I still do not have a good proof of what I´m saying.

[Luis Babboni]

Remember I still not use two values, alpha and beta.... at least explicitly.

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.

See here: https://chessprogramming.wikispaces.com/Alpha-Beta

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.
I said I´m in fault because I still do not have a good proof of what I´m saying.

I´ll try to explain again my one value algorithm that works like Alpha Beta two values works (I think):

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?

[Karlo Bala]

Remember I still not use two values, alpha and beta.... at least explicitly.

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.

See here: https://chessprogramming.wikispaces.com/Alpha-Beta

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.
I said I´m in fault because I still do not have a good proof of what I´m saying.

I´ll try to explain again my one value algorithm that works like Alpha Beta two values works (I think):

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?

It looks to me that you are doing only a shallow cutoff (or something very similar - which is far from optimal).

https://chessprogramming.wikispaces.com/Beta-Cutoff