Winboard interface

[H.G.Muller]

The version of micro-Max that I interfaced now (version 3.2, the one on the main page of the uMax website) indeed clears the hash table after every move. It had to, because it did not update the hash key when moving at game level. So the root always has the same hash key (apart from the non-differentially kept terms e.p.-status and side-to-move). This is of course very sub-optimal, even code-wise, but 3.2 really is an obsolete version. (But it is still the best-documented version that is discussed on the website, so I wanted to include a Winboard compatable version of that one.)

In version 4.0 I stream-lined the entire hash handling, switching to a replace-always scheme (shrinking the code). It still did not update the hash key at game level, though, but it does change it on every move such that all entries that were in the table from the previous search are guaranteed to be invalid.

I have experimental versions that do keep the table from previous searches, that didn't take too much extra code (but required a different mechanism of updating the key, in a global variable rather than as a function argument). There are other changes in that version as well (in particular null-move pruning), but I am still not convinced that it works properly.

I hope to put the Winboard-compatible version on my website tonight. What I still want to change is the mechanism of time control. (Now it counts nodes, but Winboard asks it to play at a certain number of seconds, and the conversion factor is CPU-speed dependent. So I will probably have it read the clock directly to make the decision to start a new iteration, which is easy enough, but needs to be calibrated.) Plus that I want to build in a way for the user to control the size of the hash table, from a command-line argument.

[Guenther Simon]

The version of micro-Max that I interfaced now (version 3.2, the one on the main page of the uMax website) indeed clears the hash table after every move. It had to, because it did not update the hash key when moving at game level. So the root always has the same hash key (apart from the non-differentially kept terms e.p.-status and side-to-move). This is of course very sub-optimal, even code-wise, but 3.2 really is an obsolete version. (But it is still the best-documented version that is discussed on the website, so I wanted to include a Winboard compatable version of that one.)

In version 4.0 I stream-lined the entire hash handling, switching to a replace-always scheme (shrinking the code). It still did not update the hash key at game level, though, but it does change it on every move such that all entries that were in the table from the previous search are guaranteed to be invalid.

I have experimental versions that do keep the table from previous searches, that didn't take too much extra code (but required a different mechanism of updating the key, in a global variable rather than as a function argument). There are other changes in that version as well (in particular null-move pruning), but I am still not convinced that it works properly.

I hope to put the Winboard-compatible version on my website tonight. What I still want to change is the mechanism of time control. (Now it counts nodes, but Winboard asks it to play at a certain number of seconds, and the conversion factor is CPU-speed dependent. So I will probably have it read the clock directly to make the decision to start a new iteration, which is easy enough, but needs to be calibrated.) Plus that I want to build in a way for the user to control the size of the hash table, from a command-line argument.

Hello HG,

Thanks for all the infos and for the announcement that
you wanna release a WB compatible version soon!
(using directly WBs time/otim should be really the best)
I am already curious how competitive your minimal
approach is.

Regards,
Guenther

[H.G.Muller]

Well, it will certainly not be able to compete with serious engines. The principal objective remains to be small, not strong. The current version even loses to TSCP, but it should still give the non-club Human player a very tough game. And the current uMax is only the first attempt, there is still room for a lot of improvement.

It should be possible to have null-move pruning, a better QS (all good captures, rather than just recaptures), hash retaininment, 3-fold repetition detection (which will make it win many more games that it now draws), and self-deepening without too much difficulty. King safety, passed Pawns and mobility are a bigger challenge.

[Sven Schüle]

Hi H.G.,

I would try to avoid having hash hits at the root node at all. Your goal of the search is to find the best move, not the (possibly stored) value of the root node. So I think it's normal to restrict hash table lookup to everything below the root, and to make/unmake all level 0 moves. Costs are neglible.

You might also overcome the problem by calculating the hash key of the root node from scratch after making the game move, if you can't update the hash key incrementally there.

Sven

[H.G.Muller]

I am not sure what would be gained by treating the root differently. In the experimental version that retains the hash table the normal situation is that if the previous move searched to, say, 8 ply, after the expected reply the root node will find the position in the hash table with a draft of 6 ply. The best move will be in the hash as well. The search then starts at 7 ply with the hash move. It will never consider the draft sufficient, since the root deepens until time is up, not until a requested depth is reached. I don't see what would be gained by re-doing the first 6 iterations, it would bring the program in exactly the same state as it is after the hash hit.

