Crazyhouse tournaments and rating list

[hgm]

Yeah, well, they're still legal moves, so the move generator generates them. They can be pruned, but it isn't smart enough to know that.

Perhaps the game definition should be smart enough to know that. It could make a distinction between legal and legal-but-stupid. (E.g. markig the latter with a question mark in the list of promotionchoices.) The latter could depend on where you promote. E.g. in Shogi you can defer Lance promotion on 7th and 8th rank, and it can be useful to do that on 7th, but not on 8th. (If you ignore the quirk that the extra covered squares can make a Pawn drop impossible.)

[Evert]

Per node store a list of moves with the proof and disproof number of the node they lead to (initially both 1, if none of the daughters exists yet). Also store the proof and disproof number of the node itself, and the number of the move with the lowest proof number.

Doesn't that duplicate information? I'm wary of doing that because of the potential for bugs. It's also my understanding that like the transposition table, you want to keep node storage size to a minimum. I was thinking of a structure similar to this:

Code: Select all

struct pn_node_t {
   uint64_t hash;
   uint64_t parent_hash;
   int proof, disproof;
};

I don't think you need to store the node-type because it alternates at each level, although with a non-recursive approach you probably do (because you don't know where in the tree you're picking the next position). Still, going to 32 bytes per entry is probably not much worse than having 24 bytes per entry (due to alignment), at least on 64 bit hardware.
I was going to store these in a list using insertion sort based on hash key. Maybe the best way to do that is have a tag-list and sorting that instead (it's more data, but sorting it should be faster). To efficiently find the next node to expand, I was thinking of a (second) tag list sorted by how good a candidate the node in question is.
There of course you can play a bit with the selection function: there are some suggestions for how to assign initial weights to leaf-nodes (using 1/1 or the number of moves, for instance), and you could probably factor in the 50-move rule, if you wanted. It's probably irrelevant for most positions though.

(I would go for a 'NegaProve' implementation, where proof and disproof get swapped in successive levels, so that the side-to-move is the 'side-to-prove'.) Then recursively walk the branch of all the best moves (only doing MakeMove() of the indicated 'hash move'), and when the recursion unwinds do the back-propagation of the result. (This would sometimes require searching a new best move, if the proof number goes up.)

That sounds reasonable too. Personally I'd like to see the algorithm in action a few times before I try to do it this way.

It is true that this would miss transpositions. But you can check during the recursion if you hit a node that was changed along another branch, by comparing the numbers listed with the moves with the totals listed in the daughters. If they differ, you abort the branch, and first propagate the altered result back to the root, before trying again. As you follow the path of lowest numbers, a transposition must have had a higher number. So if the number goes down, it would go down the same, but still stay worse. If the number goes up, the transposition would look better than it actually is, and might become a 'false best' in the root. But that would be the time you propagate the score back along that line as well.

Repeats are tricky, as they are in normal search.

I suppose my intended datastructure doesn't help. Still, in the search repetitions can never be part of optimal play; repetitions against the game history are more tricky, but perhaps I'm overthinking this: as long as I don't repeat in the search, if it can proof that the position leads to mate, it doesn't matter if there is a repeat against the game history in there (except there shouldn't be one because it should have found the mate at that point too).

[hgm]

Toprevent hijacking this thread, I started one specifically dedicated to proof-number search in the Programming section, where this discussion really belongs:

http://www.talkchess.com/forum/viewtopic.php?t=61774

[Evert]

Yeah, well, they're still legal moves, so the move generator generates them. They can be pruned, but it isn't smart enough to know that.

Perhaps the game definition should be smart enough to know that. It could make a distinction between legal and legal-but-stupid. (E.g. markig the latter with a question mark in the list of promotionchoices.) The latter could depend on where you promote. E.g. in Shogi you can defer Lance promotion on 7th and 8th rank, and it can be useful to do that on 7th, but not on 8th. (If you ignore the quirk that the extra covered squares can make a Pawn drop impossible.)

I don't like putting game-play hints in the rule description. I already hate that the piece values have to be in there.
This does remind me though: there is a bit of code that identifies "pointless deferrals" that are subsequently not generated during the search. I could include similar "pointless promotions" that are not generated during search.
I suspect this'll mostly be a cosmetic issue; then again I'm not writing Stockfish here, so gaining Elo isn't a primary concern.

[hgm]

Indeed. A deferral is in fact a special case of an under-promotion. If any choice is completely contained in another, the former is pointless.

This could fail when stalemate plays a role, however. And in Chu Shogi there are two non-obvious cases because of the Lion-capture rule: a Gold is not upward compatible to a Pawn (because it cannot stand between two Lions without offering them an opportunity to capture each other), and a Lion is not upward compatible to a Kirin (because it cannot capture a protected distant Lion, which a Kirin can do).

[hgm]

In my preliminary tests I removed the Q-side minors, and gave each side two N-B switchers in hand. The Knights seem to win that significantly.

Clever.
I can imagine the Knights being much stronger here, due to the always crowded board.

This nicely allows me to measure the ratios of the N-B, R-N and Q-R difference. But these are all 1-vs-1 imbalances, and do only determine the piece values upto addition of a constant. To fix that constant I would have to do at least one 2-vs-1 imbalance (or a 1-vs-0). Normally I use the 2N-vs-R for that.

I am not sure if there is a method to do such a thing in a drop game, similar to the switching pieces. I could of course give a side that captures a Queen two switching-Knights in hand. But what should happen when he then captures these switching Kights? I cannot give him a Queen for the each one he captures. It seems unfair to force him to wait until he has two switching Knights in hand before he can drop them (as a single Queen), then he would actually have to play a fraction of the time with a Knight less after he traded a real Knight for a switching Knight.

Perhaps the following idea would work: The first Switching Knight he captures can be dropped immediately, but will then also play as a Knight for him. Only when he captures the second Switching Knight, it won't get into his hand, but the one on the board upgrades to a Switching Queen.

I guess it would be a bad idea to do that with Knights, as it means he might not be able to (re-)capture a Switching Knight when his defense critically depends on a move of the Switching Knight he already has on the board. I could do it with Bishops, however, as the upgrade to Q keeps all the old moves.

I am not sure this gives a fair comparison to the other imbalances, however. With a 1-for-1 switching piece you would expect it to spend 50% of the time on each side (as both sides are programmed to value it equally, and thus give one side half the time usage ofpiece X, and theother one half the timeof piece Y. With this two for one scheme half the time the pieces will be in different hands, and move equally. They only cause an imbalance when both pieces are in the same hand, when one side plays with two Bishops, or the other with a Queen. So the effect of the imbalance acts only half the time.

This does of course not matter if the effect is nearly zero, i.e. if 2B vs Q happens to be perfectly balanced, and it would not stop you from deciding if 2B is better or worse than Q. You just couldn't say precisely how much better or worce, in terms of B-N differences.

[hgm]

New version (0.0.1) of CrazyWa available for download! I fixed some crippling bugs, so that null move now works, it can also use Pawns for check-drops, and it no longer passes an uninitialized e.p.square to the node after null move (which could lead to generation of moves that could even go off board,with crashes as a result).

As a result it now seems to beat Sjaak by 66%, (well, based on only 20 games...), where before it only scored 33% against it.

It still cannot castle, and has no repetition detection.

[Ferdy]

New version (0.0.1) of CrazyWa available for download! I fixed some crippling bugs, so that null move now works, it can also use Pawns for check-drops, and it no longer passes an uninitialized e.p.square to the node after null move (which could lead to generation of moves that could even go off board,with crashes as a result).

As a result it now seems to beat Sjaak by 66%, (well, based on only 20 games...), where before it only scored 33% against it.

It still cannot castle, and has no repetition detection.

Blitz rating update.

https://sites.google.com/site/zhassocia ... list/blitz

This version has gained around 200 rating points so far after 96 games at TC 3+2.

[Evert]

New version (0.0.1) of CrazyWa available for download! I fixed some crippling bugs, so that null move now works, it can also use Pawns for check-drops, and it no longer passes an uninitialized e.p.square to the node after null move (which could lead to generation of moves that could even go off board,with crashes as a result).

As a result it now seems to beat Sjaak by 66%, (well, based on only 20 games...), where before it only scored 33% against it.

It still cannot castle, and has no repetition detection.

Impressive. Do you know if the strength increase is mainly due to evaluation or search improvement?
I suspect castling is mostly irrelevant in Crazyhouse. Repetitions aren't a big issue either, from what I remember.

[Evert]

Hmm...
Apparently I can get SjaakII to score some 70% against itself by actually picking reasonable piece values.

I guess I'll be doing a new SjaakII release soonish...