This repository provides some libraries and binaries for scoring boggle boards. The emphasis is on performance, both in terms of implementation details and algorithmic advances. The most notable achievement of this code to date is finding the highest scoring 3x3 boggle board and proving that it is optimal in a few hours on a single machine. Best boards: 3x3: 545 streaedlp (exhaustive search -- proven) 3x4: 1651 slpiaentrdes (simulated annealing) 4x4: 3625 perslatgsineters (simulated annealing) Open problems are 3x4 and 4x4 boggle. To get started: $ git clone git://github.com/danvk/performance-boggle.git $ cd performance-boggle Basic checks: $ make clean $ make test ./trie_test: All tests passed! ./4x4/boggler_test: All tests passed! ./3x3/boggler_test: All tests passed! ./3x3/ibuckets_test: All tests passed! ./board-utils_test: All tests passed! ./4x4/ibuckets_test: All tests passed! $ make perf ./4x4/perf_test Loaded 172203 words into 385272-node Trie Trie contains 273917 childless nodes, 60848 words w/ children Total score: 22925120 = 105.977811 pts/bd Score hash: 0x000C1D3D Evaluated 216320 boards in 2.433583 seconds = 88889.509057 bds/sec ./4x4/perf_test: All tests passed! What the binaries do: solve: Reads in boards, prints out scores. $ echo "catdlinemaropets" | ./solve --dictionary words catdlinemaropets: 2338 neighbors: Read in boards, print all other boards w/in an edit distance of N. One "edit" is either a die swap or changing a letter in one square. $ echo "catdlinemaropets" | ./neighbors -d 2 | wc -l 267205 $ echo "catdlinemaropets" | ./neighbors -d 2 | sort -u | wc -l 122532 $ echo "abcdefghijklmnop" | ./neighbors -d 2 | sort -u | ./solve | sort -k2 -nr | head -1 abcderghisklmnop: 201 random_boards: Print out a bunch of random boards. $ ./random_boards -n 10000 | ./solve | sort -k2 -nr | head -1 bqphumsroteilstq: 445 anneal: Do simulated annealing to find a high-scoring board. $ ./anneal --max_stall 2000 ... final board: plessiagrtnrseed final score: 2960 bucket_boggle: Bucket letters into classes and forms a new dictionary by reducing the letter space. Reports the fraction of boards from a sample that can be eliminated (i.e. have an upper bound on their score less than 3625) using the given bucketing. $ ./bucket_boggle words 100000 ab cd ef gh ij kl mn op rs tu vw xy z Loaded 162848 words. 207 / 99793 ab cd ef gh ij kl mn op rs tu vw xy z : 0.99793 That means that 99.793% of boards (in normal board space) can be eliminated by using this bucketing. ibucket_boggle: Calculate an upper-bound on the highest score in a class of boards using "implicit buckets", i.e. without forming a new, bucketed dictionary. Takes a board where each cell is a class of letters. Reports the upper bound, the time it took to compute it and the number of boards represented in this class. This can sometimes eliminate a stupendous number of boards very quickly, e.g. the example below eliminates ~50 billion boards/sec. $ all=abcdefghijklmnopqrstuvwxyz $ ./ibucket_boggle $all b $all j $all jkx g $all h i $all jkx jkx jkx jkx $all Score: 3111 1.481485 secs elapsed Details: num_reps: 75066533568 = 75.066534B sum_union: 71079 max_nomark: 7465 max+one: 3111 (force cell 10) ibucket_breaker: Start with a random bucketed board (ala ibucket_boggle) created by setting each cell to one of a few letter patterns (usually 4). Compute an upper bound in the same way as ibucket_boggle. If it's < 3625, we're done. Entire class eliminated. If not, break one of the cells into its constituent letters and calculate upper bounds for each of those boards. Repeat until the entire board class has been "broken". One can imagine that, with the right classes of letters, this might be an effective way to "solve boggle". $ ./ibucket_breaker words ... 1612431360000 reps in 703.99 s @ depth 8 = 2290433843.342557 bds/sec: sy aeiou chlnrt bdfgjkmpvwxz aeiou sy bdfgjkmpvwxz aeiou bdfgjkmpvwxz bdfgjkmpvwxz bdfgjkmpvwxz chlnrt sy aeiou chlnrt chlnrt
neszt/performance-boggle
An attempt to find the highest-scoring Boggle board and prove that I've found it.
C++