Tree dumping

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

jwes
Posts: 778
Joined: Sat Jul 01, 2006 7:11 am

Re: Tree dumping

Post by jwes »

Robert Pope wrote:I expect the issue is in the search somewhere, like Uri said. I thought I had reasonable ordering rules, and I thought I had null-move working, but we'll see.

Qsearch doesn't seem to be the culprit -- I turned it off and only saved 50%, which doesn't look too unreasonable, but that still leaves 2M nodes too many.

I've already identified one improvement: when I fail high, I re-search with a wider window, but I didn't reorder to move the fail-high move to the front of the list.
Something seems really wrong with your search. Either there is some explosion of extensions, or your move ordering is worse than random. Two suggestions:
1. Put in counters and statistics, e.g. fh first percentage, null move cutoff percentage, and counters for each extension.
2. Try moving down the PV in your test position and see if the large discrepancy in nodes remains. Maybe you can get the number of nodes down to a small enough number that you can search through them.
Top
Robert Pope
Posts: 558
Joined: Sat Mar 25, 2006 8:27 pm

Re: Tree dumping

Post by Robert Pope »

Okay, I'm looking at a trace of WAC232 (iteration 3) and I'm trying to understand what I am seeing.

Here's are two pieces of the output:

Code: Select all

1  Qa4 d: 3.50 [  -0.43,   0.37] n:1066 SearchRoot(11)
  2  Rxb8 d: 2.50 [  -0.37,   0.43] n:1067 Search(1)
    3  null d: 1.50 [   0.36,   0.37] n:1068 Search(0)
    3  Qxc2 d: 1.50 [  -0.43,   0.37] n:1069 Search(1)
      4  Rxb1+ d: 0.00 [  -0.25,   0.43] n:1070 quiesce(3)
        5  Qxb1 d: 0.00 [  -0.43,   0.25] n:1071 quiesce(3)
        5  Qc2xc7 d: 0.00 [  -0.03,   0.25] n:1072 quiesce(3)
    3  Rxb8 d: 1.50 [  -0.03,   0.37] n:1073 Search(3)
    3  Rb7 d: 1.50 [  -0.03,   0.37] n:1074 Search(10)
    3  Rb6 d: 1.50 [  -0.03,   0.37] n:1075 Search(10)
    3  Rb5 d: 1.50 [  -0.03,   0.37] n:1076 Search(10)
    3  Rb4 d: 1.50 [  -0.03,   0.37] n:1077 Search(10)
    3  Rb3 d: 1.50 [  -0.03,   0.37] n:1078 Search(10)
    3  Rb2 d: 1.50 [  -0.03,   0.37] n:1079 Search(10)
    3  Rf1 d: 1.50 [  -0.03,   0.37] n:1080 Search(10)
    3  Re1 d: 1.50 [  -0.03,   0.37] n:1081 Search(10)
    3  Rd1 d: 1.50 [  -0.03,   0.37] n:1082 Search(10)
    3  Rc1 d: 1.50 [  -0.03,   0.37] n:1083 Search(10)
    3  Ra1 d: 1.50 [  -0.03,   0.37] n:1084 Search(10)
    3  Qe8 d: 1.50 [  -0.03,   0.37] n:1085 Search(10)
    3  Qa8 d: 1.50 [  -0.03,   0.37] n:1086 Search(10)
    3  Qd7 d: 1.50 [  -0.03,   0.37] n:1087 Search(10)
    3  Qa7 d: 1.50 [  -0.03,   0.37] n:1088 Search(10)
    3  Qc6 d: 1.50 [  -0.03,   0.37] n:1089 Search(10)
    3  Qa6 d: 1.50 [  -0.03,   0.37] n:1090 Search(10)
    3  Qb5 d: 1.50 [  -0.03,   0.37] n:1091 Search(10)
    3  Qa5 d: 1.50 [  -0.03,   0.37] n:1092 Search(10)
    3  Qd4 d: 1.50 [  -0.03,   0.37] n:1093 Search(10)
    3  Qc4 d: 1.50 [  -0.03,   0.37] n:1094 Search(10)
    3  Qb4 d: 1.50 [  -0.03,   0.37] n:1095 Search(10)
    3  Qb3 d: 1.50 [  -0.03,   0.37] n:1096 Search(10)
    3  Qa3 d: 1.50 [  -0.03,   0.37] n:1097 Search(10)
    3  Kg1f2 d: 1.50 [  -0.03,   0.37] n:1098 Search(10)
    3  Kh1 d: 1.50 [  -0.03,   0.37] n:1099 Search(10)
    3  Kf1 d: 1.50 [  -0.03,   0.37] n:1100 Search(10)
    3  h4 d: 1.50 [  -0.03,   0.37] n:1101 Search(10)
    3  g4 d: 1.50 [  -0.03,   0.37] n:1102 Search(10)
    3  e5 d: 1.50 [  -0.03,   0.37] n:1103 Search(10)
    3  h3 d: 1.50 [  -0.03,   0.37] n:1104 Search(10)
    3  g3 d: 1.50 [  -0.03,   0.37] n:1105 Search(10)
    3  a3 d: 1.50 [  -0.03,   0.37] n:1106 Search(10)
  2  c5 d: 2.50 [   0.03,   0.43] n:1107 Search(4)
    3  null d: 1.50 [  -0.04,  -0.03] n:1108 Search(0)
    3  Rxe8 d: 1.50 [  -0.04,  -0.03] n:1109 Search(3)
  2  Rxa2 d: 2.50 [   0.03,   0.43] n:1110 Search(10)
    3  null d: 1.50 [  -0.04,  -0.03] n:1111 Search(0)
    3  Rxe8 d: 1.50 [  -0.04,  -0.03] n:1112 Search(3)
      4  Rxa4 d: 0.00 [   0.03,   0.04] n:1113 quiesce(3)
        5  Rxf8# d: 0.00 [  -0.04,  -0.03] n:1114 quiesce(3)
          6  Ra4xe4 d: 0.00 [   0.03,   0.04] n:1115 quiesce(3)
  2  Rxg2+ d: 2.50 [   0.03,   0.43] n:1116 Search(10)
    3  Kxg2 d: 2.50 [  -0.04,  -0.03] n:1117 Search(1)
      4  null d: 1.50 [   0.03,   0.04] n:1118 Search(0)
      4  Rxb8 d: 1.50 [   0.03,   0.04] n:1119 Search(3)
        5  Rxb8 d: 0.00 [  -0.04,  -0.03] n:1120 quiesce(3)
          6  Qxb8 d: 0.00 [   0.03,   0.04] n:1121 quiesce(3)
      4  c5 d: 1.50 [   0.03,   0.04] n:1122 Search(8)
      4  Rxe4 d: 1.50 [   0.03,   0.04] n:1123 Search(10)
      4  Re5 d: 1.50 [   0.03,   0.04] n:1124 Search(10)
      4  Re6 d: 1.50 [   0.03,   0.04] n:1125 Search(10)
      4  Re7 d: 1.50 [   0.03,   0.04] n:1126 Search(10)
      4  Rc8 d: 1.50 [   0.03,   0.04] n:1127 Search(10)
      4  Rd8 d: 1.50 [   0.03,   0.04] n:1128 Search(10)
      4  Qe7 d: 1.50 [   0.03,   0.04] n:1129 Search(10)
      4  Qf7 d: 1.50 [   0.03,   0.04] n:1130 Search(10)
      4  Qg8 d: 1.50 [   0.03,   0.04] n:1131 Search(10)
      4  Kh8h7 d: 1.50 [   0.03,   0.04] n:1132 Search(10)
      4  Kg8 d: 1.50 [   0.03,   0.04] n:1133 Search(10)
      4  d5 d: 1.50 [   0.03,   0.04] n:1134 Search(10)
      4  f5 d: 1.50 [   0.03,   0.04] n:1135 Search(10)
      4  h5 d: 1.50 [   0.03,   0.04] n:1136 Search(10)
      4  c6 d: 1.50 [   0.03,   0.04] n:1137 Search(10)
  2  Rxe4 d: 2.50 [   0.03,   0.43] n:1138 Search(10)
    3  null d: 1.50 [  -0.04,  -0.03] n:1139 Search(0)
    3  Qxe4 d: 1.50 [  -0.04,  -0.03] n:1140 Search(3)
      4  Rxa2 d: 0.00 [   0.03,   0.04] n:1141 quiesce(3)
  2  Rc1+ d: 2.50 [   0.03,   0.43] n:1142 Search(10)
    3  Rxc1 d: 2.50 [  -0.04,  -0.03] n:1143 Search(1)
      4  null d: 1.50 [   0.03,   0.04] n:1144 Search(0)
      4  Rxb8 d: 1.50 [   0.03,   0.04] n:1145 Search(3)
        5  Rxc7 d: 0.00 [  -0.04,  -0.03] n:1146 quiesce(3)
      4  c5 d: 1.50 [   0.03,   0.04] n:1147 Search(8)
      4  Rxe4 d: 1.50 [   0.03,   0.04] n:1148 Search(10)
      4  Re5 d: 1.50 [   0.03,   0.04] n:1149 Search(10)
      4  Re6 d: 1.50 [   0.03,   0.04] n:1150 Search(10)
      4  Re7 d: 1.50 [   0.03,   0.04] n:1151 Search(10)
      4  Rc8 d: 1.50 [   0.03,   0.04] n:1152 Search(10)
      4  Rd8 d: 1.50 [   0.03,   0.04] n:1153 Search(10)
