|
This thread is locked; no one can reply to it. |
1
2
|
boggle solver |
Thomas Fjellstrom
Member #476
June 2000
|
Also try the official D compiler against GDC. See if the gcc D front end causes any changes in performance. -- |
GullRaDriel
Member #3,861
September 2003
|
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" |
Thomas Fjellstrom
Member #476
June 2000
|
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. -- |
GullRaDriel
Member #3,861
September 2003
|
Well, any optimisation is to take in account. "Code is like shit - it only smells if it is not yours" |
Neil Walker
Member #210
April 2000
|
Maybe I need a new computer Does that mean scrabble allows abbreviations? The first entry in your list is AA Neil. wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie |
CGamesPlay
Member #2,559
July 2002
|
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? -- Ryan Patterson - <http://cgamesplay.com/> |
Jonatan Hedborg
Member #4,886
July 2004
|
And
On a E8400 (dual, 3ghz, 2gb ram)
|
Matthew Leverton
Supreme Loser
January 1999
|
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
|
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? -- Ryan Patterson - <http://cgamesplay.com/> |
Matthew Leverton
Supreme Loser
January 1999
|
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
|
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:
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. -- Ryan Patterson - <http://cgamesplay.com/> |
Matthew Leverton
Supreme Loser
January 1999
|
I would stick with your original Q implementation and calculate the points at word list load time: QAT => QAT (3 letters, 1 point) 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
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
Matthew Leverton
Supreme Loser
January 1999
|
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
|
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:
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] -- Ryan Patterson - <http://cgamesplay.com/> |
Matthew Leverton
Supreme Loser
January 1999
|
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
|
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 [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. -- Ryan Patterson - <http://cgamesplay.com/> |
Matthew Leverton
Supreme Loser
January 1999
|
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
|