tromp

1139 ms·

3721.
by tromp 11y ago
I'm hoping Cuckoo Cycle can change that ( https://github.com/tromp/cuckoo )
3722.
by tromp 12y ago
but pretty awesome at mining the cpu-friendly Cuckoo Cycle... https://github.com/tromp/cuckoo
3723.
by tromp 12y ago
Are these the only two programming languages that are also well-known games? http://en.wikipedia.org/wiki/Nim http://en.wikipedia.org/wiki/Go_%28game%29
3724.
by tromp 12y ago
A slightly less obfuscated and somewhat more normally formatted version: #include <stdio.h> #include <stdlib.h> #include <assert.h> enum {I,O,V,A,L}; int n=44,i,c,T[M]={L,A,8,A,2, V,0,L,L,V, A,30,L,A,2,V
3725.
by tromp 12y ago
The (binary) lambda calculus interpreter at http://www.ioccc.org/2012/tromp/tromp.c , documented in http://www.ioccc.org/2012/tromp/hint.html is as tiny (and incomprehensible) as it gets,
3726.
by tromp 12y ago
Closely related are Judy Arrays (aka Judy Trees): https://en.wikipedia.org/wiki/Judy_array
3727.
by tromp 12y ago
Admittedly, the 512GB in one server is mostly for convenience. In each round, I run 8 processes each using 63GB, which could in principle also be farmed out to other machines with some more administrative and monitoring overhead.
3728.
by tromp 12y ago
Most time is spent normalizing, encoding, decoding, and sorting so-called border states, compact 18*3-bit descriptions of all information needed about a partial board position to determine its legal full-board completions. This code is fair
3729.
by tromp 12y ago
Although rulesets might differ on what is considered a legal move, they all agree on what is a legal position: one where every connected group of stones has liberties (empty adjacent point). Furthermore, in all rulesets you can reach any le
3730.
by tromp 12y ago
Indeed, the Japanese rules are not suitable for mathematical analysis of the game; see https://en.wikipedia.org/wiki/Rules_of_go#Counting_phase That's why our paper "Combinatorics of Go" assumes the so-c
3731.
by tromp 12y ago
As George Mallory said when asked "Why did you want to climb Mount Everest?" "Because it's there." The number of legal Go positions is a simply defined number that is easily approximated but an enormous computationa
3732.
by tromp 12y ago
It would take at least a nanosecond for each position. Given that 6x6 already has 62567386502084877, it would take at least 724 days. To take "practically forever", 7x7 more than suffices:)
3733.
by tromp 12y ago
Few people can believe that there are as many as 386,356,909,593 games on the tiny 2x2 board. Needless to say, nothing is pruned there either. A game could visit as many as 48 of the legal positions and have dozens of passes (but only 2 con
3734.
by tromp 12y ago
I'm not pruning any board symmetries. So, yes, the 4x4 position with only one Black stone adjacent to a corner would be counted 8 times (with the Black stone at A2 or A3 or B1 or B4 or C1 or C4 or D2 or D3). The only symmetry that the
3735.
by tromp 12y ago
Are you asking whether it's possible to determine all possible 1-move predecessors of a given position? If so, then yes, that is pretty straightforward. E.g. the last move was either a pass, or a move by White, or a move by Black. For
3736.
Number of legal 18x18 Go positions computed. One more to go(tromp.github.io)
229 points by tromp 12y ago|109 comments
3737.
by tromp 12y ago
A small error I noticed: After explaining the difference between subset and strict_subset, they claim that for all A empty_set strict_subset A which obviously fails when A is itself empty.
3738.
by tromp 12y ago
> it's just a lot harder to right a self-interpreter in lambda calc. Here's one for the http://en.wikipedia.org/wiki/Binary_lambda_calculus , all of 29 bytes long, including parsing: 01010001101000000
3739.
by tromp 12y ago
"Too slow for its memory usage" means that that in order to use large amounts of memory, it becomes impractically slow. One of the non-finalists (Centrifuge) was criticised for byte-grained random memory accesses. A random access
3740.
by tromp 12y ago
That sabotage was "necessitated" by the desire for fast proof-of-work verification. With hashcash, proof attempt is as hard as proof verification, but there are other asymmetric schemes where the former is much harder. The first s
3741.
by tromp 12y ago
Forming a spanning tree; or equivalently, having a unique path between any two cells. Sometimes a few additional connections (adding cycles to the spanning tree) are considered ok.
3742.
by tromp 12y ago
My Fhourstones solver and a perfect playing applet may be found at http://tromp.github.io/c4/c4.html
3743.
by tromp 12y ago
How do these compare space and performance wise with Judy arrays, which are 256-ary trees whose nodes also distinguish between sparse and dense subsets? https://en.wikipedia.org/wiki/Judy_array
3744.
by tromp 12y ago
The second example on http://en.wikipedia.org/wiki/Obfuscation_%28software%29 is a 7 line maze that generates arbitrary length mazes. Its construction is described at http://tromp.github.io/maze.html
3745.
by tromp 12y ago
Minor nitpick: the first real line of code alphabet = "abcdefghijklmnopqrstuvwxyz" is better written as alphabet = ['a'..'z'] This is really syntactic sugar for enumFromTo 'a' '
3746.
by tromp 12y ago
By the same token, most numbers are more than 8 digits long. In fact, most are over a billion digits long. Although I've never see a single one in the wild...
3747.
by tromp 12y ago
It's not like Go where you can actually count the number of reachable positions. Deciding whether a single chess position is reachable can be really hard. There is a whole class of so called "retrograde" chess problems focuss
3748.
by tromp 12y ago
And then there's this version > There are two doors with goats and one with a car. You choose one door from the three. The host may select one of the doors with a goat from the remaining two doors, and open it. Should you switch doo
3749.
by tromp 12y ago
We have excellent approximations; for 19x19 the number is known to be approximately 2.081681994 * 10^170. Getting the exact number is the big challenge. You can see in the paper that we spent a lot of effort on reducing the complexity of th
3750.
by tromp 12y ago
No. Every legal position is easily reachable by having the side with fewer stones pass the requisite number of turns.

More ›