...
...
1  e5 d: 3.50 [  -0.03,   0.37] n:1571 SearchRoot(11)
  2  null d: 2.50 [   0.02,   0.03] n:1572 Search(0)
  2  Rxb8 d: 2.50 [   0.02,   0.03] n:1573 Search(1)
    3  null d: 1.50 [  -0.03,  -0.02] n:1574 Search(0)
    3  Rxb8 d: 1.50 [  -0.03,  -0.02] n:1575 Search(3)
    3  exd6 d: 1.50 [  -0.03,  -0.02] n:1576 Search(3)
    3  exf6 d: 1.50 [  -0.03,  -0.02] n:1577 Search(3)
    3  Qa4 d: 1.50 [  -0.03,  -0.02] n:1578 Search(8)
    3  Qxd6 d: 1.50 [  -0.03,  -0.02] n:1579 Search(10)
    3  Rb7 d: 1.50 [  -0.03,  -0.02] n:1580 Search(10)
    3  Rb6 d: 1.50 [  -0.03,  -0.02] n:1581 Search(10)
    3  Rb5 d: 1.50 [  -0.03,  -0.02] n:1582 Search(10)
    3  Rb4 d: 1.50 [  -0.03,  -0.02] n:1583 Search(10)
    3  Rb3 d: 1.50 [  -0.03,  -0.02] n:1584 Search(10)
    3  Rb2 d: 1.50 [  -0.03,  -0.02] n:1585 Search(10)
    3  Rf1 d: 1.50 [  -0.03,  -0.02] n:1586 Search(10)
    3  Re1 d: 1.50 [  -0.03,  -0.02] n:1587 Search(10)
    3  Rd1 d: 1.50 [  -0.03,  -0.02] n:1588 Search(10)
    3  Rc1 d: 1.50 [  -0.03,  -0.02] n:1589 Search(10)
    3  Ra1 d: 1.50 [  -0.03,  -0.02] n:1590 Search(10)
    3  Qc8 d: 1.50 [  -0.03,  -0.02] n:1591 Search(10)
    3  Qa8 d: 1.50 [  -0.03,  -0.02] n:1592 Search(10)
    3  Qb7 d: 1.50 [  -0.03,  -0.02] n:1593 Search(10)
    3  Qa7 d: 1.50 [  -0.03,  -0.02] n:1594 Search(10)
    3  Qc6 d: 1.50 [  -0.03,  -0.02] n:1595 Search(10)
    3  Qb6 d: 1.50 [  -0.03,  -0.02] n:1596 Search(10)
    3  Qb5 d: 1.50 [  -0.03,  -0.02] n:1597 Search(10)
    3  Qa5 d: 1.50 [  -0.03,  -0.02] n:1598 Search(10)
    3  Qc4 d: 1.50 [  -0.03,  -0.02] n:1599 Search(10)
    3  Qd3 d: 1.50 [  -0.03,  -0.02] n:1600 Search(10)
    3  Qa3 d: 1.50 [  -0.03,  -0.02] n:1601 Search(10)
    3  Qe2 d: 1.50 [  -0.03,  -0.02] n:1602 Search(10)
    3  Qf1 d: 1.50 [  -0.03,  -0.02] n:1603 Search(10)
    3  Kg1f2 d: 1.50 [  -0.03,  -0.02] n:1604 Search(10)
    3  Kh1 d: 1.50 [  -0.03,  -0.02] n:1605 Search(10)
    3  Kf1 d: 1.50 [  -0.03,  -0.02] n:1606 Search(10)
    3  h4 d: 1.50 [  -0.03,  -0.02] n:1607 Search(10)
    3  g4 d: 1.50 [  -0.03,  -0.02] n:1608 Search(10)
    3  a4 d: 1.50 [  -0.03,  -0.02] n:1609 Search(10)
    3  e6 d: 1.50 [  -0.03,  -0.02] n:1610 Search(10)
    3  h3 d: 1.50 [  -0.03,  -0.02] n:1611 Search(10)
    3  g3 d: 1.50 [  -0.03,  -0.02] n:1612 Search(10)
    3  a3 d: 1.50 [  -0.03,  -0.02] n:1613 Search(10)
