Having trouble understanding advanced move ordering techniques

[JVMerlino]

It also seems like your depth 9 output gives 10 PV moves. You seem to be possibly doing some extra work.

Not if there are any extensions (e.g. check), or if the PV is also including moves from the qsearch.

[dangi12012]

A movelist does not exist if you bake your sorting heuristic into the movegenerator itself.
That way no sort is needed before alphabeta recursion - because the leftmost move will probably be good.
Does not answer your question - but its good to keep in mind that the current state of the art TT + Alphabeta is not ideal but a relic of the order of discoveries (like all code is).
Also asking in a forum gives you a status quo answer and does not push new discoveries forward.

[dangi12012]

Good resource:
https://thesai.org/Downloads/Volume5No5 ... ethods.pdf

Also chess is interesting as insofar its really a graph up to and until a pawn moves. Then its a completely new graph (as all previous positions now can never intersect with new positions). Same is true for castling. So two movetypes spawn a subgraph - but every other move is in fact not a tree but a graph. Thats the reason why TT is so important - to find arrows back to a previous position.

[j.t.]

A movelist does not exist if you bake your sorting heuristic into the movegenerator itself.

Even if that would be a very little bit faster than how sorting is done today, it would produce code that is not very maintainable. The move generation shouldn't have anything to do with how moves are sorted for searching, from a software engineering standpoint. And I would argue that for new discoveries, this standpoint is quite relevant, as you can only easily try out new ideas, if the code you're working with is not a monolith.

[dangi12012]

You want to truly improve computerchess to a new level? Devel in existing stuff up to and until full understanding is reached and then look forward - currently known bottlenecks and issues yet to be solved. For example this paragraph from 2014 still holds true 8 years later:

Other programming libraries were designed to run parallel
algorithms in GPU rather than CPU, including CUDA [23].
However, few algorithms were implemented using these
libraries because of the complexity of programming search
trees using these libraries. On the other hand, the implemented
algorithms that tested on GPU showed a better speedup than
the CPU

If you were to create a treesearch algorithm that can run on 1000s of threads concurrently that would be one such thing. As a not so broadly known fact is that Compute Kernels that run Vulkan can run on the CPU too - and the GPU and even concurrently. This is more multiplatform than C++ because you can run such code in browsers almost natively.
Parallel MCTS looks promising for me to replace what is currently used (Alphabeta + TT + all the domain ordering techniques you are asking about).

Also look how TT is currently used - all that zobrist hashing is a replacement for a game graph in memory. A indirect access method into what would otherwise be direct access into a graph.

[j.t.]

Parallel MCTS looks promising for me to replace what is currently used (Alphabeta + TT + all the domain ordering techniques you are asking about).

Also, look how TT is currently used - all that zobrist hashing is a replacement for a game graph in memory. An indirect access method into what would otherwise be direct access into a graph.

What leave evaluation are you specifically thinking about when talking about MCTS? Classical playouts, or neural networks? In chess, MTCS is often used when the leave evaluation is very slow. In these cases, it makes more sense to try to parallelize this evaluation instead of the tree search (like Lc0 already does).

