fairygen 1.2 released

[h.g.muller]

I released a new version of my WinBoard compatible EGT generator. (Source + Windows binary downloadable from http://hgm.nubati.net/fairygen.zip .)

Like the previous version it can generate 3, 4 or 5-men EGT with arbitrary octo-symmetric pieces, and can work under rules where black can null-move (-0 flag) or stalemated counts as a loss (-s flag). The EGT remains in memory, and you can play against it with black (i.e. defending against the mate).

This version allows you to 'seed' the tablebase, by setting the DTx of selected positions by hand to any desired value. Thisis done immediately after identification of the checkmates and stalemates, so that you can reset those to undecided or any other value. To use this, a file with seed positions can be specified with a -f option.

It also supports a new -m flag, which makes it generate DTM rather than DTC.

See the included README file for details.

[koistinen]

After changing line 802 to:

Code: Select all

for(tb=p;4095&(long)tb;) ++tb;    /* align with cash line         */

and including string.h it appears to compile without complaints from GCC on my Debian system.
Running with argument "KQ.K" results in output:

Code: Select all

2602010 2603000
# N:   18,3  14,3 -14,3 -18,3  33,3  31,3 -31,3 -33,3
# B:   17,7  15,7 -15,7 -17,7
# R:   16,7 -16,7   1,7  -1,7
# Q:   16,7 -16,7   1,7  -1,7  17,7  15,7 -15,7 -17,7
# K:   16,3 -16,3   1,3  -1,3  17,3  15,3 -15,3 -17,3
# M:   16,3 -16,3   1,3  -1,3  17,3  15,3 -15,3 -17,3
# A:   18,3  14,3 -14,3 -18,3  33,3  31,3 -31,3 -33,3  17,7  15,7 -15,7 -17,7
# C:   18,3  14,3 -14,3 -18,3  33,3  31,3 -31,3 -33,3  16,7 -16,7   1,7  -1,7
# F:   17,3  15,3 -15,3 -17,3
# W:   16,3 -16,3   1,3  -1,3
# E:   34,3  30,3 -30,3 -34,3
# H:   18,7  14,7 -14,7 -18,7  33,7  31,7 -31,7 -33,7
# I:   17,7  15,7 -15,7 -17,7  16,3 -16,3   1,3  -1,3
# J:   16,7 -16,7   1,7  -1,7  17,3  15,3 -15,3 -17,3
# G:   17,7  15,7 -15,7 -17,7  32,3 -32,3   2,3  -2,3
# D:   17,3  15,3 -15,3 -17,3  16,3 -16,3   1,3  -1,3  18,3  14,3 -14,3 -18,3  3
3,3  31,3 -31,3 -33,3
# O:   17,3  15,3 -15,3 -17,3  34,3  30,3 -30,3 -34,3  32,3 -32,3   2,3  -2,3
# U:   18,3  14,3 -14,3 -18,3  33,3  31,3 -31,3 -33,3
# V:   19,3  13,3 -13,3 -19,3  49,3  47,3 -47,3 -49,3  35,3  29,3 -29,3 -35,3  5
0,3  46,3 -46,3 -50,3
# S:   19,3  13,3 -13,3 -19,3  49,3  47,3 -47,3 -49,3  35,3  29,3 -29,3 -35,3  5
0,3  46,3 -46,3 -50,3
# L:   17,3  15,3 -15,3 -17,3  34,3  30,3 -30,3 -34,3   1,2  -1,2  16,2 -16,2
# Z:   17,7  15,7 -15,7 -17,7  16,3 -16,3   1,3  -1,3
KQ_K
bishops: -1 -1 -1 (0)
  0.        48     28732     13612     49030   0.000   0.000   0.000
complete:
  9.        48         0         0       206   0.000   0.000   0.000
 10.       171       897       313      2467   0.000   0.000   0.000
 11.       385      2221       647      5734   0.000   0.000   0.000
 12.       956      4239      1175     12747   0.000   0.000   0.000
 13.      1841      8839      2583     27125   0.000   0.000   0.000
 14.      3303     12322      3367     42776   0.010   0.010   0.000
 15.      5145     14271      4113     58820   0.010   0.010   0.000
 16.      6921     13441      4109     64854   0.020   0.020   0.000
 17.      5585      7140      1914     44573   0.020   0.020   0.000
 18.      1454      1516       347     10987   0.030   0.030   0.000
 19.        14        14         2       112   0.030   0.030   0.000
 20.         0         0         0         0   0.030   0.030   0.000
    32182 marked win.wtm
    93632 labeled potential win(n).btm
    25884 verified win(n).btm
   319431 checked

[h.g.muller]

Code: Select all

for(tb=p;4095&(long)tb;) ++tb;    /* align with cash line         */

Ah, that is probably a 64-bit issue. I will fix it in my next release.

I see the output is a it verbose, because it prints what it reads from the piecedef.ini file (after expansion of omni-directionality). This originally served only for debugging, but it was sometimes convenient to remind me that I was using a pieceded.ini file, and not the built-in piece types. Running under WinBoard /XBoard you would not see any of that: WinBoard ignores lines starting with #.

[byakuugan]

Mine always produces 1 error on line 859

piece[j] = strchr(cc, argv[1]) - cc;

and says "invalid operands to binary"

I assume mine is more critical.


Lately I've been learning more C and C# by studying the code for the tablebase generator, and the code for "ninjachess" which is a bot that plays the turnless chess variant seen on my youtube channel. I know they are not the same, but I think it would be possible to create a "turnless tablebase" in which pieces can move simultaneously, but there would have to be 3 evaluation modes:

Pessimistic mode: Black gets to foresee all of White's moves for the next moment
Neutral mode: Neither player gets to see each others' moves for that moment (wins are determined by probability)
Optimistic mode: White gets to foresee all of Black's moves for the next moment.

KQ vs K would be draw in Pessimistic mode, because lone K can foresee QxK and always move out of the way the same time it happens.... but it would be a win in Neutral mode since the probability of that happening is very low.

if anyone wants to give me any ideas, the code for the bot can be viewed on http://ninjachess.codeplex.com/

[h.g.muller]

Did you add the line

#include <string.h>

somewhere in the beginning, like koistinen mentions? The error message suggests that the compiler misjudges the type of strchr (which finds a character in a string), which should be defined in this header file.

Onething I wondered when I saw turnless chess was indeed if the moves took finite time, and if so,whether this time depends on distance covered, and how it relates to the 'recovery time' of moved pieces.

I am not sure I buy your argument: yes, the King has time to move out of check, but so it has in standard chess. Yet KQK is hardly drawish there. The trick is you can be checkmated, so that there is no safe square to flee to. In turnless chess the King can also not afford to step into check, because it wouldnot be recharger before it is taken. So if you only check with the Queen when the King blocks all escape squares, it seems to me you are just as mated.

I would be curious how exactly this turnless chess works. If there is a transit time, and if so, how long, and does the opponent already get to know your destination before you land there? (And if not,can you still change it based on him initiating something, by stopping where you are now?) And is the piece off the board during that time, or on intermediate squares? Can they collide 'in flight' (e.g. white plays Qa1-g1 while at the same time black plays Qh1-b1).

[h.g.muller]

A screenshot:

[byakuugan]

It generates now without errors, but it will always generate a different endgame than specified, and will always show a different position than I entered.


Travel time in turnless chess is determined by the furthest distance traveled along one axis, not the actual distance along the vector, so a queen moving from a1 to a8 takes the same amount of time as a queen moving from a1 to h8 (I don't think there would be a fool-proof way to implement irrational times), and rejuvenation time is always the same no matter how far the piece traveled. (But dropped pieces in bug/crazy modes take 1.5 times longer to rejuvenate than pieces simply moved on the board)

Once you make a move, it is final, but nobody else besides the person moving will be aware of the destination square for rider moves. (So if you see an opponent's rook riding toward your king, you won't know if it is going to try to take your king, or if it will stop at some point before it reaches your king), also, riders will "sweep" anything that is moved into their paths after they've moved, so technically it is possible to capture every piece in one move.
In your scenario with the simultaneous queen moves a1-g1 and h1-b1, both queens would start moving, then at some point between d1 and e1, the queen that moved second would vanish, and the queen that moved first would simply finish its move.
For tablebase evaluation purposes, I think your idea for changing the destination square for rider pieces should be allowed for Black in pessimistic mode, and allowed for White in optimistic mode, since those modes are designed to give one player the most amount of luck possible.

I think all 3-man endgames are draws in pessimistic mode, since White's king can only take away 2/4 squares from Black's, the third piece will always be obligated to control at least 2 squares, so any time this piece tries to capture Black's king, Black will foresee it (in pessimistic mode) and will always have a safe square to move to that is not covered by White's king. The defender will stand still, and then guess QxK.

[h.g.muller]

It generates now without errors, but it will always generate a different endgame than specified, and will always show a different position than I entered.

Hmm, that sounds bad. Let me make sure I correctly understand the problem. You are using it in stand-alone mode from the command line, right? Can you post the command line you typed and the program's response here for a case that it geerated a different end-game than you specified?

... For tablebase evaluation purposes, I think your idea for changing the destination square for rider pieces should be allowed for Black in pessimistic mode, and allowed for White in optimistic mode, since those modes are designed to give one player the most amount of luck possible.

OK, thanks for your explanation. What you describe makes it a game of incomplete information, because the opponent cannot know the destination square of riders immediately (e.g. from the speed). I would have to think about the consequences this has for retrograde analysis (or forward search, for that matter).
Another issue is that this is not purely a game of strategy, but also of speed. I can plan to move 5 pieces at once, but who will say whether I will be fast enough to actually do that before the opponent sneaks in with amove of his own? Is there also a guaranteed dead time after entering a move? Or can this be treated in that a player can order uninterruptable ('atomic') combinations of moves of upto 16 pieces? I expect even then there could be race conditions. In the 'colliding Queen' example we discussed, it is crucial who entered the move first. Suppose the moves had to wait for some third event, or coupled non-simultaneous events (e.g. the departure and the arrival of piece) which makes them want to leave simultaneously, what will decide who will be considered the first mover?

I think all 3-man endgames are draws in pessimistic mode, since White's king can only take away 2/4 squares from Black's, the third piece will always be obligated to control at least 2 squares, so any time this piece tries to capture Black's king, Black will foresee it (in pessimistic mode) and will always have a safe square to move to that is not covered by White's king. The defender will stand still, and then guess QxK.

OK, let's take a practical example:

3k3Q/8/3K4/8/8/8/8/8 w


Black sees that the white Queen starts moving in the direction of a8. What does he do?

[byakuugan]

I have the piecedef file editted so that 5 of the piece slots will always generate the correct piece, so I can just change these specifically when needed.
The real problem is that I can't search the positions I want. No matter what I type into the command line, it will always make a move for White from the longest winning position, and then let's say I try to type the position that results after a Black move, it will simply make the best move for White, and will ignore what I type.


Regarding your turnless scenario with bKd8 wKd6 wQh8 and Q heading toward a8, most players would choose their moves at random. Black can play Ke8 and hope White tried Qf8, or Black can play Kc8 and hope White tried Qxd8, or Black can simply stand still, and hope Black is trying Qe8. White should want his queen on the 7th rank and go for a contact mate, in which Black has maybe a 0.00001% chance of guessing when QxK will be attempted.

Regarding the colliding queens, riding pieces will pass through each other if they were moved at the same time, but you can no longer move pieces PAST their pieces. In the old version there was a glitch where let's say there is: bKh8 bRh7 wRh1, and White attempts the illegal move RxK, if it just so happens to be at the same time Black tries to play RxR, then White's rook will pass through Black's and capture White's, but in the new version none of these "illegal attempts" are ever processed in the game.
Also if 2 enemy kings at different areas of the board get independently captured at the same time, then the game will either say "Draw" meaning that both captures were completed simultaneously, or say that somebody won (even if both kings appear to be off the board) meaning that one of the captures was completed first.

"Atomic" tactics can only be done by bots (I'll try to post some bot videos) but they cannot be done by humans. The tablebase should probably consider the idea that a human could simultaneously move pieces (especially if there ever comes a time in the future where players use hotkeys). There are "timing attacks" (different from speed) which are aimed to purposely put the human opponent in a position where they can win material, but if they are not quick enough, then their rhythm is messed up and they could end up losing everything. A bot will auto-capture everything, but against human opponents, an Optimistic tablebase-bot should take timing attacks into account, because KNvK has a high win-rate in fast time controls.

http://www.youtube.com/watch?v=K0kB5ZJAlGE
In the game starting around 2:15, my partner employs a timing attack, but it would've been quickly refuted against a bot opponent. You'll notice that my playing style is a lot more Pessimistic than his.

[h.g.muller]

OK, I will take a look at it. Since I implemeted WinBoard protocol I have only be using the EGTgen as WinBoard engine. This works perfectly, but does not use the octal input. (In stead it accepts the position through commands like Ke4, and the move in long algebraic format, e4e5.) So I cannot exclude I have broken something in the octal input by implementing WB protocol.

In the mean time you could of course try to use it in WB mode, like

4men -xboard KBN.K
edit
#
Ke2
Be1
Nd1
c
Ke4
.
go
e4d4

(Only your input is show; before 'edit' you would see all the buildig stats, and after 'go' it would print a list of white moves and then the move it plays.) Of course in all cases it would be much easier to play it under the WinBoard GUI, for which this version was really intended...

OK, I see the problem with the turnless chess. I intended to play Qa8, to sweep up the black king, but I understand now this would be refused. I would never play Qe8 in the hope he would move there, of course, as playing Qd8 would annihilate him there anyway. Still seems won to me, though: I can keep him on 8th rank forever with my King, following his moves to maintain opposition. I then take the initiative to step towards him in steps of 1 with my Queen (so I am sure my Q recovers first when he moves in response), until there are 0 or 1 empty squares between us. When it is 0 (because he moved towards me in response to my last move) he is dead: because the Queen wakes up first, I initiate a capture against him, so that colliding would be fatal for him, so he must step back, but can only do that until he reaches a8. So suppose he has steel nerves and tries to stare me down from a distance of 2. Now I initiate a capture against him (say Qf8xd8 in the diagram position). He can only survive by stepping back (Kc8). But now he recovers before me, because he moved 1 square, and my Queen 2. Still being next to the Queen when she recovers is fatal, as before. But now he can launch a counter-strike at my Queen! But his total distance d8-c8-d8 was equal to my Queen's f8-d8, so my Queen wakes up in time to side-step his attack: Qd8-d7. Now my Queen is defended, and being in a contact-mate position, moving would be fatal for him, as I would be in time to destroy him during recovery wherever he goes. So he has no choice other than waiting until I am fully recharged. Then I initiate Qd7xd8, and whether he sidesteps to c8 or e8, my Queen will chase him down all the way to the corner, as I have the tempo, while my King keeps him trapped on 8th rank.

[h.g.muller]

I have the piecedef file editted so that 5 of the piece slots will always generate the correct piece, so I can just change these specifically when needed.

Itis very strange that this would be needed. But aslong as you don't show me the command you use to start up the generator it cannot be solved...

The real problem is that I can't search the positions I want. No matter what I type into the command line, it will always make a move for White from the longest winning position, and then let's say I try to type the position that results after a Black move, it will simply make the best move for White, and will ignore what I type.

Oh yes, you are right, I did break something. In the third line of the piece of code below all 3 occurrences of 'curpos' should have been replaced by 'playpos'

Code: Select all

  } else {
       printf("octal position number: "), scanf("%o", &j);
       if(j&~077) curpos = j; else curpos = curpos&~077|j;
  }
  if(force) continue;
  curpos = playpos;
  // map into symmetry sector

The old version worked only with curpos, but then it would mirror the position whenever the white King transgressed a symmetry line. This was unacceptable to WinBoard, which would assume the position would staythe same and only the best move was done. So I introduced an extra variable 'playpos' to remember the original orientation, so that you could continue with that on the next move after 'curpos' was reflected. But I did that only after splitting the input processing in an 'if(xboard)' and an 'else' part, and forgotto change the 'else' part accordigly.

I will release a corrected version one of the next days; if you are able to compile it, you could already make this fix yourself. (note you also have to set the value for #define MEN at the begining to the number of men you want to build for (3, 4 or 5).)

[byakuugan]

Thank you very much. This should keep me occupied for a long time. My next 2 projects are going to be to provide simple understandings of King + Hybrid vs. King, and King + 2 leapers/riders vs. King. I plan on providing efficient formulas for playing out the cornering methods of these endgames, and figuring whether or not a position is a draw. An easy way to remember how important and precise the cornering method must be, is to realize that a rider piece is not always better than its leaper counterpart. Sometimes, the extra squares that the rider piece controls, give the defender additional stalemate defenses that are not possible against the leaper counterpart, so a leaper can be better than its rider counterpart.
(I still can't seem to work the feature that should allow me to rule any position as a win, but this isn't any of my concern for now.)

Regarding a turnless chess tablebase, the problem with KQvK is that a bot equipped with its knowledge would still not be guaranteed to win 100% of the time. Even if the bot is programmed to choose a random time to attempt QxK in contact mate positions, it is possible that a human could happen to move its king at the moment the bot attempts QxK, which would cause the bot to spend more time to acheive another contact mate position, and then it is possible that the human could get lucky again. There is a 5-minute rule similar to the 50-move rule, so it not impossible that a human could continuously get lucky over the course of 5 minutes, and get a draw. The bot should first choose endgames that can be won in a foolproof way (Wins in Pessimistic Mode) and if there are none, choose endgames based on their winning probabilities in Neutral Mode.

I can probably find some good bot footage already on my computer, so I'll probably upload some human vs. bot turnless chess games within the next 24 hours. My insight into the tablebase endings I am analyzing probably won't appear on my channel for about a week.

[h.g.muller]

Well, there is zero probability that two independently chosen real numbers (or even rational numbers) would be equal. This game has a problem anyway if you assume exactly simultaneous moves by opposite sides are possible (e.g. white would play Qa1-a8 and black Qa8-a1 at the same time). So I assume that a server implementing this would in that case have to decide which one moved first in case it could not resolve the timing difference. I think that a fair protocol would in that case have to inform the side that is ruled to move last of the fact that his opponent started a move, before committing him to the requested move.

If I had to design a protocol that allows automatic play between bots, I would do it the following way:

The referee would send a move number with each move to the bots, and would always sent it to both bots. When a bot sends a move, it would send the number of the last move it received with it. The referee only accepts a move if it is accompanied by the move number that indeed represents the most recently played move in this game. If, because of communication lag, moves cross each other, and a bot would submit a move from a position that is no longer current, its move would be rejected, and in stead it would receive the move(s) that update its position. If it still wants to make the move after receiving this new info, it would have to resend it, but it is free to change its mind and send another move (or none at all) in stead.

Would you agree this is a good way to implement the idealization of the game where the players have infinitely fast reaction speed and instant updating?

I think in this idealization I can prove KQK is a forced win. Because I either beat him in getting my King-capture to the server before his evasion, in which case I can continue to beat him by sending my moves so they arrive at the referee before I recover (in which case the referee would delay them to that point) and keep the initiative forever (as our recovery times and transit times are equal), or he would beat me, which cancels my move, after which I would now re-enter a move to his destination, killing him there before he recovers.

Without the assumption of instant communication, it becomes another game, and would need additional parameters to be specified beside moving speed and recovery time to be fully defined.

[byakuugan]

There have been many changes made to the legality of certain moves in certain timing situations, so it is likely that they will change again. For example: it used to be legal for enemy pieces to be en route to the same square, where the first piece to arrive will get captured (unless second piece gets swept along the way), but now you have to wait until there are no pieces en route to a square, before you can start the journey to that square, which changes the tactics of the game.


Correspondence Tempest has been suggested before, where turns would be like "moments" where a moving rider will travel 1 square, and each player submits a list of legal moves to play that moment without seeing other player make list. Say Moment #1 White submits a4 b4 c4 d4 e4 f4 g4 h4 Nf3 Nc3 but Black decides to not submit anything, so Moment #2 will show all White pawns on 3rd rank, and knights floating halfway to their destinations. Black decides not to submit anything for Moment #2 and since none of White's pieces can move, Moment #3 arrives where all White's pieces are at destinations with 100% rejuvenation time, and since White cannot move for awhile, Black can decide to take advantage of White's weaknesses with something like e6 Bxb4 a5 or d6 Bxg4 h5.


Right now tempest bots do not know how to calculate opponent's moves, (that is too many variations) so all they do is calculate a point value system (assigned by bot's owner) to all legal moves including not moving, and then execute each piece's best move without really being able to calculate the consequences.


I found some "byakuubot" sessions recorded by my tempest partner, which I uploaded:


This is Bot + Human vs. 2 Bots, which I sped up 3x to display the chat quickly:
http://www.youtube.com/watch?v=hQe2gvbLcWo


This is a more recent session at normal speed, where the bot's pieces are "smarter" but more cowardly.
http://www.youtube.com/watch?v=8LeqwfxNDHU


This is a slowed down demonstration of one of the ways a human can achieve a high rating from abusing a bot. (also demonstrates what "sweeps" are)
http://www.youtube.com/watch?v=7prmxbKFAZA