The Chess Variant Pages
Custom Search




[ Help | Earliest Comments | Latest Comments ]
[ List All Subjects of Discussion | Create New Subject of Discussion ]
[ List Latest Comments Only For Pages | Games | Rated Pages | Rated Games | Subjects of Discussion ]

Comments/Ratings for a Single Item

Later Reverse Order EarlierEarliest
This item is a computer program
It belongs to categories: Orthodox chess, 
It was last modified on: 2016-11-21
 Author: Greg  Strong. ChessVThis item is a computer program
It belongs to categories: Orthodox chess, 
It was last modified on: 2016-11-21
 Author: Greg  Strong.. Missing description[All Comments] [Add Comment or Rating]
V. Reinhart wrote on 2018-01-08 UTC

Oh thanks - I understand now. Other than bishops, I've never played with any piece restricted to a limited range of the board. I'm sure there are many such pieces, but unfortunately there is probably no existing catalog of "meta-color" bound pieces. Maybe something for me (or anyone) to work on for this year?


H. G. Muller wrote on 2018-01-06 UTC

'Color' is just the square shade you can see on a checkered board, light or dark. The term 'meta-color' usually refers to another (hypothetical, i.e. not actually visible) coloring scheme using more than two colors in some other pattern, each meta-color indicating a set of reachable squares. E.g. a Dababba can only reach a quarter of all board squares, so that you can put four Dababbas on a board that could ever collide with each other, each on its own meta-color.


V. Reinhart wrote on 2018-01-06 UTC

Just a little confused about some of this discussion: what is the distinction between "meta-color bound" compared to "color-bound"?


H. G. Muller wrote on 2018-01-06 UTC

I think that trying to treat irreversible pieces like Pawns as color bound misses the point. E.g. a Xiangqi 'passed Pawn' (fsW) or a Dai-Shogi Evil Wolf (fsWfF) on a1 can reach the entire board. But that ignores that when they try that, they never can move back. Pieces like that have an ever shrinking accessible area, which is basically a property independent of color binding.

This is further complicated (or neutralized, depending on how you look at it) by promotion. Pawns in Chess do promote to pieces that can access the entire board. So they are not really meta-color bound. But in Makruk, where they are predestined to promote on a certain color to a color-bound Ferz, there actually are locations where they never will be able to go. That Pawns before their promotion can access only a limited part of the board is more comparable to (temporarily poor) mobility than to color binding.

Another issue is how to treat captures. As in general you cannot force survivable captures at will, capture moves are not very helpful for breaking color binding. It seems better to treat a non-promotable FIDE Pawn as having access only to the (forward part of) the file it is on, while interdicting access to some squares outside that area. Such attacks outside the meta-color to which it is bound can of course have consequences for its mating potential. Two mFcW on different square shade have no mating potential, so they behave pretty much as color-bound pieces as far as checkmating a bare King is concerned.


Greg Strong wrote on 2018-01-06 UTC

Do these "rules of thumb" work for the huygens chess piece? As far as I know this piece does not appear in any chess engines, but it could be a good exercise to test the robustness of any new code.

Thanks, that is an excellent idea.  Although I've never added the Huygens, it should work and consider the entire board to be one slice, since the Huygens has no color-binding.  It cannot move a single space directly, but since it can leap three forward, and then two back, it can effectively move a single space, and the recursive algorithm would find this.

That said, it seems that we have other problems.  I've had this algorithm for a while, but since it wasn't really used for much, any issues went unnoticed.  I now notice that we do, indeed, have some issues, and it is nothing so fancy as the Huygens.  The problems start with the venerable chess pawn...

