More questions that are on my mind...

[voyagerOne]

Please enlighten me experts!

Is it only important to have move ordering on the PV line? (i.e once you get your alpha, it does not matter if the rest of the moves are ordered poorly or good...it will finish the depth near the same time)

When you sort moves by scores. Do you just sort the root moves? Or moves from every parent? How do you go about getting the root scores?

Most the articles I read about Null Moves it mentions that you will skip your turn and have the opponent play a 2nd move. Can this be applied reverse? (i.e. you skip your opponent move and you play a 2nd move)

Thanks in advance!

P.S. If you have a chance checkout my program! Its quite challenging considering its just alpha/beta.

www.mytopcoder.com/gmol

[jwes]

Please enlighten me experts!

Is it only important to have move ordering on the PV line? (i.e once you get your alpha, it does not matter if the rest of the moves are ordered poorly or good...it will finish the depth near the same time)

It is important at all cut nodes, or in effect at all nodes, since if you know for certain a node is an all node, you should not search it at all.

Most the articles I read about Null Moves it mentions that you will skip your turn and have the opponent play a 2nd move. Can this be applied reverse? (i.e. you skip your opponent move and you play a 2nd move)

You already did that on the previously ply.

[micron]

When you sort moves by scores. Do you just sort the root moves? Or moves from every parent? How do you go about getting the root scores?

A preliminary sort of the root moves is worthwhile and easy. Note the absence of alpha and beta variables in the pseudocode below; they are fixed at -/+INFINITY so that you get an exact score (not a bound) for all moves.

Code: Select all

for ( j = 0; j < nRootMoves; j++ ) &#123;
  Make&#40; rootMoves&#91;j&#93; );
  scores&#91;j&#93; = -QSearch&#40; pos, -INFINITY, INFINITY );
  Unmake;
&#125;
SortDescendingByScore&#40; rootMoves, scores );

After the preliminary sort, proceed straight to iterative deepening. As usual in ID, you shift the best move from each iteration to become the first move in the next.

[diep]

Bill, your link doesn't work here.

Note it is important to sort everywhere, as you never know whether you can get a cutoff.

You don't know in advance what is a cutnode nor whether something in advance is an allnode.

There is different strategies followed over the course of years. For example i remember how Joost Buijs once told he's sorting just the first 5 moves and the rest is semi-random, simply to keep a high nps and not lose system time to move ordering.

Not sure whether he's still doing that.

15 years ago there was more creativity in computerchess there.

In Diep i always used the slowest manner of sorting, in O ( n^2 ), i pick each move from the list, yet at out of order processors it is a predictable way of doing things...

Averaged for each move that's O ( n ), but of course the total for 1 position is O ( n ^ 2 ), in c ase it's an allnode.

if you really start optimizing this indepth it's possible you'l find lossless something faster than the simple method i'm using in Diep there.

What i do you can call PickSort() - even Gnuchess was already using that.

Sjeng is splitting the moves from the scores, in 2 separated arrays. That seems not very cache efficient at first sight, but amazingly intel c++ 11.x knows how to vectorize this in SIMD.

[voyagerOne]

Thank you all for helping me out. My follow up question is:
At what depth do you stop scoring the root move? The search will perform quite slow if you just have +/- infinite for every root move during deeper searches...

[voyagerOne]

@diep: Its a Java applet...you need Java to run it.

[bob]

Please enlighten me experts!

Is it only important to have move ordering on the PV line? (i.e once you get your alpha, it does not matter if the rest of the moves are ordered poorly or good...it will finish the depth near the same time)

It is critical at every last CUT node, which appear throughout the tree at every other ply. You always want to search a move at a CUT node that produces a cutoff. You don't need to search the "best move" first. But you do need to search a move that is good enough to cause a cutoff first. Otherwise you will have to search others and blow the size of the tree up.

When you sort moves by scores. Do you just sort the root moves? Or moves from every parent? How do you go about getting the root scores?

Most the articles I read about Null Moves it mentions that you will skip your turn and have the opponent play a 2nd move. Can this be applied reverse? (i.e. you skip your opponent move and you play a 2nd move)

Thanks in advance!

P.S. If you have a chance checkout my program! Its quite challenging considering its just alpha/beta.

www.mytopcoder.com/gmol

[syzygy]

Most the articles I read about Null Moves it mentions that you will skip your turn and have the opponent play a 2nd move. Can this be applied reverse? (i.e. you skip your opponent move and you play a 2nd move)

If I understand you correctly (but maybe I don't), by "opponent" you mean the side that is not to move at the root node of the search (i.e. in the position currently on the board).

In the articles you read, "opponent" refers to the side that is not to move at the current node in the tree. During one and the same search, the side that is the "opponent" flips between black and white from (parent) node to (child) node (except for null moves, obviously).

It would be possible to do only null moves for the side that is to move at the root node, but that would result in an asymmetrical search. I believe that nowadays most if not all engines use a symmetrical search algorithm.