Glaurung 0.2.0/0.2.1: Thanks!

[Tord Romstad]

Hi all,

During the last 24 hours, I have received a tremendous amount of help in the frustrating task of making Glaurung's new book code work correctly in Windows. After the latest suggestions by Alessandro, Jon and Fabien, I think the problem is finally solved. Simply changing the last argument of fopen() from "r" to "rb" seems to do the trick.

I would like to give a big thanks to Alessandro, Anastasios, Dann, Fabien, Geoff, Jim, Jon and Tim for your efforts to solve my problem. Thanks also to Pallav for suggesting that I put a link to my Web site in my profile.

The source code for Glaurung 0.2.1 is now corrected. The version number stays the same -- I thought the addition of a single character to the source code was too tiny to increment the version number. The Cygwin executable is still the only one I have for Windows, but now it should be easy to compile 0.2.1 with book support with a better compiler. I hope Dann or somebody else can produce a fast executable before the start of AEGT4 Rook Class tomorrow morning.

Tord

[Tim Foden]

Hi all,

I would like to give a big thanks to Alessandro, Anastasios, Dann, Fabien, Geoff, Jim, Jon and Tim...

Thanks for the mention, but I don't think I was really any help at all! I was too busy debugging my new DTM table base generator. GLC has had a KPK distance-to-promotion generator for quite some time, and I've been meaning to get around to writing a full DTM and W/L/D generators (for in-memory bitbases) for quite some time. Now that loads of others seem to be working on recognisers, I decided I'd have a go this weekend. So far it only manages to generate KRK and KQK correctly (although I've not tested extensively yet)... KPK DTM is still somewhat of a problem... is there really a mate-in-41? (no there isn't)

Cheers, Tim.

[Norm Pollock]

Tord, I am very glad that this obstacle has been overcome.

However I fail to grasp the importance of this issue, no doubt due to my own lack of understanding. I did not want to ask this question while the search for a solution was going on. But now that the solution has been found, I will ask.

Since Glaurung is an UCI engine, and UCI engines run in guis like Arena/Fritz, what is wrong with having the book being supplied by the gui? Why was it so important for Glaurung to access directly its "own" book?

-Norm

[Tord Romstad]

I would like to give a big thanks to Alessandro, Anastasios, Dann, Fabien, Geoff, Jim, Jon and Tim...

Thanks for the mention, but I don't think I was really any help at all!

Well, at least you tried, despite being busy doing much more interesting things. It's more than I deserve.

I was too busy debugging my new DTM table base generator. GLC has had a KPK distance-to-promotion generator for quite some time, and I've been meaning to get around to writing a full DTM and W/L/D generators (for in-memory bitbases) for quite some time.

This is interesting. The endgame is one of the things I will focus on in Glaurung in the near future (in addition to cleaning up the increasingly messy source code, tuning eval and search parameters, and trying to figure out why my program is so damn slow). I am not sure I will want to use bitbases, but at least they are worth a look.

Do you have any recommendations about places to start learning about bitbase generation? I don't want to use Nalimov EGTBs (except possibly for verification), because I didn't write the code.

Tord

[Robert Allgeuer]

From a user perspective:

I find it absolutely ANNOYING in engines such as Shredder, that I am bound to the original GUI, when I wanted to run it with its native and probably strongest book. Why having a standard (UCI in this case), when "benefitting" of its interoperability advantages means that I cannot use the one book that has been created and tuned for its playing style just because I am so "bold" to use it in Arena or ChessPartner rather than the original GUI?

In my view there is a chess playing entity which consists of book and engine, and I think it is a good move to keep those together. So one has the choice: native, original book available in any GUI or using possibly also any other GUI book.

A good solution btw to this problem has Lokasoft and Deep Sjeng: They use the same format for the native and GUI book.

Robert

[Tord Romstad]

Hi Norm!

Since Glaurung is an UCI engine, and UCI engines run in guis like Arena/Fritz, what is wrong with having the book being supplied by the gui? Why was it so important for Glaurung to access directly its "own" book?

The main reason is that not all GUIs have any book support. This is a particularly big problem on my own platform (Mac OS X), where both of the two GUIs I am using (xboard and Sigma Chess) lack book support. The problem is not quite that bad under Windows, but there are still a significant number of users who use Winboard.

Another important point is that even though many or even most GUIs include some kind of books, there is no single book format which works everywhere. If I ever want to make a special tournament book for Glaurung, this book would only work in a single GUI. It is much better to be able to use the same book everywhere.

Book learning is also an issue. I currently have no plans of implementing this, but I want to leave the possibility open for the future. This is not possible unless Glaurung is able to read and manipulate its own book file.

Finally, there are a few tournaments where the engines are expected to play with their own book, and engines without such a book are forced to play with a small, crippled book or no book at all.

Tord

[Tord Romstad]

A good solution btw to this problem has Lokasoft and Deep Sjeng: They use the same format for the native and GUI book.

And that, in fact, is precisely what I intend to do myself. This is why my book contains so much information. In addition to the moves themselves, my book file contains statistics about the number of wins, losses and draws for each move in the PGN database used to build the book. I plan to include the ability to browse the opening book in the GUI, and I think being able to see the statistics for each move would be interesting.

By the way, I hope you wait for an optimised Windows executable of Glaurung 0.2.1 before you start testing it in YABRL. I don't think you'll have to wait very long.

Tord

[Robert Allgeuer]

Tord, you plan to write a GUI?

I will wait for a faster compile of Glaurung

Robert

[Tord Romstad]

Tord, you plan to write a GUI?

Yes, I have been working on a Mac OS X GUI for a long time. Progress is extremely slow. Unfortunately there is still no Macitosh GUI which satisfy my needs. Xboard is not a native Mac OS X program, and is completely unusable for the vast majority of Macintosh users. Sigma Chess has some nice features, but lacks support for xboard engines, does not have the ability to run engine matches, and is not free. Neither GUI can be used for hexagonal chess (the hexagonal version of Glaurung is still private, because of the lack of a suitable GUI).

Tord

[Tim Foden]

I was too busy debugging my new DTM table base generator. GLC has had a KPK distance-to-promotion generator for quite some time, and I've been meaning to get around to writing a full DTM and W/L/D generators (for in-memory bitbases) for quite some time.

This is interesting. The endgame is one of the things I will focus on in Glaurung in the near future (in addition to cleaning up the increasingly messy source code, tuning eval and search parameters, and trying to figure out why my program is so damn slow). I am not sure I will want to use bitbases, but at least they are worth a look.

Do you have any recommendations about places to start learning about bitbase generation? I don't want to use Nalimov EGTBs (except possibly for verification), because I didn't write the code.

Tord

When I first wrote my KPK dist-to-promotion generator, I just tried to figure it out by myself. I learned a few things then, but trying to write a general DTM I did look at a couple of sources...

1. The source to Steven Edwards' table base generator. I've got a copy of this if you'd like me to mail it to you. I got it directly from Steven when I had a disk go down, and I could no longer find a copy of it on the net.

2. The Wu + Beal paper ("A Memory Efficient Retrograde Algorithm and
Its Application To Chinese Chess Endgames") that talks about their improved generator. This gives some psuedo code for the main algorithm, but you still have to figure out a lot of things that they don't say (I find this with most papers that have interesting algorithms!)

Basically you have to:

1. Figure out what indexing scheme you want, and implement it. This must be able to translate an index to a position, and vice-versa.

2. Initialise the indexer with a TB constellation.

3. Get the size of the TB from the indexer.

4. Allocate the memory (or disk space, whatever). One table for WTM, and one for BTM.

5. Scan all positions, and mark the ones that are broken, mate and stalemate. Strictly speaking I don't think you need to mark the stalemates, but it costs nothing and can't hurt. All others in the table are marked as unknown.

6. Start iterating over mate distances, starting from n = 1 (we've already found all lost-in(0) positions).

7. For each WTM unknown position, generate moves, and see if we can get to a BTM lose-in(n - 1) position. If so, mark this pos as mate-in(n).

8. For each BTM unknown position, generate moves, and see if we can get to a WTM lose-in(n - 1) position. If so, mark this pos as mate-in(n).

9. For each WTM unknown position, generate moves, and see if the best we can get to is a BTM mate-in(n) position. If so, mark this pos as lose-in(n).

10. For each BTM unknown position, generate moves, and see if the best we can get to is a WTM mate-in(n) position. If so, mark this pos as lose-in(n).

11. Increment n and repeat from step 7. if we changed anything.

12. We're done.


For steps 7 through 10, when scanning for unknown positions, you can cut down the work by working backwards from the target values in the source TB, and generating reverse moves. I don't do this yet, as I still haven't figured out how to cope with reverse transitions from other TB's (and I haven't implemented the reverse moves, but they're pretty much the same as the forward ones, except for pawns).

GLC has had the Edwards indexing scheme implemented for some time. I used it to calculate some stats from them (the Edwards TBs), and to probe positions. I have found this useful in debugging my generator.

Nalimovs indexing scheme is way more complicated, so I don't think I'll be trying it any time soon.

For my indexing I used folding of the 2 kings, flank if pawns are involved, and 8-symmetry if no pawns, with 48 squares for pawns and 64 for other pieces. I may try to do a bit better than this later. I haven't implemented en-passant yet either.

Cheers, Tim.

[Fabien Letouzey]

Do you have any recommendations about places to start learning about bitbase generation? I don't want to use Nalimov EGTBs (except possibly for verification), because I didn't write the code.

Yes, read papers about games other than chess.

Checkers (Chinook), Nine Men's Morris, Awari, ...

I think many programmers, including me, are interested in bitbases. We should coordinate our efforts unless you want to solve the problem entirely on your own.

Last year I started writing a generator, but a more efficient indexing scheme is needed. Another possibility is of course to convert DTM bases.

Compression is also an important topic, I don't expect all users to download gigabytes of specific data.

Fabien.

[Tim Foden]

I don't want to use Nalimov EGTBs (except possibly for verification), because I didn't write the code.

Yes, I kind of feel the same way, which is why I'm doing this stuff myself. If I didn't have to ask permission then it may be a different matter, although I did implement the Edwards indexing scheme rather than use the code from Crafty.

I think many programmers, including me, are interested in bitbases. We should coordinate our efforts unless you want to solve the problem entirely on your own.

I would agree about coordinating efforts. I've thought about writing a public domain tbgenerator and access code. However, I write in C++ really, not C, so maybe it wouldn't be so useful.

Last year I started writing a generator, but a more efficient indexing scheme is needed. Another possibility is of course to convert DTM bases.

I was thinking about indexing last night, and something in the Wu/Beal paper made me think of using 3 pieces (KK*) for the initial indexing rather than just the 2 kings. With strictly legal positions of all of these 3 pieces, tables like KQK BTM would be vastly reduced. Nalimov just uses the 8 squares around the Q? If we used all the square it would be even better.

Of course you can convert DTM bases too, but they still need to be generated. I guess Nalimov's bases would be used?

Compression is also an important topic, I don't expect all users to download gigabytes of specific data.

Fabien.

True. I have been writing a compressor too, but maybe zip would be OK, although better compression than zip may be possible of course. Are there any freely usable compressors that are likely to be better, or would we need to write our own one?

Cheers, Tim.

[Alessandro Scotti]

There's also a "cheap" approach to bitbase generation, which maybe could be considered "cheating" but to be honest I wouldn't mind using, i.e. use EGTB to get the result and then re-encode it with your favorite method...

[Tim Foden]

There's also a "cheap" approach to bitbase generation, which maybe could be considered "cheating" but to be honest I wouldn't mind using, i.e. use EGTB to get the result and then re-encode it with your favorite method...

Yes, this method was mentioned somewhere above.

We were also discussing the second part... the favourite method.

I think it would be good to have a set of BitBases that everyone could share, and Fabien thought that a better indexing scheme could be used for them.

We should also consider the TBs like KNKN, which only have a small number of Mate-in-1, Lose-in-0 positions, and the rest are draws. For these we just need to store a table of indexes and scores, rather than the whole TB.

Cheers, Tim.

[Tim Foden]

Last year I started writing a generator, but a more efficient indexing scheme is needed.

I forgot to ask what kind of scheme you were using that you considered inefficient.

Some further thoughts on the 3 piece indexing that I thought of using.

If you take the KQKR TB, if we index using KRK for the WTM db, and using KQK for the BTM tb, and exclude all invalid (broken) positions in these indexes, the tables will be a lot smaller than just using 462 * 62. The 62 would be a worst case, with the best case for the KRK being 462 * (62 - 13) {-21%} and for the KQK being 462 * (62 - 27) {-43%}.

Would something like this fit your criteria?

You may also be able to get a 4 piece index running when both the extra pieces are the same, e.g. KRRKQ indexing using KKRR.

Cheers, Tim.

[Tony van Roon-Werten]

I was thinking about indexing last night, and something in the Wu/Beal paper made me think of using 3 pieces (KK*) for the initial indexing rather than just the 2 kings. With strictly legal positions of all of these 3 pieces, tables like KQK BTM would be vastly reduced. Nalimov just uses the 8 squares around the Q? If we used all the square it would be even better.

Cheers, Tim.

The problem is that an illegal position position in KQK might be legal in KQNK because the knight is blocking the check.

So you have to find a way to notice this, and somehow add these again to the index.

Tony

[Tim Foden]

The problem is that an illegal position position in KQK might be legal in KQNK because the knight is blocking the check.

So you have to find a way to notice this, and somehow add these again to the index.

Thanks for pointing this out Tony. Now that you have said it I vaguely remember reading about this before.

I'm glad someone told me before I actually got down to trying to code it!

Cheers, Tim.

[Tord Romstad]

Do you have any recommendations about places to start learning about bitbase generation? I don't want to use Nalimov EGTBs (except possibly for verification), because I didn't write the code.

Yes, read papers about games other than chess.

Checkers (Chinook), Nine Men's Morris, Awari, ...

Thanks, I will see what I can find. Thanks also to Tim for his excellent 12-step list, which should be sufficient to get me started.

I think many programmers, including me, are interested in bitbases. We should coordinate our efforts unless you want to solve the problem entirely on your own.

Great idea, but I will have to spend some time learning the basics before I can make any useful contributions.

Tord

[Fabien Letouzey]

Hi Tim,

Yes, I kind of feel the same way, which is why I'm doing this stuff myself. :) If I didn't have to ask permission then it may be a different matter, although I did implement the Edwards indexing scheme rather than use the code from Crafty. :?

Permission is really annoying, but huge code size (due to C++ templates) would still be a problem.

I would agree about coordinating efforts. I've thought about writing a public domain tbgenerator and access code. However, I write in C++ really, not C, so maybe it wouldn't be so useful. :)

Eugene's code is also C++ and dozens of engines are using it?!
Not a problem then.

I was thinking about indexing last night, and something in the Wu/Beal paper made me think of using 3 pieces (KK*) for the initial indexing rather than just the 2 kings. With strictly legal positions of all of these 3 pieces, tables like KQK BTM would be vastly reduced. Nalimov just uses the 8 squares around the Q? If we used all the square it would be even better.

Sorry I got you confused. I meant my I did not work at all on indexing, so as to focus on generation speed (to get an idea how much time would be needed). Schemes described in Heinz's book are good enough. IMO unclockable checks is uncalled-for complexity.

True. I have been writing a compressor too, but maybe zip would be OK, although better compression than zip may be possible of course. Are there any freely usable compressors that are likely to be better, or would we need to write our own one? :)

I was thinking about real-time decompression, with a specific algorithm. The RLE + Huffman mix described in the "recent" Chinook papers looks near-perfect to me.

Anyhow, I really think it's become a programmer-only topic by now!

Fabien.

[Jon Kreuzer]

I recently added more win/draw/loss bitbases to Slow Chess.
It seems like my interest in bitbases differs from other posters in this thread though. At least so far I just added a few specific important endings, and haven't tried to create a generalized scheme. (Also I didn't generate the w/d/l results of any of the 4 men bitbases myself.)

The bitbases are compressed in memory, but I was less interesting in getting decent compression than in keeping it faster than doing a normal eval (It just does 2 table lookups to probe) since I use them in the QSearch and only use a few 4-men.

If anyone is interested I can put my bitbases and source code to access (~160 lines) on my webpage. (I considered this before, but I assumed there would be no interest.)

I use KPK, Pawn Race, KPKQ, KPKR, KPKP, KPPK, and KPPKP (where a black and white pawn are locked.) Together they total 1.7 megs in memory, 561 KB as a zipped download.

Also a question, I'm curious if anyone can think of any other important 4-men endings for W/D/L.