A pawn placed on a1 cannot visit the whole board, only a little over half the board.  So it considers that triangular-shaped half the first slice.  (Nevermind that a pawn cannot even exist on a1, that's a whole 'nother problem.)  Since this did not find the whole board, it detects the second slice by throwing a pawn on b1 - but this only finds 7 more squares!  For slice three, throw a pawn on c1 and find 6 more squares ...  Obviously, this is not at all what we want to happen.  In fact, as far as the pawn goes, I'm not even sure what the theoretically correct answer is, although I'm quite sure this ain't it.  A slight improvement would be to ignore the pawn's capture-only moves on the grounds that it might never have the opportunity to do that.  This would leave each file as a separate slice.  There is some logic to this.  It might even be the correct answer to some questions.  But, for purposes of making a material hash table, to detect draws by insufficient material and probably do other groovy stuff as well, I believe we want to consider all pawns to be identical (although I'm not 100% sure of that either...)  So I guess the pawn just gets a special flag that tells the system to treat it as though it is not colorbound even though it really is.

The pawn also points out another potential problem with this algorithm.  It begins by visiting the "first" space.  This, for the pawn, was bad, but not truely terrible because it considered a1 to be the "first" space.  But what if pawns went backwards instead of forwards?  Now instead of considering the board to be split into 8 different slices, it would be split into 64 different slices!  Clearly, for asymmetric pieces, the choice of which square to visit first is very important.  I can see two potential ways to deal with this.  First, we can look at how the piece moves and then be wicked smart about which square to visit first.  This would be awesome, but I'm not sure how to determine this (it makes my head hurt, and, frankly, I'm just not that smart.) And I'm not 100% sure that there even is a best answer for all kinds of pieces.  The other possible solution is to leave it as-is, with the addition that when we are doing our recursive analysis to detect a new slice, if we happen to stumble across a square that we have visited while discovering a previous slice, we now need to consider this new traversal to be part of that original slice.  I think this approach is solid, although the algorithm is now becoming more complicated ...  But, well, that's why this particular project fascinates me so much.  The various interesting issues to ponder are practically never-ending.

Another potential issue, alluded to above - we probably only want to consider squares to which a piece can theoretically move.  It doesn't matter what a pawn on the first rank can do.  But for a better example, consider: Pocket Knight.  The knight "drop" is not really a normal move, so I think (although I'm not sure) that our fancy colorbinding-detector should not consider it.  Therefore, it should consider the knight to see the board as three separate slices (three different meta-colors) - the main board, White's pocket square, and Black's pocket square.  Groovy.  But what we don't want to happen is for it to then consider the bishop to also have three meta-colors, since the bishop isn't in the pocket and can't go there.  So this would be the next change to the algorithm - don't find the entire board when the game is created.  Only start this process when a piece is actually placed on a square and that square hasn't been visited yet (meaning it hasn't yet been segregated into any given slice.) Strangely, this is how the old C++ ChessV used to do it. I changed it because I thought I was simplifying things, when apparently I was breaking things :)

One final random thought ...  If a piece type has two meta-colors, you can NOT assume that it is equivalent to all other pieces with two meta-colors.  Example: Alice Chess.  In Alice Chess, both the Knight and the Bishop can see exactly 50% of the squares.  But their color-bindings are NOT the same!

Fun stuff!!!


V. Reinhart wrote on 2018-01-06 UTC

Do these "rules of thumb" work for the huygens chess piece? As far as I know this piece does not appear in any chess engines, but it could be a good exercise to test the robustness of any new code.
 


Greg Strong wrote on 2018-01-05 UTC

The algorithm Greg describes seems completely robust, even for hex boards, or pieces with position-dependent moves.

Yup.  I try not to attack any problem unless I'm attacking it in a "universal" way.  Although, on further reflection, my algorithm will fail for Chess on an Infinite Board whereas yours would work fine :)


H. G. Muller wrote on 2018-01-05 UTC

The algorithm Greg describes seems completely robust, even for hex boards, or pieces with position-dependent moves. And it is not that computation intensive, when you mark the squares you have already visited; it just requires running the move generator once on every reachable square.


Aurelian Florea wrote on 2018-01-05 UTC

@HG,

I assume more bounded pieces like the dababah or the elphant should be found by conditions on other parities like deltax and deltay separatly. The chiral knight is interesting. Any ideea on hex boards?


Greg Strong wrote on 2018-01-05 UTC

ChessV does this with a brute-force recursive algorithm.  It calls a recursive function to "visit" the first square.  This function marks that square as "found" and then proceeds to go through every movement capability that the piece has, finds the next square in that direction, and recursively calls itself to visit that square.  When this finally finishes every square you have visited is part of the first "slice" or "meta-color".  Are there any squares that weren't visited?  If so, do this whole process again starting with the first square that wasn't visited.  The results of this search will be the second slice.  Continue as necessary until the entire board has been found.  This should work for any board geometry.  It's a little computationally expensive, but is only performed once when a new game is being created.


H. G. Muller wrote on 2018-01-05 UTC

