More questions that are on my mind...

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
voyagerOne
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

More questions that are on my mind...

Post by voyagerOne » Sun Apr 01, 2012 6:19 pm

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
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: More questions that are on my mind...

Post by jwes » Sun Apr 01, 2012 7:27 pm

voyagerOne wrote: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.
voyagerOne wrote: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
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: More questions that are on my mind...

Post by micron » Mon Apr 02, 2012 4:19 am

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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: More questions that are on my mind...

Post by diep » Mon Apr 02, 2012 11:36 am

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
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: More questions that are on my mind...

Post by voyagerOne » Mon Apr 02, 2012 1:27 pm

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
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: More questions that are on my mind...

Post by voyagerOne » Mon Apr 02, 2012 1:30 pm

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

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: More questions that are on my mind...

Post by bob » Mon Apr 02, 2012 4:08 pm

voyagerOne wrote: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
Posts: 4458
Joined: Tue Feb 28, 2012 10:56 pm

Re: More questions that are on my mind...

Post by syzygy » Mon Apr 02, 2012 9:39 pm

voyagerOne wrote: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.

Post Reply