And a TT is not only an approximate representation of a graph, it also caches identical positions at different positions in the graph (that's why it is called "transposition table"). EDIT: I didn't see your earlier comment and assumed mistakenly that you mean tree by graph.

[Mike Sherwin]

You want to truly improve computerchess to a new level? Devel in existing stuff up to and until full understanding is reached and then look forward - currently known bottlenecks and issues yet to be solved. For example this paragraph from 2014 still holds true 8 years later:

Other programming libraries were designed to run parallel
algorithms in GPU rather than CPU, including CUDA [23].
However, few algorithms were implemented using these
libraries because of the complexity of programming search
trees using these libraries. On the other hand, the implemented
algorithms that tested on GPU showed a better speedup than
the CPU

If you were to create a treesearch algorithm that can run on 1000s of threads concurrently that would be one such thing. As a not so broadly known fact is that Compute Kernels that run Vulkan can run on the CPU too - and the GPU and even concurrently. This is more multiplatform than C++ because you can run such code in browsers almost natively.
Parallel MCTS looks promising for me to replace what is currently used (Alphabeta + TT + all the domain ordering techniques you are asking about).

Also look how TT is currently used - all that zobrist hashing is a replacement for a game graph in memory. A indirect access method into what would otherwise be direct access into a graph.

Pure MCTS is not IMHO where to look as it is not intelligent. Pure alpha-beta should be a tool and not the whole answer. What if a whole game is played using a-b that is one move plus Qsearch. Then intelligence is brought to MCTS. Each move of the game is stored in the TT and its Reinforcement Learning scores are adjusted. For multithreaded searchers each moves RL scores will have to be made fuzzy with a window and some randomness added so all the threads won't search the exact same line. Now that would be something worth testing!

[pedrojdm2021]

You want to truly improve computerchess to a new level? Devel in existing stuff up to and until full understanding is reached and then look forward - currently known bottlenecks and issues yet to be solved. For example this paragraph from 2014 still holds true 8 years later:

Other programming libraries were designed to run parallel
algorithms in GPU rather than CPU, including CUDA [23].
However, few algorithms were implemented using these
libraries because of the complexity of programming search
trees using these libraries. On the other hand, the implemented
algorithms that tested on GPU showed a better speedup than
the CPU

If you were to create a treesearch algorithm that can run on 1000s of threads concurrently that would be one such thing. As a not so broadly known fact is that Compute Kernels that run Vulkan can run on the CPU too - and the GPU and even concurrently. This is more multiplatform than C++ because you can run such code in browsers almost natively.
Parallel MCTS looks promising for me to replace what is currently used (Alphabeta + TT + all the domain ordering techniques you are asking about).

Also look how TT is currently used - all that zobrist hashing is a replacement for a game graph in memory. A indirect access method into what would otherwise be direct access into a graph.

I've read a little about Monte Carlo Tree Search, and it seems that alpha-beta / negamax is still better, MCTS seems to rely in more like brute force computing, rather than smart search. witch that can result in a slower search. That's why i'm not even interested in studying that alternative to alphaBeta and it's derivates.

Also, i'm currently not interested on making an engine run in multi thread format, i'm only doing single thread for now, and that is enough for me right now

Source: https://towardsdatascience.com/monte-ca ... 8a917a8baa

[pedrojdm2021]

You want to truly improve computerchess to a new level? Devel in existing stuff up to and until full understanding is reached and then look forward - currently known bottlenecks and issues yet to be solved. For example this paragraph from 2014 still holds true 8 years later:

Other programming libraries were designed to run parallel
algorithms in GPU rather than CPU, including CUDA [23].
However, few algorithms were implemented using these
libraries because of the complexity of programming search
trees using these libraries. On the other hand, the implemented
algorithms that tested on GPU showed a better speedup than
the CPU

If you were to create a treesearch algorithm that can run on 1000s of threads concurrently that would be one such thing. As a not so broadly known fact is that Compute Kernels that run Vulkan can run on the CPU too - and the GPU and even concurrently. This is more multiplatform than C++ because you can run such code in browsers almost natively.
Parallel MCTS looks promising for me to replace what is currently used (Alphabeta + TT + all the domain ordering techniques you are asking about).

Also look how TT is currently used - all that zobrist hashing is a replacement for a game graph in memory. A indirect access method into what would otherwise be direct access into a graph.

Pure MCTS is not IMHO where to look as it is not intelligent. Pure alpha-beta should be a tool and not the whole answer. What if a whole game is played using a-b that is one move plus Qsearch. Then intelligence is brought to MCTS. Each move of the game is stored in the TT and its Reinforcement Learning scores are adjusted. For multithreaded searchers each moves RL scores will have to be made fuzzy with a window and some randomness added so all the threads won't search the exact same line. Now that would be something worth testing!

Yes i've already tranposition tables, they help a lot, if i wont have TT my results were much, much worse

[pedrojdm2021]

It also seems like your depth 9 output gives 10 PV moves. You seem to be possibly doing some extra work.

Not if there are any extensions (e.g. check), or if the PV is also including moves from the qsearch.

Yes, i do check extension, is the only extension that i have.