Allegro.cc - Online Community

Allegro.cc Forums » The Depot » boggle solver

This thread is locked; no one can reply to it. rss feed Print
 1   2 
boggle solver
Thomas Fjellstrom
Member #476
June 2000
avatar

Also try the official D compiler against GDC. See if the gcc D front end causes any changes in performance.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

GullRaDriel
Member #3,861
September 2003
avatar

Thomas said:

The extra pointer indirection adds up if its done a lot.

Oh man, I totally forgot that ! It will only be noticeable on a very large set of 100% CPU usage computation thought ( As Matthew's boogle solver ) but I do not think I would see a big speed change in a game ;-p

"Code is like shit - it only smells if it is not yours"
Allegro Wiki, full of examples and articles !!

Thomas Fjellstrom
Member #476
June 2000
avatar

Quote:

but I do not think I would see a big speed change in a game ;-p

Maybe it it was used in a particle engine implementation.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

GullRaDriel
Member #3,861
September 2003
avatar

Well, any optimisation is to take in account.

"Code is like shit - it only smells if it is not yours"
Allegro Wiki, full of examples and articles !!

Neil Walker
Member #210
April 2000
avatar

Maybe I need a new computer ;)
Solved 100000 boards in 39.782001 seconds (2513.699569/s)

Does that mean scrabble allows abbreviations? The first entry in your list is AA

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

CGamesPlay
Member #2,559
July 2002
avatar

The rules of boggle are that you can't use the same tile twice in a word. And yeah, you already pointed out that you don't check for duplicates. Maybe a map-reduce scheme would be good here?

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Jonatan Hedborg
Member #4,886
July 2004
avatar

1boggle 100000
2Loading dictionary...OK
3395
4S D I O
5E I L B
6M T F W
7N I O N
8 
9626
10B R D T
11E N E O
12H I S H
13O D T L
14 
15644
16S S E H
17D A O N
18V N T R
19S I G T
20 
21833
22A N D C
23E C A D
24S T H E
25S A K R
26 
271097
28G U S V
29A O I E
30M T R S
31E O L R
32 
331149
34R G T L
35R E N E
36U A S I
37B H S Y
38 
391321
40S L S Q
41T A R S
42A V E E
43D T T R
44 
451358
46M A E Z
47H I S R
48S E E T
49W S T I
50 
511417
52R A M N
53G H E E
54D R S T
55B E E R
56 
571441
58N A E L
59T R E K
60A I S T
61M G E T
62 
631484
64S W R L
65O E E T
66S S N I
67R E Q D
68 
692317
70B N S E
71M A R T
72R E T E
73P T R R
74 
752349
76T E R E
77B R T T
78A S A A
79E E N I
80 
81Solved 100000 boards in 5.406000 seconds (18497.964754/s)

And

1 
2boggle 1000000
3Loading dictionary...OK
4351
5O I I C
6V C L N
7E O A F
8T R Z W
9 
10378
11F M O N
12E E E N
13D O O R
14D M I E
15 
16446
17Q I T N
18S E K H
19R O E A
20Y E L E
21 
22858
23T R E H
24I E M L
25E S T S
26B R P L
27 
281529
29M E O C
30R E R S
31N T E I
32A H S W
33 
341575
35O S R A
36R T E E
37A L E N
38L R O K
39 
401688
41E S S R
42S S A T
43V A R I
44E E H R
45 
462100
47T S N E
48S I D S
49O E R E
50R B A M
51 
522441
53D P S T
54A T E R
55R L A T
56H T S T
57 
582985
59R N E I
60I E S S
61S T E O
62O R A N
63 
64Solved 1000000 boards in 54.375000 seconds (18390.804598/s)

On a E8400 (dual, 3ghz, 2gb ram)

Matthew Leverton
Supreme Loser
January 1999
avatar

Quote:

Does that mean scrabble allows abbreviations? The first entry in your list is AA

No, but that's a word. There are a lot of weird two or three letter words. Note that in Boggle, you must have a minimum of three letters for the word to count. And in a 5x5 board, they must be four letters.

But regardless, I believe the official Boggle dictionary is more strict than the Scrabble dictionary.

Quote:

And yeah, you already pointed out that you don't check for duplicates.

Just to be clear, I mean duplicate words, not duplicate tiles. I've since added support for that and the Qu die. (Binary not updated yet.)