If the reply was not the best one, the position will be in the hash table as a cut node, and since in the root beta is +INF the lower bound cannot satisfy the request regardless of draft. Deepening will then start at depth zero, with the hash move.

Anyway, the executable of the Winboard-compatible version is now on my website for download!

[Tony Thomas]

I am going to test your engine as soon as I test, Danasah and Romichess.

[Uri Blass]

I am not sure what would be gained by treating the root differently. In the experimental version that retains the hash table the normal situation is that if the previous move searched to, say, 8 ply, after the expected reply the root node will find the position in the hash table with a draft of 6 ply. The best move will be in the hash as well. The search then starts at 7 ply with the hash move. It will never consider the draft sufficient, since the root deepens until time is up, not until a requested depth is reached. I don't see what would be gained by re-doing the first 6 iterations, it would bring the program in exactly the same state as it is after the hash hit.

If the reply was not the best one, the position will be in the hash table as a cut node, and since in the root beta is +INF the lower bound cannot satisfy the request regardless of draft. Deepening will then start at depth zero, with the hash move.

Anyway, the executable of the Winboard-compatible version is now on my website for download!

I tested it under Fritz gui and it seems to have bugs

I started by testing against simply tscp at depth 2 plies from one of the noomen position

I got the following game:

13.Bf4 is not a move that I expect an engine to play at depth 2 plies because it lose the queen

After 30...Qxh3 MicroMax simply refused to play.
Note that micromax know the depth parameter and I found that depth 6 beated simple tscp depth 2 easily