I cannot really answer that for ChessV, but Pair-o-Max does it too, and it is quite rivial. You just check if delta_x + delta_y is even for every possible move. Sliding moves are just multiple moves of the basic step, so you only have to test the basic steps. I suppose ChessV does that likewise.

This of course only works on a topologically flat board. If you would have an odd-circumference cylinder, or helical board, it could be uncheckerable, so that there only is a single square shade,

I am not sure how you would determine the meta-color of a square, though. Especially in non-trivial cases like (say) right-handed chiral Knights, which distinguish 5 meta-colors. In principle every point-symmetric piece with 4 moves other than Wazir should have a form of meta-color binding.


Ben Reiniger wrote on 2018-01-05 UTC

How does ChessV determine colorboundedness?  Just by moving a piece around for a few moves?


H. G. Muller wrote on 2018-01-05 UTC

Indeed, distinguishing pieces by (meta-)color is beneficial, and would also allow easy depreciation of end-games with unlike Bishops, like KBPPPKBP. I am not sure how that generalizes, BTW. End-games with unlike Ferzes did not seem particularly drawish. And logic dictates that the color binding should only be a handicap for the strong side, and not an asset for the weak side. So in KBPPPKXP it should not matter much if X is color bound or not. Yet when X=N this is not particularly drawish. The drawishness with X=B seems to be caused by the ability of the Bishop to stop large numbers of Pawns from crossing a diagonal.

Of course with multiple color-bound piece types mating potential can also critically depend on whether they are on the same or a different shade. Note that is Makruk it is beneficial to also consider Pawns as color bound, depending on the shade of their promotion square. KPPPK will be a draw if all Pawns promote on the same shade! It is a good question how to judge divergent pieces, such as the Berolina Pawn. My gut feeling is that you would have to judge them by their m component.

I have forgotten the exact number, but it surprised me how much stronger Pair-o-Max was than Fairy-Max. (I think over 50 Elo.) And this was just from recognizing Bishop pair and the drawishness. Where the latter was not even implemented through a material hash, so that I expected a significant slowdown from it. But the primary filter for the drawishness code is that the number of Pawns of the strong side should be <= 1, which is not the case throughout most of the game, and rather cheap to test. The largest overhead is actually keeping a count for each piece type (which probably costs less than updating a material hash key). Pair-o-Max doesn't recogize unlike-Bishop end-games, however, as these typically occur with many Pawns.


Greg Strong wrote on 2018-01-05 UTC

Ok, I think I'm now going to tackle these related issues of detecting draw by insufficient material and scaling down the evaluation of positions that are likely drawn due to the material present.

As a first step, I'm going to code a material hashtable so this detection won't be too slow.  Although the page on the chess programming wiki only describes tracking the number of each type of piece per player, it seems you also want to track colorbound pieces of each type separately...  KBBK is a draw if they bishops are on the same color, otherwise it isn't.  So it seems for these purposes, a black bishop on light squares should be considered a different type of piece from a black bishop on dark squares.  Fortunately, ChessV already detects which pieces are colorbound automatically, as well as how many different "colors" each has (which internally I call "slices" so as not to confuse the different meanings of colors.)


V. Reinhart wrote on 2018-01-04 UTC

Yes, agree with all. There are some 7-men endings that engines can't play perfecty, such as the mate-in-546 position. I once plugged that position into a chess engine and it was pretty much clueless. Even with the 50-move rule, the side that could achieve the draw (by playing to 50 moves) sometimes lost the game. (Of course, these endings aren't seen often if ever in actual play).


H. G. Muller wrote on 2018-01-03 UTC

It is possible to look up the game positions. But this usually provides no benefit at all, because engines are usually good enough to win won games on their own steam. Most gain comes from probing EGT in search when there still are more men on the board than in your largest EGT, to make sure you will convert to a won position, rather than a drawn one. This requires several hundred thousand probes per second. E.g. as a simplified example consider a KPPPKPP position, whith many possible ways to force conversion to KPK depending on where you start attacking with your King. If you only have a 3-men EGT for KPK, and no special knowledge of KPK, you would just randomly convert to one of the KPK positions. Pobing the game position would then just tell you "Oh, too bad, this is a draw". The search would not see that, as in KPK you can postpone a stalemate or repetition very long, to beyond the horizon. Only when you can see in the search which KPK positions you can convert to are wins and which are draws, you can make the right choice, and force conversion to the winning KPK position.


