neszt / performance-boggle Goto Github PK

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