[Event "URI-AMD, 2Ply / 2Ply"]
[Site "URI-AMD"]
[Date "2007.01.11"]
[Round "1"]
[White "micromax"]
[Black "SimpleTscp"]
[Result "*"]
[PlyCount "60"]
[TimeControl "40/240:40/240:40/240"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3
O-O 9. h3 Bb7 10. d4 {0.01/1 4} exd4 {-0.33/2 0} 11. Nxd4 {(cxd4) 0.01/1 0}
Nxd4 {-0.41/2 0} 12. Qxd4 {0.01/1 0} c5 {-0.47/2 0} 13. Bf4 {(Qd3) 0.01/1 0}
cxd4 {-8.95/2 0} 14. cxd4 {(Nd2) 0.01/1 0} Bxe4 {-8.91/2 0} 15. Nc3 {0.01/1 0}
d5 {-9.04/2 0} 16. Nxe4 {(Be5) 0.01/1 0} Nxe4 {-9.04/2 0} 17. Kf1 {
(Be5) 0.01/1 0} Bf6 {-9.70/2 0} 18. Ke2 {(Be5) 0.01/1 0} Bxd4 {-10.87/2 0} 19.
Kf3 {(Rad1) 0.01/1 0} Bxb2 {-11.97/2 0} 20. Bc2 {(Rab1) 0.01/1 0} Bxa1 {
-13.67/2 0} 21. Rxa1 {0.01/1 0} Qf6 {-13.67/2 0} 22. Bxe4 {(Rd1) 0.01/1 0}
dxe4+ {-17.49/2 0} 23. Kxe4 {0.01/1 0} Qxa1 {-17.49/2 0} 24. Be5 {
(Bd6) 0.01/1 0} f5+ {-18.50/2 0} 25. Kf4 {(Kd5) 0.01/1 0} g5+ {-19.60/2 0} 26.
Kxg5 {0.01/1 0} Qxe5 {-19.54/2 0} 27. f4 {0.01/1 0} Qg7+ {-20.54/2 0} 28. Kh5 {
0.01/1 0} Qxg2 {-21.53/2 0} 29. Kh4 {(h4) 0.01/1 0} Qf3 {-21.55/2 0} 30. Kg5 {
0.01/1 0} Qxh3 {-22.54/2 0} *


[Event "URI-AMD, 6Ply / 2Ply"]
[Site "URI-AMD"]
[Date "2007.01.11"]
[Round "1"]
[White "micromax"]
[Black "SimpleTscp"]
[Result "1-0"]
[ECO "C92"]
[PlyCount "63"]
[TimeControl "40/240:40/240:40/240"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3
O-O 9. h3 Bb7 {Both last book move} 10. d3 {0.01/1 4} g6 {-0.28/2 0} 11. Bh6 {
(Nbd2) 0.01/1 0} Re8 {-0.18/2 0} 12. Nbd2 {0.01/1 1} b4 {-0.02/2 0} 13. Bd5 {
(d4) 0.01/1 1} Nxd5 {-0.11/2 0} 14. exd5 {0.01/1 0} bxc3 {-0.05/2 0} 15. bxc3 {
0.01/1 4} Na7 {0.13/2 0} 16. Qb3 {(c4) 0.01/1 1} Nb5 {0.18/2 0} 17. c4 {
(d4) 0.01/1 1} e4 {1.29/2 0} 18. dxe4 {0.01/1 1} Bf6 {2.24/2 0} 19. Rac1 {
(cxb5) 0.01/1 1} c6 {3.14/2 0} 20. cxb5 {0.01/1 1} cxb5 {3.29/2 0} 21. Kf1 {
(Bf4) 0.01/1 1} Be5 {3.09/2 0} 22. a4 {(Kg1) 0.01/1 1} Qa5 {2.51/2 0} 23. Rb1 {
0.01/1 1} f5 {3.19/2 0} 24. Nxe5 {(axb5) 0.01/1 1} Rxe5 {2.65/2 0} 25. axb5 {
(Bf4) 0.01/1 1} fxe4 {2.49/2 0} 26. Nxe4 {(Nc4) 0.01/1 1} Bxd5 {2.39/2 0} 27.
Nf6+ {0.01/1 1} Kh8 {4.65/2 0} 28. Nxd5 {0.01/1 1} Rxe1+ {4.65/2 0} 29. Rxe1 {
0.01/1 0} axb5 {4.80/2 0} 30. Qb2+ {(Bf4) 0.01/1 0} Qc3 {14.84/2 0} 31. Qxc3+ {
(Nxc3) 0.01/1 0} Kg8 {99.98/2 0} 32. Qg7# {0.01/1 0} 1-0

[H.G.Muller]

Ah, it seems that indeed you have caught a bug here (sort of). I guess uMax interprets the sd n command in a strange way, setting it to an n-1 ply search rather than n ply: the argument with which the uMax search routine is called is 1 for SEE (recaptures-only search), and 2 for a full-width 1-ply search. And in the iterative deepening loop it has something like:

Code: Select all

while(IterDepth++ < Depth || IN_ROOT && TIME_LEFT && IterDepth <= MaxDepth)


where MaxDepth is the global variable set by the sd command and IterDepth-1 is passed as search depth for the replies to the searched moves (if that it is >= 1, otherwise the move is not searched).

Because IterDepth is already increased in the left-hand-side of the ||, the last iteration the root does is with IterDepth equal to MaxDepth. (Depth=0 in the root.) If MaxDepth=2 that means IterDepth=2, but that is only a one-ply search.

I should offset the argument of sd by one to conform to the intuitive meaning of the depth parameter, rather than stick to the micro-Max meaning. Doing only a one-ply search with SEE-quality QS of course makes it overlook that the Queen is onder attack; it only searches the recapture of the Bishop. I have tried, versions, btw, that would also give an extension for each lower x higher capture, next to the recapture. (This effectively emulates a SEE taking account of soft pins.) Those would have recognized the threat against the Queen even at 1-ply, but in general it did not increase strength, so I dropped it.

[Uri Blass]

Ah, it seems that indeed you have caught a bug here (sort of). I guess uMax interprets the sd n command in a strange way, setting it to an n-1 ply search rather than n ply: the argument with which the uMax search routine is called is 1 for SEE (recaptures-only search), and 2 for a full-width 1-ply search. And in the iterative deepening loop it has something like:

Code: Select all

while(IterDepth++ < Depth || IN_ROOT && TIME_LEFT && IterDepth <= MaxDepth)


where MaxDepth is the global variable set by the sd command and IterDepth-1 is passed as search depth for the replies to the searched moves (if that it is >= 1, otherwise the move is not searched).

Because IterDepth is already increased in the left-hand-side of the ||, the last iteration the root does is with IterDepth equal to MaxDepth. (Depth=0 in the root.) If MaxDepth=2 that means IterDepth=2, but that is only a one-ply search.

I should offset the argument of sd by one to conform to the intuitive meaning of the depth parameter, rather than stick to the micro-Max meaning. Doing only a one-ply search with SEE-quality QS of course makes it overlook that the Queen is onder attack; it only searches the recapture of the Bishop. I have tried, versions, btw, that would also give an extension for each lower x higher capture, next to the recapture. (This effectively emulates a SEE taking account of soft pins.) Those would have recognized the threat against the Queen even at 1-ply, but in general it did not increase strength, so I dropped it.

most programs including tscp can avoid losing the queen at depth 1

Tscp simply does it by recursive search of all possible captures when the remaining depth is 0.

It means that comparing depth between tscp and micromax is meaningless not only because of the check extension that tscp does but also because tscp has a better evaluation of nodes when the remaining depth is 0.

Tscp will never evaluate position when the opponent can capture the queen as a leaf node unless the
score of the evaluation is above beta that mean that even doing nothing is good enough for the opponent and he does not have to capture to get the score above beta.

Uri

[H.G.Muller]

Comparing depth between two engines is always meaningless, because depth means a different thing in different engines.

It is true that TSCP sees much more that uMax at the same depth, but it also has to search many more nodes for that. Most top engines do not have a QS as elaborate as TSCP, so TSCP is probably not optimal in this respect either. It 'over-does' it, while uMax under-does it.

Like I said, I did also try versions where uMax would try any lower x higher capture in addition to the recapture. In self-play with equal average CPU time (approximately equal nodes searched) this did not make a significant difference. So my guess is that the advantage of recognizing if the Queen is under attack in this position in a 1-ply search is on the average offset by the time wasted in other positions.

Note that even in this position, if it would have occurred deep in a tree, it would have made little difference: The Queen is under attack, but there are plenty of moves that save the Queen. So the score is approximately OK, it is only the move that is wrong. But the move is only used at the root.

You might argue that if a black piece would have been hanging elsewhere on the board, the score would have been very wrong, because uMax would assume it could safely take that piece in stead of saving its Queen. In such a situation the move attacking the Queen would (unjustly) be considered as losing that piece. But that is unlikely to affect the score of that underlying node, since black would still have the alternative to save the piece immediately, without threatening the white Queen first. Only in cases were the hanging piece can be saved by no other means than chasing away the enemy Queen first, it would make a difference in the 2-ply score, and in the tree such positions are very rare. And of course if the Queen that is attacked cannot be saved at all, but for a Queen to be trapped is also very rare.

Note that a similar attack on the King would be recognized at one ply, for King captures are always recognized and scored (there is no need to search them...) at any depth, even if they are not recaptures. This is rationalized by the fact that it is not as obvious that you could save a King as that you can save a Queen.

I guess that the bottom line is that searching L x H captures very often is a waste of time, because the fact that you can do them merely shows that you are in a 'dead branch', where the opponent made the mistake of allowing the LxH capture. (Unless where your high piece was lured to that square in a swapoff sequence, and the recapture search takes care of that.)

[Uri Blass]

Comparing depth between two engines is always meaningless, because depth means a different thing in different engines.

It is true that TSCP sees much more that uMax at the same depth, but it also has to search many more nodes for that. Most top engines do not have a QS as elaborate as TSCP, so TSCP is probably not optimal in this respect either. It 'over-does' it, while uMax under-does it.

Like I said, I did also try versions where uMax would try any lower x higher capture in addition to the recapture. In self-play with equal average CPU time (approximately equal nodes searched) this did not make a significant difference. So my guess is that the advantage of recognizing if the Queen is under attack in this position in a 1-ply search is on the average offset by the time wasted in other positions.

Note that even in this position, if it would have occurred deep in a tree, it would have made little difference: The Queen is under attack, but there are plenty of moves that save the Queen. So the score is approximately OK, it is only the move that is wrong. But the move is only used at the root.

You might argue that if a black piece would have been hanging elsewhere on the board, the score would have been very wrong, because uMax would assume it could safely take that piece in stead of saving its Queen. In such a situation the move attacking the Queen would (unjustly) be considered as losing that piece. But that is unlikely to affect the score of that underlying node, since black would still have the alternative to save the piece immediately, without threatening the white Queen first. Only in cases were the hanging piece can be saved by no other means than chasing away the enemy Queen first, it would make a difference in the 2-ply score, and in the tree such positions are very rare. And of course if the Queen that is attacked cannot be saved at all, but for a Queen to be trapped is also very rare.

Note that a similar attack on the King would be recognized at one ply, for King captures are always recognized and scored (there is no need to search them...) at any depth, even if they are not recaptures. This is rationalized by the fact that it is not as obvious that you could save a King as that you can save a Queen.

I guess that the bottom line is that searching L x H captures very often is a waste of time, because the fact that you can do them merely shows that you are in a 'dead branch', where the opponent made the mistake of allowing the LxH capture. (Unless where your high piece was lured to that square in a swapoff sequence, and the recapture search takes care of that.)

As far as I know all top programs(at least top free programs) search all LxH captures in the qsearch(I assume you mean low piece capture high piece).

tscp also searches all HxL captures that means lines like Qxa7 Rxa7 when a7 is a pawn and better programs save searching that line because Qxa7 is considered as bad capture not to search but
they always search capturing queen in the qsearch when it is first move.

Note that it can happen that the opponent has a fork in the last move and you can escape with the queen or with the rook but not with both.

Micromax will need additional ply to see it relative to most programs.

Uri

[H.G.Muller]

Yes, entirely correct.

Micro-max will need an extra ply of depth to see forks. On the other hand, its QS is very cheap, so it might always have that extra ply at equal search time.

Like I said, I did try this, and it didn't seem to give any improvement in self-play. It is very simple to implement: in stead of calculating the new depth as

Code: Select all

NewDepth = IterDepth - (ToSqr != LastTo);


you simply do

Code: Select all

NewDepth  = IterDepth - (ToSqr != LastTo & Victim <= Piece);


This takes only 5 extra characters. (You would have to put the value of a King in the PieceValue[] table to 10 in stead of -1, and the King-capture test Victim<0 should become Victim>9 to make it work, but this doesn't change the number of characters.) But I didn't see any difference in strength. Probably because LxH is in practice of less importance than Any x Undefended.

[Uri Blass]

Yes, entirely correct.

Micro-max will need an extra ply of depth to see forks. On the other hand, its QS is very cheap, so it might always have that extra ply at equal search time.

Like I said, I did try this, and it didn't seem to give any improvement in self-play. It is very simple to implement: in stead of calculating the new depth as

Code: Select all

NewDepth = IterDepth - (ToSqr != LastTo);


you simply do

Code: Select all

NewDepth  = IterDepth - (ToSqr != LastTo & Victim <= Piece);


This takes only 5 extra characters. (You would have to put the value of a King in the PieceValue[] table to 10 in stead of -1, and the King-capture test Victim<0 should become Victim>9 to make it work, but this doesn't change the number of characters.) But I didn't see any difference in strength. Probably because LxH is in practice of less importance than Any x Undefended.

qsearch of only captures should not be expensive.
Based on my memory tscp does not use most of its time in the qsearch and tscp qsearch algorithm should cost you significantly less than a ply assuming that you have a branching factor that is bigger than 2.

It is possible to get even cheaper qsearch by not considering bad captures but the qsearch of tscp of searching all captures is not very bad and I assume that it is better than micromax's qsearch.

Uri

[H.G.Muller]

I am afraid I still need a little bit of help:

I am now trying to interface Joker to Winboard, but unlike micro-Max, Joker is an engine that knows pondering. Now inter-process communication in Windows is a totally blind spot of mine, so to get the pondering running in the first place, I made use of a subroutine that the author of Zzzzzz was kindly enough to provide to me, which reports if there is input waiting without hanging:

Code: Select all

#include <windows.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/select.h>
#include <sys/time.h>

static fd_set rset;
static struct timeval timeout = {0, 0};


int unbuffered_input(void)
{
   FD_ZERO(&rset);
   FD_SET(0, &rset);
        if(select(1, &rset, NULL, NULL, &timeout) < 0) printf("error X\n");
   if (FD_ISSET(0, &rset))
      return(TRUE);
   return(FALSE);
}


I have no idea how it works and what the various calls it does are for, but it tells me (TRUE or FALSE) if there is input pending, so that I have to stop pondering. (It does for me what KeyHit() used to do under MSDOS.)

Could I still use that same routine if I run Joker under Winboard, or are there any modifications required here???

Any suggestions would be most welcome!