I store the found words in a fixed char* words[2000] array, starting at 0, and going onward for each new word. I just added a loop to check if the pointer already exists before adding the new word. I might be able to speed that up by switching to a fixed block of linked lists and inserting the words alphabetically.

CGamesPlay
Member #2,559
July 2002
avatar

The 'qu' die is easy: when making the dictionary, skip the letter after a 'q' (since the 'q' can only occur alongside a 'u' in Boggle).

How do you time? Are you counting core-seconds, or wall clock seconds? I wrote a solver, it gets about 57500 boards per second with 4 threads on my machine (31000 when optimizations are disabled). Also, how do you generate boards, since that has a large impact on solving time?

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Matthew Leverton
Supreme Loser
January 1999
avatar

QAT is not equivalent to QT.

Qu T
X  B

Not everybody plays that Qu must be a single unit. You can consider the U as optional. By unconditionally skipping the letter, the above board would think it found QAT as QT. Also, you must take care to calculate the points ahead of time since QUIT is four letters, not three as QIT would suggest.

I'm just counting the elapsed real world time after the dictionary loads.

My boards are all valid Boggle boards using the official dice. Thus there are 16 dice each with 6 different letters. Thus not every combination of letters is valid. I'm sure my board setup is quite slow since it just uses a dumb dice shuffle algorithm.

CGamesPlay
Member #2,559
July 2002
avatar

Good point on the Qs. What I do now instead is, after I've checked all adjacent spaces with the Q, I tack on a U and check all the adjacent spaces again.

The difference between a random board and one based off of the dice is staggering. My performance is down to 18000 boards / sec with these dice:

1const int Boggle::Dice[Size * Size][6] = {
2 { 'T', 'O', 'E', 'S', 'S', 'I' },
3 { 'A', 'S', 'P', 'F', 'F', 'K' },
4 { 'N', 'U', 'I', 'H', 'M', 'Q' },
5 { 'O', 'B', 'J', 'O', 'A', 'B' },
6 { 'L', 'N', 'H', 'N', 'R', 'Z' },
7 { 'A', 'H', 'S', 'P', 'C', 'O' },
8 { 'R', 'Y', 'V', 'D', 'E', 'L' },
9 { 'I', 'O', 'T', 'M', 'U', 'C' },
10 { 'L', 'R', 'E', 'I', 'X', 'D' },
11 { 'T', 'E', 'R', 'W', 'H', 'V' },
12 { 'T', 'S', 'T', 'I', 'Y', 'D' },
13 { 'W', 'N', 'G', 'E', 'E', 'H' },
14 { 'E', 'R', 'T', 'T', 'Y', 'L' },
15 { 'O', 'W', 'T', 'O', 'A', 'T' },
16 { 'A', 'E', 'A', 'N', 'E', 'G' },
17 { 'E', 'I', 'U', 'N', 'E', 'S' },
18};

I'll do an actual comparison between our programs when I get a Windows machine, since your program won't work under Wine with multiple threads.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Matthew Leverton
Supreme Loser
January 1999
avatar

I would stick with your original Q implementation and calculate the points at word list load time:

QAT => QAT (3 letters, 1 point)
QUIT => QIT (4 letters, 1 point)
QUEUE => QEUE (5 letters, 2 points)

It only won't work if this creates an ambiguity, but I'd not care if on rare occasion it got the score wrong by a point. If you want to treat QU as a unit, then remove impossible words like QAT from the dictionary.

A given die is only going to be Q about 1% of the time, so it's not a huge difference but every little bit counts.

The dice are designed to make the game playable. So the solver will take more time going down more valid paths. There's actually a couple sets of dice depending on the version of Boggle. I don't have my source with me, but I think I'm using:

AAEEGN
ABBJOO
ACHOPS
AFFKPS
AOOTTW
CIMOTU
DEILRX
DELRVY
DISTTY
EEGHNW
EEINSU
EHRTVW
EIOSST
ELRTTY
HIMNQU
HLNNRZ

CGamesPlay
Member #2,559
July 2002
avatar

My node structure is actually very stripped down:

  bool endPoint, hasChildren;
  Node* children[26];
  Node* parent;

