hgm wrote:Indeed, that is true. But applying the eeffects of the disappearance of two Pawns and re-appearance of one of them elsewhere is still much less work than creating an empty scratch board, and letting 8 Pawns appear there. Plus that only a small fraction of the moves move or capture a Pawn. Most moves might be Pawn moves in the initial position, but that quickly reverses once you develop pieces and Pawn chains start interlocking.
Total number of (moves = connections) in a tree is equal to total number of nodes minus one. For root doesn't count.
So for the leaves of a binary tree it is 8 * k * power(2, d)
Against for the moves of a binary tree:
power(2, d+ 1) -1 unmake operations + power(2, d+ 1) -1 make operations (= pawn captures + pawn moves)
Yes, so binary trees have a comparatively small fraction of their nodes in the leaves. The nodes-1 rule also holds for other branching factors. In a search tree for Chess almost all nodes are QS nodes, where you do evaluate to see if you can stand pat, and the number of Makes/Unmakes is hardly larger.
hgm wrote:Indeed, that is true. But applying the eeffects of the disappearance of two Pawns and re-appearance of one of them elsewhere is still much less work than creating an empty scratch board, and letting 8 Pawns appear there. Plus that only a small fraction of the moves move or capture a Pawn. Most moves might be Pawn moves in the initial position, but that quickly reverses once you develop pieces and Pawn chains start interlocking.
Total number of (moves = connections) in a tree is equal to total number of nodes minus one. For root doesn't count.
So for the leaves of a binary tree it is 8 * k * power(2, d)
Against for the moves of a binary tree:
power(2, d+ 1) -1 unmake operations + power(2, d+ 1) -1 make operations (= pawn captures + pawn moves)
[Let's make it less clear.]
If 1 out of p moves is a pawn capture or pawn move then we have
k2 * bf * (power(bf, D-1) -1) / p against 8 * k1 * power(bf, D-1)
when disregarding unmake moves.
Let bf = 4 and power(bf, D-1) -1 ~= power(bf, D-1) we get
I think you can apply a very simple performance improvement for your "mobility to squares that are not attacked by an enemy pawn" evaluation. Even if your board representation and move generation does not use bitboards you can simply create two pawn bitboards, one for white and one for black. That should be doable with negligible effort, and you do not even need to bother with calculating it incrementally or not (just calculate it always from scratch in the beginning of eval). Then you can use these efficiently for many purposes within your evaluation function, for instance:
- derive "attacked by [white/black] pawns" bitboards from original pawn bitboards with simple shift/and/or/masking operations, and look it up during mobility evaluation;
- find passed pawns;
- find open and semi-open files;
- find isolated pawns, multiple pawns;
- ...
The first one should already improve your evaluation performance.
I think you can apply a very simple performance improvement for your "mobility to squares that are not attacked by an enemy pawn" evaluation. Even if your board representation and move generation does not use bitboards you can simply create two pawn bitboards, one for white and one for black. That should be doable with negligible effort, and you do not even need to bother with calculating it incrementally or not (just calculate it always from scratch in the beginning of eval). Then you can use these efficiently for many purposes within your evaluation function, for instance:
- derive "attacked by [white/black] pawns" bitboards from original pawn bitboards with simple shift/and/or/masking operations, and look it up during mobility evaluation;
- find passed pawns;
- find open and semi-open files;
- find isolated pawns, multiple pawns;
- ...
The first one should already improve your evaluation performance.
Sven
Skipper was already using bit boards but not for move generation or mobility. I am busy with adding mobility using the new AttackedByPawns bit boards. Might be that the other bit boards operations during evaluation need to be rewritten if they just can reuse the AttackedByPawns bit boards.
hgm wrote:Indeed, that is true. But applying the eeffects of the disappearance of two Pawns and re-appearance of one of them elsewhere is still much less work than creating an empty scratch board, and letting 8 Pawns appear there. Plus that only a small fraction of the moves move or capture a Pawn. Most moves might be Pawn moves in the initial position, but that quickly reverses once you develop pieces and Pawn chains start interlocking.
Total number of (moves = connections) in a tree is equal to total number of nodes minus one. For root doesn't count.
So for the leaves of a binary tree it is 8 * k * power(2, d)
Against for the moves of a binary tree:
power(2, d+ 1) -1 unmake operations + power(2, d+ 1) -1 make operations (= pawn captures + pawn moves)
[Let's make it less clear.]
If 1 out of p moves is a pawn capture or pawn move then we have
k2 * bf * (power(bf, D-1) -1) / p against 8 * k1 * power(bf, D-1)
when disregarding unmake moves.
Let bf = 4 and power(bf, D-1) -1 ~= power(bf, D-1) we get
k2 /p against 2 * k1
Looks like k2 ~<= 3 * k1. Adding from scratch is just a bitwise | (or)operation.