V. Reinhart wrote on 2018-01-03 UTC

Thanks HGMuller for the very informative information.

I believe the Lomonosov EGT is based on DTM because it includes forced mates that go on for hundreds of moves without pawn moves or promotions. The longest I believe is a 546-move forced mate.

Many of my questions are from the point-of-view of seeking an engine which plays perfectly. Of course there's no prospect of anyone doing this in the near future. But the question of "how" is interesting to me.

As for using the existing Lomonosov tablebase for actual play, I believe it could be possible for anyone who has paid to use the resource. Although the database is huge, information related to the "position-at-hand" could be transmitted in packets. I would think the internet is fast enough to support a game with 90 min/40 moves (for example).

Nevertheless, you raise some very good points. Another interesting point is that in perfect play, most of the 7-man tablebase includes positions that may not even exist in a perfectly-played game. In other words, although the tablebase represents "perfect play", much of it may not be part of "perfect games".

It's interesting to think how chess is still so far from being solved, and yet people like you (Fairy-max), Greg (ChessV), Nicolino (Chess and a Half ), Aurelian (Enep), and others keep inventing stuff that is beyond chess!


H. G. Muller wrote on 2018-01-03 UTC

An extra man both means that there are many more material combiations, and that each combiation takes far more storage and time (like a factor 64 or 32 times as much). If 7 men took half a year, 8 men will take about half a century.

A reason to do it again would be ownership; the 7-men Lomonov EGT are a commercial enterprise, and you have to pay for the use of it. The type of EGT could also be an issue; I don't know whether Lomonosov is DTM or DTZ50, but whatever it is, one could want to have the opposite type.

Note that the 7-men EGT are good for looking up positions from the actual game, but are virtually useless for guiding the search (which would need probing of about a million times as many positions). Their size is so large that current storage media on anything but a super-computer cannot hold them. So access must be through the internet, which is thousands of times too slow to be of any use. EGT up to 6-men can still be stored on a typical had disk (or better yet, a solid-state replacement), and thus be accessed in reasonable time, although this still causes significant slowdown of the search.

Note that use of 5-men EGT by Chess engines typically improved their play by about 0 Elo. For 6-men there seems to be a small positive effect, like 10-20 Elo. This is most likely due to the fact that the current top engines have been developed while 6-men EGT were already available, and thus have been designed to be fully dependent on them, andrather clueless in their absense. Engines are typically developed only for Elo, and the the rating lists test them in games that are adjudicated as soon as the 5- or 6-men stage is reached. So who cares if their engine is not able to win KQK or KRK, when they get the point for free by adjudication anyway?


V. Reinhart wrote on 2018-01-03 UTC

@HGMuller,

As usual thanks for the info. I believe that there is only one institution that has produced a complete 7-man tablebase, and it required a few months using supercomputers in Moscow. I believe queries of the data can be made here:

http://tb7.chessok.com/probe

Since this has been completed, there is no reason for anyone to do it again. But I've been curious how much work it would take to expand it to an 8 man tablebase. Doing it completelly is probably currently not feasible, but from your description I would guess some "shortcuts" can be used to gain some end-game results for a range of 8 (or more) end-game positions.

Again, this is for normal chess, so you and Greg have a lot of work to do.;)


H. G. Muller wrote on 2018-01-02 UTC

@Greg: In WinBoard I distinguish two cases: official game end due to impossibility of help mate, and adjudication because of practical impossibility to force a mate against reasonable couter play. KNK and KBK (or more Bishops on the same shade) are official draws, KNNK, KBKN, KRKR are just impossible to win. For the latter type there usually are some tactical positions from where they could be lost (like mate in 1, or Rook capture in 3), so WinBoard does the adjudication (when enabled) only after a few moves. Note that FIDE rules also stipulate draws in some positions no engine or GUI would recognize, with impenetrable walls of Pawns separating the Kings and the pieces that could attack them.