It doesn't event know what letter it is. Also, when I find a solution, I just keep a record to the node that contained it, which describes a unique word. This trivializes the storing of solutions, since it's just a pointer to the end node.

I want to rearrange the way the dictionary works, though. I'll have to do more testing.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Matthew Leverton
Supreme Loser
January 1999
avatar

How do you calculate the score in an efficient manner?

My node structure is similar; instead of endPoint, I have a pointer to a Word struct (or null if it isn't valid) and I don't have any hasChildren flag.

CGamesPlay
Member #2,559
July 2002
avatar

When I test on the same machine, your program has a good half second on mine that I can't seem to get rid of. Here's some output:

1Loading dictionary...OK
2312
3O R G H
4K M O N
5E A M S
6H E G T
7 
8328
9Y O E E
10Y M E N
11M O A A
12X S E N
13 
14483
15L W G T
16L E Y F
17S E S I
18U N N B
19 
20681
21C E A W
22S E H T
23E R N D
24C P A E
25 
26795
27L T M U
28R S A L
29S A N S
30H T D E
31 
32840
33G B R I
34L I A E
35Y E T T
36N O O R
37 
381035
39Z H R E
40S U B U
41H S R S
42I E T E
43 
441498
45U R I A
46O E E D
47T D R S
48T A T I
49 
501570
51G S T H
52M S E R
53A T E T
54W R O Z
55 
561778
57I I S F
58T T N T
59E G A U
60S R B L
61 
621923
63I S D M
64E R E O
65E R S V
66I T O E
67 
68Solved 10000 boards in 3.125000 seconds (3200.000000/s)

And my program:

C:\projects\boggle>cl cgp_boggle.cpp getopt.c /I.\ pthreadvc2.lib winmm.lib /nol
ogo /EHsc /Ox && cgp_boggle -n 10000 -j 8
cgp_boggle.cpp
Generating Code...
Compiling...
getopt.c
Generating Code...
Random seed 1606
Dictionary created
267627 words, 597827 nodes, 69.0 MB
Longest word is 15 letters
Solved 10000 boards in 3.547000 seconds (2819.283902 boards / s)
0 boards had no words

I'm trying lots of different things to squeeze more speed out of it, but it's tricky to find trouble spots because the entire operation takes place in one function :)

[append]
I attached a Windows binary.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Matthew Leverton
Supreme Loser
January 1999
avatar

My program is even faster without the output. ;)

It could be a difference in the compiler's optimization. I used gcc (probably 3) using -O3 and few other switches that may already be included in O3. With fewer optimizations it was noticeably slower.

Are you using recursion?

CGamesPlay
Member #2,559
July 2002
avatar

Yeah, the output really does slow the programs down. I also don't even keep track of boards that were high scores, but neither do you :P

[edit]

You should try adding a hasChildren field. It gives me a moderate boost versus when I disable it. It is only used for endpoints, to see if the program should bother continuing to search along this path. IIRC, it gave me an extra ~200 boards / sec.

I'm calling my version finished until somebody steps up and beats it. My speed boosts came from optimizing score calculation and unrolling the loops. I had to resort to the preprocessor to do that, so the code is somewhat ugly now. I tried doing the same using templated functions, but the compiler couldn't optimize as well. The solver has 2 loops and 9 gotos :)

On a trial of 100 000 boards, your solver took 29.70 seconds, solving 3366.66 boards / second. My solver took 27.67 seconds, solving 3613.76 boards / second, which is 6.84% faster. Your solver uses 3 MB less memory, though.

By the way, how many boggle boards are there? 16! * 166, right? If that's right, it'll take 1.5 billion processor-years to solve all of them on my box, which has 4 processors (Q6600). It'd be fun to write a distributed solver to collect stats on the boards. Each work packet could be one arrangement of dice, where the client has to try all the permutations of the dice without moving them: it would take about 10 minutes on my Q6600, and there's only 20 trillion of those.

Anyways, attached is a Windows binary and the source code. The source code has getopt.{cpp,h}. Linux users should ignore them.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Matthew Leverton
Supreme Loser
January 1999
avatar

I won't be able to compare for a few days, but...

Quote:

By the way, how many boggle boards are there? 16! * 16^6, right?

In general, yes. But 16^6 can be reduced because some dice have duplicates and 16! can be reduced because some boards are mirror images.

 1   2 


Go to: