Speed vs ELO gain

[hgm]

Yes, in case you do something there it makes sense to count it as a node. My initial remark was only intended to warn against comparing the nps obtained this way with that of another program, which might very well not count the same way as you do (e.g. count MoveGens in stead of MakeMoves).

MakeMoves in general are way cheaper than MoveGens, so if you count MakeMoves, you are likely to get way higher nps. If you would count MoveGens, you would probably be down from 28 Mnps to 1 Mnps. You might be able to increase that to 2-3 Mnps by not making the final moves (if you have an alternative way for determining their legality, and you are not counting the MakeMoves anyway).

[jacobbl]

Thanks to everyone for all your answers, but I still can't understand how you get these high nodecounts.

I put a knight on D5 (8 legal moves), and did a popcount 10.000.000 times. thes took 1.4 seconds. This makes it quite impossible to reach 10MN/S.

Maybe my popcount function is very bad:

Function AntTrekk(ByVal lTrekk As ULong) As Byte
Dim led As ULong

AntTrekk = 0
While lTrekk
If lTrekk >> 48 Then
led = LedRuteTabell(lTrekk >> 48) + 48
ElseIf lTrekk >> 32 Then
led = LedRuteTabell(lTrekk >> 32) + 32
ElseIf lTrekk >> 16 Then
led = LedRuteTabell(lTrekk >> 16) + 16
Else
led = LedRuteTabell(lTrekk)
End If

lTrekk = lTrekk And FjernLedTabell(led) 'Removes the lead bit
AntTrekk = AntTrekk + 1
End While
End Function

I also tried:

Function AntTrekk2(ByVal lTrekk As ULong) As Byte
AntTrekk2 = 0
While lTrekk
AntTrekk2 = AntTrekk2 + 1
lTrekk = lTrekk And (lTrekk - 1)
End While
End Function

But this took 5.5 seconds on 10.000.000 popcounts.

Am I doing it all wrong, or is it the lack of inline that is hurting my performance?

How long time does a 10.000.000 popcount (with a population of 8) take for you?

Regards Jacob

[micron]

Code: Select all

int static inline CountBits( BitBoard b )
{
	BitBoard  result, tmp;
	
	asm( "   popcnt  %1, %0  \n\t"
		 :  "=&r" (result), "=&r" (tmp)
		 :  "1" (b)
		 :  "cc" );
	return result;
}

By timing with N = 1000 000 000 calls in a loop, subtracting the time for the loop without CountBits(), and dividing by N, I find that this takes 0.3 ns (one clock cycle).

[micron]

Code: Select all

int AntTrekk2( UInt64 lTrekk ) 
{ 
  int  AntTrekk2 = 0; 
  while ( lTrekk ) 
 { 
    AntTrekk2++; 
    lTrekk &= (lTrekk - 1); 
  } 
  return AntTrekk2; 
}  

With 8 bits set in the input parameter, my measured timing is 7 ns.

For 10 million calls that is 70 ms, which contrasts strikingly with your time of 5.5 s.

[jacobbl]

Thanks for your testing. 70ms is a factor of 80 faster (maybe some different in computer speed, I'm using a 2.00 gHz) than my VB compile. It looks like VB has som limitations which will never make my engine fast

I tried this idea from Dann Corbit:

This can help:
http://msdn.microsoft.com/en-us/library/6t9t5wcf.aspx

but I didn't get any speed gain from it.

Thanks again for your help.

Regards
Jacob

[Don]

It would be faster, but the nodes per second would be a lot slower. Moves are not nodes. What you count now is more accuratey described as moves/sec than as nodes/sec.

Well I guess it is just a matter of opinion. This is the way I do it for almost 34 years now. I count each new position as a node. I don't know how others count their nodes. I don't even understand what your definition of a node exactly means.

A node is a position. If you make a move, you have created a new position or put another way you have created a new node in the graph which represents the game tree. I don't understand how any other definition makes any sense. I know some programs count "end nodes" or positions that are evaluated (and not expanded) which used to give similar numbers, but with the small branching factors of modern chess programs this can be a lot different.

I don't count the root node, as it is not generated by the search, it is provided to the search. Of course this would only make a difference of 1.

The only other ambiguity is whether you count illegal moves that some programs generate. For example some programs make a move, then test to see if the program is in check. Bob Hyatts programs used to wait until the king is captured to resolve the legality of some moves, don't know what he does now. In my view, and this is purely opinion and semantics, those are not nodes. It doesn't seem right to count illegal positions as nodes and compare this to other programs.

Most good programs do a significant amount of work to avoid making a move, in effect they are evaluating a future node although not directly visiting it. Komodo uses the strictest definition, we have to actually create a new board position to call it a node and it has to be a legal position (although we do most of the checking to avoid creating an illegal position it happens occasionally.)

It's difficult to compare nodes per second to other programs because all seem to count differently.

[frankp]

Just to check: so if you make a legal move, decide it is futile, prune and return alpha this is a node?

[Sven]

I am not sure what we are discussing about. For one, you just exactly repeat what I said before: one does not make moves to positions where one doesn't want to do anything, which sugest we agree.

But the point was, do you count moves that you prune (without making them, obviously), as nodes? And if you don't do that in a Chess program, why would you do it in a perft? So I would think that in a perftprogram where you do _not_ make and unmake the counted moves, but only count them, you would not count the moves as nodes. And I am not even sure you disagree with that...

1) Obviously within "perft" nothing will ever get pruned.

2) "perft" is different from regular search in that its target is to calculate a certain number: the number of leaf nodes of a game tree with certain given conditions. Whether you actually make the moves that create these leaves, or optimize for calculation speed and anticipate the correct result by taking the number of generated (legal) moves without making each one, does not matter: in both cases you count the leaf nodes.

In regular search, however, reporting the node count and nps has another intent: to indicate the size of the game tree that was actually traversed within a certain time, a certain number of iterations, ...

Therefore one should not compare the definitions of a node in "perft" and in regular search.

3) Of course I agree that in regular search you do not count positions that are never reached due to pruning of moves as nodes.

Sven

[Milos]

Ernst A. Heinz (2001) found indications of decreasing returns from increasing search in chess:
* 12-ply was 84 ELO points better than 11 ply
* 11-ply was 92 ELO points better than 10 ply
* 10-ply was 115 ELO points better than 9 ply

https://chessprogramming.wikispaces.com ... %20Returns

Ernst Heinz was wrong the same as he was wrong for null move reduction and many other things. In terms of chess development quoting Heinz (or Bob Hyatt) is the same as quoting Isaac Newton in terms of unifying theory in physics.

[bob]

Ernst A. Heinz (2001) found indications of decreasing returns from increasing search in chess:
* 12-ply was 84 ELO points better than 11 ply
* 11-ply was 92 ELO points better than 10 ply
* 10-ply was 115 ELO points better than 9 ply

https://chessprogramming.wikispaces.com ... %20Returns

Ernst Heinz was wrong the same as he was wrong for null move reduction and many other things. In terms of chess development quoting Heinz (or Bob Hyatt) is the same as quoting Isaac Newton in terms of unifying theory in physics.

Where was Heinz wrong with null-move reduction. We came up with the _same_ reduction (3 near the root, 2 near the tips, what he called 'adaptive null-move') independently through testing. When I added checks to Crafty's q-search, I found R=3 was very slightly (emphasis on _slightly_ better). But without the qsearch checks, 2~3 was significantly better.

The only ones that can legitimately say he was wrong are those that have actually run some tests. I have, and I found his results pretty accurate...