1  Qc6 d: 3.50 [  -0.03,   0.37] n:1614 SearchRoot(11)
  2  null d: 2.50 [   0.02,   0.03] n:1615 Search(0)
  2  Rxc6 d: 2.50 [   0.02,   0.03] n:1616 Search(1)
    3  null d: 1.50 [  -0.03,  -0.02] n:1617 Search(0)
    3  Rxe8 d: 1.50 [  -0.03,  -0.02] n:1618 Search(3)
    3  R8b4 d: 1.50 [  -0.03,  -0.02] n:1619 Search(8)
    3  Rd8 d: 1.50 [  -0.03,  -0.02] n:1620 Search(10)
    3  Rc8 d: 1.50 [  -0.03,  -0.02] n:1621 Search(10)
    3  Ra8 d: 1.50 [  -0.03,  -0.02] n:1622 Search(10)
    3  R8b7 d: 1.50 [  -0.03,  -0.02] n:1623 Search(10)
    3  R8b6 d: 1.50 [  -0.03,  -0.02] n:1624 Search(10)
    3  R8b5 d: 1.50 [  -0.03,  -0.02] n:1625 Search(10)
    3  R8b3 d: 1.50 [  -0.03,  -0.02] n:1626 Search(10)
    3  R8b2 d: 1.50 [  -0.03,  -0.02] n:1627 Search(10)
    3  R1b7 d: 1.50 [  -0.03,  -0.02] n:1628 Search(10)
    3  R1b6 d: 1.50 [  -0.03,  -0.02] n:1629 Search(10)
    3  R1b5 d: 1.50 [  -0.03,  -0.02] n:1630 Search(10)
    3  R1b4 d: 1.50 [  -0.03,  -0.02] n:1631 Search(10)
    3  R1b3 d: 1.50 [  -0.03,  -0.02] n:1632 Search(10)
    3  R1b2 d: 1.50 [  -0.03,  -0.02] n:1633 Search(10)
    3  Rf1 d: 1.50 [  -0.03,  -0.02] n:1634 Search(10)
    3  Re1 d: 1.50 [  -0.03,  -0.02] n:1635 Search(10)
    3  Rd1 d: 1.50 [  -0.03,  -0.02] n:1636 Search(10)
    3  Rc1 d: 1.50 [  -0.03,  -0.02] n:1637 Search(10)
    3  Ra1 d: 1.50 [  -0.03,  -0.02] n:1638 Search(10)
    3  Kf2 d: 1.50 [  -0.03,  -0.02] n:1639 Search(10)
    3  Kh1 d: 1.50 [  -0.03,  -0.02] n:1640 Search(10)
    3  Kf1 d: 1.50 [  -0.03,  -0.02] n:1641 Search(10)
    3  h4 d: 1.50 [  -0.03,  -0.02] n:1642 Search(10)
    3  g4 d: 1.50 [  -0.03,  -0.02] n:1643 Search(10)
    3  a4 d: 1.50 [  -0.03,  -0.02] n:1644 Search(10)
    3  e5 d: 1.50 [  -0.03,  -0.02] n:1645 Search(10)
    3  h3 d: 1.50 [  -0.03,  -0.02] n:1646 Search(10)
    3  g3 d: 1.50 [  -0.03,  -0.02] n:1647 Search(10)
    3  a3 d: 1.50 [  -0.03,  -0.02] n:1648 Search(10)
