[fofvhzyk] Chessbase Christmas puzzles in FEN

Chessbase 2009 "anti-computer" Christmas puzzles in a form more amenable to feeding to computers, namely FEN.

D. Djaja 1972 White to play and draw
6R1/P2k4/r7/5N1P/r7/p7/7K/8 w - - 0 1

W.E. Rudolph, La Stratégie 1912 (William E. Rudolph of Brooklyn, NY page 184 of the March 1911 Chess Amateur) White to play and draw
3B4/1r2p3/r2p1p2/bkp1P1p1/1p1P1PPp/p1P1K2P/PPB5/8 w - - 0 1

J. Hašek, Národní Listy 1951 White to play and draw
8/1p6/1Pp2N1Q/p1Ppk2p/P3p3/3PPpPp/3K1P1P/1R6 w - - 0 1

M. Matous, 1.hm Szachy 1975 White to play and win
n2Bqk2/5p1p/Q4KP1/p7/8/8/8/8 w - - 0 1

From Vitaly Chekhover, Gatchinskaja Pravda, 1954 White to play and draw
8/8/8/5Bp1/7k/8/4pPKP/8 w - - 0 1

Vitaly Chekhover, Gatchinskaja Pravda, 1954 White to play and draw (is 1.Rh8+ Kg4 2.Rf8 c1Q 3.h3+ Kf4 4.Be6 Ke5 5.Bxf5 Qa3 6.Rf7 Qf3+ 7.Kg1 e3 8.Re7+ Kf6 9.Rxe3 Qxf5 an alternate solution?)
1R6/8/8/5bp1/4p2k/8/B1p2PKP/8 w - - 0 1

Vitaly Chekhover, Gatchinskaja Pravda, 1954 (after 1.Rh8+) Black to play and White to draw
7R/8/8/5bp1/4p2k/8/B1p2PKP/8 b - - 1 1

From a study by Smyslov White to play and win
2b1rk2/5p2/p1P5/2p2P2/2p5/7B/P7/2KR4 w - - 0 1

A. A. Troitzky, Magyar Sakkvilág 1931 White to play and win
1R4bq/p1p3p1/2p3Pb/k1P3PR/2P4P/p1K5/P7/8 w - - 0 1

A. A. Troitzky version Pal Benko, 2007 White to play and win
1R4bq/p1p3p1/2p3Pb/k1P4R/2P4P/p5P1/P7/1K6 w - - 0 1

Sandipan Chanda, 2009 White to play and win
k7/n1p1p1K1/P1p1Pp2/5P2/3R3P/pB6/2p5/2r5 w - - 0 1

Vitaly Chekhover, Parna Ty Bull 1947 White to play and draw
7r/p3k3/2p5/1pPp4/3P4/PP4P1/3P1PB1/2K5 w - - 0 1

F. Simkovitch, 3.hm L'Italia Scacchistica 1923 White to play and draw
2br4/r2pp3/8/1p1p1kN1/pP1P4/2P3R1/PP3PP1/2K5 w - - 0 1

Noam Elkies, 1991 White to play and draw
8/1p6/1p6/kPp2P1K/2P5/N1Pp4/q2P4/1N6 w - - 0 1

[ilqixood] Generating random numbers faster

Consider the benchmark task of generating 2,000,000,000 random integers each between 0 and 3. This was the inner loop of a random walk on an integer lattice.

We use rand(), the system library random number generator, which on Linux GNU libc (glibc), happens to be a lagged Fibonacci generator. All programs were compiled with g++ -Wall -DNDEBUG -O99 with gcc 4.2.4.

If we scale the output of rand() the "right" way, i.e., first converting to double (float only has 23 bits of precision), dividing through by RAND_MAX+1.0, multiplying by 4, and casting to int, we get this program. We do not sample the lower bits because the are supposedly less random than the upper bits. The run time is 159.174 seconds.

Noting that RAND_MAX = 2³¹-1, we can scale for ranges that are powers of two by simply a right shift. This gets us this program. The run time is 75.257 seconds, or a speedup of 2.1 times over the base "floating point" implementation.

Examing the open-source source code to rand(), we see that it has considerable overhead due trying to handle various types of random number generator state sizes. Also, because it is in a separately compiled library, it cannot be inlined. Let us manually reimplement the same random number generator algorithm in an inlineable C++ class. This gets us this program. The run time is 12.457 seconds, or a speedup of 6.0 times over the "pure integer" implementation, and a speedup of 12.8 times over the "floating point" implementation.

These are some spectacular speedups. Note that all three programs produce exactly the same result (namely, 2999980260); that is, they are all implementing the exact same random number algorithm (and scaling), resulting in exactly the same stream of random integers between 0 and 3.

While researching the internals of rand(), I encountered Bug libc/3662 "Implementation bugs in random_r and friends".

[jvcvfvjo] Point growth tree growth

I'm growing a virtual tree (in the computer science sense: a connected graph with no loops). Here are snapshots of its growth, scaled.

[ttkkuggc] Block agar

An animated GIF of the degradation of the block agar in Conway's game of life. The "camera" pans diagonally up and to the left at the same rate (3c/4) as the agar degrades. It's four generations per frame, which keeps the untouched blocks in the same (relative) place in the frame.

The other image is a snapshot of the whole thing (huge image, may crash your browser or operating system) at generation 8000.

Block Agar