To apply these rules to arbitrary fairy pieces requires kowledge that is not so trivial to obtain automatically, but usually easy to provide as part of the game definition. For orthodox Kings the possibility for help mates exists with single pieces that attack orthogonally adjacent squares, or any two pieces not bound to the same color. But for more general royal pieces it can be tricky. E.g. in Knightmate a Bishop superficially can cause a checkmate (Royal Knights on a1 and d4, Bishop on b2), but the position is unreachable from any 3-men position. To know if a mate can be forced would require generating a 3- or 4-men EGT. Sometimes you quickly see that the mate cannot be forced in general (such as with a pair of Knights or a Gnu), sometimes you have to calculate for many moves (e.g. KQKQ or Wazir + Ferz). But perhaps piece combinations where forcible mates can take many moves should never be adjudicated as draws.

@V.Reinhart: EGTs are always created by retrograde analysis. Doing this for a single 7-men end-game can take weeks. Each extra men basically drives up the storage requirement a factor 64 (32 if it is a color-bound piece), for standard 8x8 boards, and the generation time likewise. 4-men on 8x8 take only a second, however, and 5-men less than a minute, and can conceivably be done during a game.

There is a trick, however: these estimates only apply to pieces that have access to the full board, through reversible moves. Orthodox Pawns can only move forward, and the number of different Pawn constellations with 5 or 6 Pawns that are mostly blocking each other head to head can be surprisingly low. So in principle it should be easy to generate EGTs for Kings + 2 mobile pieces + a number of Pawns, even if the total number of men would be 6-10, during the game, provided the Pawns are sufficiently blocking each other. The point is that you only have to worry about the Pawn constellations that are still reachable.


Jeffrey T. Kubach wrote on 2018-01-02 UTC

Thanks Greg; I will try to provide a sample of the error message.  I should mention that I didn't see Review available when the computer was thinking (which is fine, as you had planned), but I had clicked on the "far back" and "far forward" buttons and that's when the error came up.

 


Greg Strong wrote on 2018-01-02 UTC

@H.G.,

Thanks for providing the heuristics.  I think I will implement this so it doesn't blindly trade it's way into a stalemate endgame thinking it is ahead.  It wasn't what I was thinking of though.  I'm wondering for which combinations of pieces the GUI should terminate the game and declare a draw.  Any combination of pieces that can't be arranged into a checkmate position even if the opponent walks his king into a corner would be a good start (and probably sufficient.)  But that could be hard to determine.  Probably would have to start with a simple piece property that specifies if that piece with just a king can checkmate another king (your Mating Minor property) and then only detect 3-piece forced draws.

@Jeff,

Thanks, I will look into this.  It's possible I didn't test with a completed game.  As a work-around, you could just do one "take back move" so that the game is no longer finished.  (First, be sure to uncheck "computer plays white" and "computer plays black" so it doesn't try to start playing when you take back a move.)  I'm also unsure why it would give you an error and crash during a game.  This was certainly tested.  Is the computer thinking when you try to go back?  That would certainly mess it up, although I think I put checks in place to prevent entering review mode when the computer is thinking.  When you get this crash, can you use the button on the crash dialog box to save out the error long and email it to me?


Jeffrey T. Kubach wrote on 2018-01-02 UTC

I should add that when loading a previously saved game - as long as the game was NOT finished, I was able to scroll through moves, but only in that particular instance (I think Review mode working on a finished game should be higher priority, my opinion)


Jeffrey T. Kubach wrote on 2018-01-02 UTC

Hi Greg, congrats on the release of Version 2.1!  It looks pretty good from what I've seen so far, but I did notice an issue on my end: I was trying the Review step-through option - both during the game and after the game.  During the game I would get an error message and crash, while after the game it would keep stating the results in a pop-up window (without being able to click through moves).  Was I doing something wrong or might this be a bug?


V. Reinhart wrote on 2018-01-02 UTC

@Aurelian - Happy new year!

@HGMuller - Thanks for the detailed answer. I really appreciate it.

I'm not sure if you can answer this or not, but you mentioned retrograde analysis can be done "on the fly" instead of pre-calculated. Obviosly this saves storage space, at the small cost of more code.

Do you have any idea what is the most men on the chessboard that can exist where this strategy can be used? The reason I ask is that tablebases have been created for normal chess with up to 7 men, but the storage space required was immense.

Could some storage space have been saved by using retrograde analysis instead, or can the 7-men tablebase be effectivelly expanded by adding a retrograde analysis in front of it (thus getting info on 8-men positions).

Not sure if that would be easy to answer, but curious if you or anyone knows.


25 comments displayed

Later Reverse Order EarlierEarliest

Permalink to the exact comments currently displayed.