1. It seems that at after the first root move is searched, then at depth 2, the first move tried is always a null-move (e.g. n=1615). But why wasn't a null-move tried first on the first rootmove (n=1067)?

2. Can someone talk me through what is happening with the A-B bounds for n=1110-1115 or 1116-1125? Here's what it looks like to me:
A. After trying Rxb8 and c5 at depth 2, the alpha-beta window has shrunk to [0.03,0.43].
B. We make Rxa2 (n=1110) and search its successors. I would have expected the window to flip to [-0.43,-0.03] for ply 3.
C. We do a null move at ply 3 and search a minimal window [-0.04,-0.03] to see if we can stand pat (n=1111).
D. I don't think the null-move made a cut-off because we search another move at ply 3 (Rxe8 n=1112).
E. We search Rxe8, which ends up being a cut node, so we don't need to search any more ply 3 nodes.

Am I reading the trace right? Why did Rxe8 get searched with a [-0.04,-0.03] window? I would have expected the non-null-moves to begin with [-0.43,-0.03] as the alpha-beta bounds.
Top
Robert Pope
Posts: 558
Joined: Sat Mar 25, 2006 8:27 pm

Re: Tree dumping

Post by Robert Pope »

I'm at least 80% there, with just a couple changes. I can't believe it made such a difference:

1. I discovered I had been limiting null-moves to ply 4 and deeper when my 3 ply search didn't have a single null-move cutoff. After looking at Crafty, I brought it down to ply 2.
2. After a fail-high, I wasn't re-ordering. Now I put the fail-high move at the front.

Original program to complete ply 6: 4,045,000 nodes
Null-move at lower plies: 1,675,504 nodes
Search fail-high move first: 667,566 nodes

Still 8-10x as many nodes as Crafty, but that's an incredible improvement! I now get to a given depth in about 1/2 the time, and the new version is consistently beating the old one.
Top

Return to “Computer Chess Club: Programming and Technical Discussions”