You can subscribe to this list here.
2005 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(15) |
Aug
|
Sep
(72) |
Oct
(34) |
Nov
(10) |
Dec
(20) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2006 |
Jan
|
Feb
(22) |
Mar
(9) |
Apr
(11) |
May
(18) |
Jun
(68) |
Jul
(10) |
Aug
(4) |
Sep
(13) |
Oct
(29) |
Nov
(21) |
Dec
(24) |
2007 |
Jan
(32) |
Feb
(19) |
Mar
(11) |
Apr
(14) |
May
(8) |
Jun
(7) |
Jul
(3) |
Aug
|
Sep
|
Oct
(8) |
Nov
(26) |
Dec
(16) |
2008 |
Jan
(1) |
Feb
(4) |
Mar
(4) |
Apr
(25) |
May
(23) |
Jun
(22) |
Jul
(18) |
Aug
(61) |
Sep
(129) |
Oct
(106) |
Nov
(99) |
Dec
(24) |
2009 |
Jan
(6) |
Feb
(2) |
Mar
(29) |
Apr
(84) |
May
(106) |
Jun
(70) |
Jul
(56) |
Aug
(42) |
Sep
(62) |
Oct
(140) |
Nov
(38) |
Dec
(9) |
2010 |
Jan
(19) |
Feb
(15) |
Mar
(32) |
Apr
(36) |
May
(28) |
Jun
(17) |
Jul
(12) |
Aug
(13) |
Sep
(7) |
Oct
(9) |
Nov
(156) |
Dec
(56) |
2011 |
Jan
(53) |
Feb
(25) |
Mar
(6) |
Apr
|
May
(1) |
Jun
(22) |
Jul
(8) |
Aug
(20) |
Sep
(50) |
Oct
(60) |
Nov
(44) |
Dec
(3) |
2012 |
Jan
(2) |
Feb
(11) |
Mar
(32) |
Apr
(35) |
May
(13) |
Jun
(90) |
Jul
(15) |
Aug
(27) |
Sep
(15) |
Oct
(28) |
Nov
|
Dec
|
2013 |
Jan
|
Feb
(119) |
Mar
(91) |
Apr
(68) |
May
(29) |
Jun
(24) |
Jul
(4) |
Aug
(14) |
Sep
(3) |
Oct
(11) |
Nov
(31) |
Dec
(36) |
2014 |
Jan
(48) |
Feb
(1) |
Mar
(23) |
Apr
(14) |
May
(15) |
Jun
(4) |
Jul
(8) |
Aug
(18) |
Sep
|
Oct
(14) |
Nov
|
Dec
(5) |
2015 |
Jan
(2) |
Feb
|
Mar
(11) |
Apr
(3) |
May
(44) |
Jun
(14) |
Jul
(7) |
Aug
(2) |
Sep
(5) |
Oct
(23) |
Nov
(27) |
Dec
(7) |
2016 |
Jan
(15) |
Feb
(22) |
Mar
(23) |
Apr
(41) |
May
(25) |
Jun
(1) |
Jul
(27) |
Aug
(9) |
Sep
(5) |
Oct
|
Nov
(27) |
Dec
|
2017 |
Jan
|
Feb
|
Mar
(3) |
Apr
(2) |
May
(1) |
Jun
(18) |
Jul
(16) |
Aug
(11) |
Sep
|
Oct
(3) |
Nov
|
Dec
|
2018 |
Jan
(11) |
Feb
(2) |
Mar
(3) |
Apr
|
May
(13) |
Jun
(12) |
Jul
(16) |
Aug
|
Sep
|
Oct
(1) |
Nov
|
Dec
|
2019 |
Jan
|
Feb
(3) |
Mar
(21) |
Apr
(8) |
May
(12) |
Jun
|
Jul
|
Aug
(4) |
Sep
(4) |
Oct
(2) |
Nov
(5) |
Dec
(16) |
2020 |
Jan
|
Feb
|
Mar
(1) |
Apr
(2) |
May
(16) |
Jun
|
Jul
(10) |
Aug
(24) |
Sep
(31) |
Oct
(17) |
Nov
(4) |
Dec
|
2021 |
Jan
(3) |
Feb
|
Mar
|
Apr
(1) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
(4) |
Nov
(12) |
Dec
(10) |
2022 |
Jan
|
Feb
(3) |
Mar
(2) |
Apr
(15) |
May
(4) |
Jun
|
Jul
|
Aug
(15) |
Sep
|
Oct
|
Nov
|
Dec
|
2023 |
Jan
|
Feb
|
Mar
|
Apr
(3) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2024 |
Jan
|
Feb
|
Mar
(1) |
Apr
(6) |
May
(1) |
Jun
|
Jul
(1) |
Aug
(3) |
Sep
|
Oct
|
Nov
|
Dec
(1) |
2025 |
Jan
(1) |
Feb
|
Mar
(1) |
Apr
|
May
|
Jun
(1) |
Jul
(3) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
|
1
(4) |
2
(7) |
3
(9) |
4
(3) |
5
(3) |
6
(1) |
7
|
8
(2) |
9
(9) |
10
|
11
(7) |
12
(1) |
13
|
14
|
15
(1) |
16
|
17
|
18
(4) |
19
|
20
|
21
|
22
(8) |
23
(11) |
24
(18) |
25
(8) |
26
(9) |
27
|
28
(6) |
29
(5) |
30
(13) |
|
|
|
|
From: Tom R. <ro...@gm...> - 2008-09-30 23:46:39
|
CVS was offline for a few hours while sourceforge migrated the data (really, deltas from an earlier migration) from California to Chicago. Somehow in the process they broke the golly CVS, so right now neither updates nor checkouts (and presumably, commits) will not complete. I've filed a support request (well, piggybacked on someone else's similar complaint). -tom -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-30 16:06:28
|
Actually, I see no strong reason to remove the ruletables, at least not right away. We may want to do some tricky thing to set or modify the priority of the two for different rules or something (not sure how to do that yet) but clearly ruletables does "win" over ruletrees significantly for at least one rule, and I know there are rules for which ruletrees will simply fall apart (huge, random rules). But most importantly, I like the fact that it is possible people can author ruletables directly; they may prefer that over writing a programming language script. Not everyone is a programmer (even for short relatively simple functions.) >> even be easily authorable, and we can remove the rule tables. It is |
From: Tom R. <ro...@gm...> - 2008-09-30 16:03:08
|
Wow, so lifetable does a significantly better job at compressing Hutton32. That's interesting. Yeah, Rule-Tables is vestigal; everything is going into Rules (with the extensions .table and .tree). > I'll try to add some of the rule/pattern info tonight. Excellent! Tim, you've made a huge impact on Golly in a very short time; I for one am very happy to have you aboard! > The NDD stuff is excellent, Tom. With cross-language scripts it should > even be easily authorable, and we can remove the rule tables. It is > weird about the Hutton32 tree, especially since given the number of > table rules. Thanks! You inspired the idea; it's not that much different from ruletables. Should we consider making ruletables faster? What I was thinking is building (at load time) an array of arrays: int matches[ceil(rules/32)][num_states][neighbors+1] and matches[i][j][k] has bit m set if and only if the state value j in neighbor k is a matching state value for rule number 32*i+m. This way, we can "evaluate" the rules by just: for (int i=0; i<ceil(rules/32); i++) { int check32 = matches[i][nw][0] & matches[i][n][1] ... ; if (check32) { find least significant set bit; that's the matching rule; look up its value } } Does this make any sense? You may even share common last rows (through the variable definitions) to make the table smaller (in which case you may want to use the ordering matches[ceil(rules/32)][neighbors+1][num_states]). This is just a thought, and it would complicate the code a bit more, but not too much, and I think it will make the rule table a fair bit faster. Using 64-bit long longs may be faster yet. |
From: Tom R. <ro...@gm...> - 2008-09-30 15:54:25
|
>> Well, local-win.mk, local-gtk.mk, etc., since there are syntax diffs so I >> can't share a common local.mk file. >> I'm going to do it only to -win for the very moment and I'll get around to >> the others shortly. > I'm not exactly sure how this improves the situation. I'm clearly going > to have to modify local-win.mk to build Golly on my Win system. If I do > that, and then do a cvs commit, then when one of you guys does a cvs update > your modified local-win.mk file will get clobbered by my changes. > How do we avoid that happening? That's a good point; I was still in p4-think mode (perforce allows you to maintain modified versions of repository files transparently to the repository itself; I forgot CVS just finds all changed files and sends them at a go.) Clearly we want a short file that is under the builder control but not under CVS control; yet we want a template/example such file in CVS. Further we want the makefile to not only include it, but if it's not there, tell the user what to do. So how about we include local-win.template but not local-win.mk and the makefile tries to make local-win.mk first thing, and if it doesn't exist it echos "please copy local-win.template to local-win.mk and edit it for the paths relevant on your system"? I think for makefile-gtk and makefile-win, there are no paths that need to be set (at least, the default makefiles appear to work fine for me.) So this is only an issue on Windows and the Mac, probably. BTW I may try to merge more commonality from the makefiles; I really really hate that I have to edit *four* makefiles to add or remove a single source file. > PS. I think the !include line in local-win.mk needs an explicit C drive: > > !include <C:/wxWidgets-2.8.7-32/build/msw/config.vc> > > This allows people to build Golly on a different drive. > > Andrew > > ------------------------------------------------------------------------- > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-30 15:49:30
|
This sounds great to me! On Tue, Sep 30, 2008 at 5:48 AM, Andrew Trevorrow <an...@tr...> wrote: >> We need to get "info" descriptions for some of the patterns in Loops. > > And don't forget Help/Algorithms will need RuleTable.html and RuleTree.html. > > On this topic, I've thought of an idea that should be quite useful. > For the html files inside Help/Algorithms, we can easily turn all > the example rules into special links so that clicking on a rule > automatically puts it into the new rule box. For example, RuleTable.html > and RuleTree.html could refer to WireWorld like so: > > <a href="rule#WireWorld">WireWorld</a> > > How does that sound? (I've already done this sort of thing for links > that open the prefs dialog and load lexicon patterns, so it would be > trivial to implement.) > > Andrew > > ------------------------------------------------------------------------- > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > -- Check out Golly at http://golly.sf.net/ |
From: Andrew T. <an...@tr...> - 2008-09-30 12:48:28
|
> We need to get "info" descriptions for some of the patterns in Loops. And don't forget Help/Algorithms will need RuleTable.html and RuleTree.html. On this topic, I've thought of an idea that should be quite useful. For the html files inside Help/Algorithms, we can easily turn all the example rules into special links so that clicking on a rule automatically puts it into the new rule box. For example, RuleTable.html and RuleTree.html could refer to WireWorld like so: <a href="rule#WireWorld">WireWorld</a> How does that sound? (I've already done this sort of thing for links that open the prefs dialog and load lexicon patterns, so it would be trivial to implement.) Andrew |
From: Andrew T. <an...@tr...> - 2008-09-30 12:30:59
|
> Well, local-win.mk, local-gtk.mk, etc., since there are syntax diffs so I > can't share a common local.mk file. > > I'm going to do it only to -win for the very moment and I'll get around to > the others shortly. I'm not exactly sure how this improves the situation. I'm clearly going to have to modify local-win.mk to build Golly on my Win system. If I do that, and then do a cvs commit, then when one of you guys does a cvs update your modified local-win.mk file will get clobbered by my changes. How do we avoid that happening? PS. I think the !include line in local-win.mk needs an explicit C drive: !include <C:/wxWidgets-2.8.7-32/build/msw/config.vc> This allows people to build Golly on a different drive. Andrew |
From: Andrew T. <an...@tr...> - 2008-09-30 12:15:03
|
You can now override an algo's default icons by using a new "Load Icons" button in Prefs > Color. This seemed the best place to do it given that colors and icons are closely linked. Clicking the button opens a dialog box that displays all the current 15x15 and 7x7 icons and lets you load a new set of icons from a suitable file. Rather than use XPM files for storing icons, I decided to let people use more common formats: BMP/GIF/PNG/TIFF. This also makes it easier to store both 15x15 and 7x7 icons in the one file. At the top of the dialog are some notes and a picture showing how the icon bitmaps must be arranged within the file (hopefully very simple and obvious). The dialog also has a button for restoring the algo's default icons. I've added a simple test file in the bitmaps subdir called icon_dot.bmp that can be used to exercise the new dialog. Let me know if there are any problems. I've decided not to implement a seticons() scripting command. I don't see much need for scripts to be changing icons. I can always add it later if people think it would be useful. PS. The default icon used for algos that don't supply any built-in icons is now a diamond -- looks nicer than a dot. Andrew |
From: Tim H. <tim...@gm...> - 2008-09-30 08:12:06
|
I've added the missing Nobili32 and Hutton32 rule tables, at 202 and 379 rules respectively. (They are currently in Rule-Tables but I think that folder is going soon?) I think we can remove jvnalgo. I'll try to add some of the rule/pattern info tonight. The NDD stuff is excellent, Tom. With cross-language scripts it should even be easily authorable, and we can remove the rule tables. It is weird about the Hutton32 tree, especially since given the number of table rules. On Sun, Sep 28, 2008 at 6:04 PM, Tom Rokicki <ro...@gm...> wrote: > I think we should do the following things for the release, with respect to the > algorithms: > > 1. Integrate nddalgo (and of course keep ruletable_algo). > > 2. Change the .txt extensions for ruletables to .trans. > > 3. Change the rule format for nddalgo and ruletables to just > be the rule itself (WireWorld, for instance) rather than > requiring ndd: or ruletable:. > > 4. Eliminate WireWorld and SlowLife as separate algorithms > (WireWorld is easily done with either ndd or ruletables.) > > 5. Do *not* modify bgolly to generate .ndds from the built-ins > (we don't need that anymore). > > 6. Write the ndd generators for Java, Python, and Perl; > collect them and the c++ generator with docs in some > directory somewhere. > > 7. Decide for each ruletable/ndd algorithm whether we want > to distribute a .trans or .ndd (the .trans is more readable, > but the .ndd executes somewhat faster). > > 8. Decide if we want to pick up .color and/or .icon files > for the file-based algorithms (I think this would be a > relatively easy thing to do, and allow people to easily > configure an algorithm-based default color/icon set). > > Note that we need to keep Generations (because it uses > parameterized rules) and JvN (because Hutton32 doesn't > generate a reasonably compact .ndd file). > > What do you guys think? > > BTW I've modified the .ndd stuff to be a bit more efficient > (it uses state* instead of int* for the lowest level, so if no > compression for a particular rule is possible, at worst it > requires space the size of the transition table). > > The notion of a "default rule" falls apart somewhat for NDD > and ruletable, but that's okay. > > -- > Check out Golly at http://golly.sf.net/ > > ------------------------------------------------------------------------- > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > -- Tim Hutton - http://www.sq3.org.uk Take the Organic Builder challenge - http://www.sq3.org.uk/Evolution/Squirm3/OrganicBuilder/ |
From: Tom R. <ro...@gm...> - 2008-09-30 05:00:05
|
We need to get "info" descriptions for some of the patterns in Loops. -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-30 04:58:40
|
Ran out of steam tonight, did not get it all done. But I got a lot of it done. Golly should now have ruletreealgo in there, and not slife or wireworld. I've updated ruletree and ruletable both to use the short names of rules and build filenames in the Rules dir. I've added a "local override" local-win.mk to makefile-win (but not to the other makefiles). I've updated the patterns that use rule_table to specify their rule in the new fashion. And a bunch of other changes. These are the things remaining on my plate for this particular portion: * Update makefiles to build dists with Rules, not Rule-Tables * Add "local-x.mk" to makefiles other than -win * Update patterns that mention rule_table: syntax * Eliminate WireWorld, SlowLife, Rule-Tables from cvs * Add default rule to ruletreealgo, ruletablealgo * Add RuleTree.cpp, .h, GenRuleTree.cpp (with docs) * Write RuleTree/GenRuleTree in Java, Perl, other languages * Add RuleTree documentation -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-30 02:34:08
|
Well, local-win.mk, local-gtk.mk, etc., since there are syntax diffs so I can't share a common local.mk file. I'm going to do it only to -win for the very moment and I'll get around to the others shortly. On Mon, Sep 29, 2008 at 7:26 PM, Tom Rokicki <ro...@gm...> wrote: > I'm going to do the following, unless I get a veto. > > I'm going to add a > > include local.mk > > to Makefile-gtk, a > > !include local.mk > > to Makefile-win, and whatever syntax OS-X wants for > include files to Makefile-mac. > > I will also add an empty local.mk to the source. > > The idea is you override makefile variables *here*; > this will make it much easier to build, since you > don't modify the master makefile, just the environment > overrides in that included file. > > What do you guys think? > > -tom > > -- > Check out Golly at http://golly.sf.net/ > -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-30 02:26:41
|
I'm going to do the following, unless I get a veto. I'm going to add a include local.mk to Makefile-gtk, a !include local.mk to Makefile-win, and whatever syntax OS-X wants for include files to Makefile-mac. I will also add an empty local.mk to the source. The idea is you override makefile variables *here*; this will make it much easier to build, since you don't modify the master makefile, just the environment overrides in that included file. What do you guys think? -tom -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-29 02:10:54
|
> Not at all. I'll try to make all these changes, and check in RuleTree, > tonight. RuleTable and RuleTree sound good to me. It may wait until tomorrow night; I forgot I have some more stuff to do tonight. :-) But I'll start things tonight. |
From: Tom R. <ro...@gm...> - 2008-09-29 02:05:58
|
> How attached are you to "NDD" for the algo name? How about something > more mnemonic like "RuleTree"? Then we'd have 2 algos called RuleTable > and RuleTree and their corresponding extensions could be .table and .tree. Not at all. I'll try to make all these changes, and check in RuleTree, tonight. RuleTable and RuleTree sound good to me. > We also need to rename the Rule-Tables folder to Rules, given that it > contains files used by both algos. Yep. >> 3. Change the rule format for nddalgo and ruletables to just >> be the rule itself (WireWorld, for instance) rather than >> requiring ndd: or ruletable:. > Yep, good idea. I'm also going to make sure that the rule string does not contain '/' or '\' or ':', and if it does, do an immediate fail. I don't want someone opening ../../../../../etc/passwd (or ../../../../proc/someproc/fd/...) and doing something nefarious. > I guess the natural place is somewhere inside the Rules dir, perhaps > in a subdir called "NDD" or "Tree-Generators"? Nice. > We can have both can't we, at least for the beta release? Yes, absolutely. Of course RuleTable comes before RuleTree alphabetically, so that's the one that will be picked by default. But that's fine while we are testing things out. >> The notion of a "default rule" falls apart somewhat for NDD >> and ruletable, but that's okay. > > I'd like to make a suggestion about that. Could both those algos > use a built-in table/tree for the default rule (presumably a very > simple rule, like "Life") that *doesn't* require loading any file? > Golly's GUI code assumes that switching to the default rule can > never fail, so at the moment if a user does something silly like > rename/remove the Rules folder then all hell breaks loose. Sure; I'll do that. I'll have to generalize the "get-next-line" routine but that's easy enough. And I agree that standard Life should be the built-in default rule. > Not only did Golly crash when I was testing this, it actually > crashed my Mac (something I've never seen before!). That is *super* worrisome. I have no idea how that could happen! Wow. Another note: there is a slight concern if the user is developing SuperAutomata.table or SuperAutomata.tree. Right now RuleTree (ndd) checks and if the user attempts to set the same rule, it just ignores it. But it *really* should check if the file has changed on disk since the last time that file was loaded. Is this worth adding? Or should I make it always reload on every change, even if the change is to the same rule? I guess the latter is best, but if people ever put in random rules that take multiple seconds to load (which could well happen if they have a multi-megabyte ruletree), this could get annoyng. I think for now I'll take out the check-and-don't-reload and see how it goes. -tom |
From: Andrew T. <an...@tr...> - 2008-09-29 01:18:13
|
> I think we should do the following things for the release, with respect to the > algorithms: > > 1. Integrate nddalgo (and of course keep ruletable_algo). Yep, I'd like to have both available so we can easily compare their performance, at least for the beta release. It may become clear that one algo has significant advantages over the other (in which case we drop the other algo from the final release), or both algos might have particular strengths in different areas (in which case we keep both). > 2. Change the .txt extensions for ruletables to .trans. How attached are you to "NDD" for the algo name? How about something more mnemonic like "RuleTree"? Then we'd have 2 algos called RuleTable and RuleTree and their corresponding extensions could be .table and .tree. We also need to rename the Rule-Tables folder to Rules, given that it contains files used by both algos. > 3. Change the rule format for nddalgo and ruletables to just > be the rule itself (WireWorld, for instance) rather than > requiring ndd: or ruletable:. Yep, good idea. > 4. Eliminate WireWorld and SlowLife as separate algorithms > (WireWorld is easily done with either ndd or ruletables.) Good idea. > 5. Do *not* modify bgolly to generate .ndds from the built-ins > (we don't need that anymore). Fine by me. > 6. Write the ndd generators for Java, Python, and Perl; > collect them and the c++ generator with docs in some > directory somewhere. I guess the natural place is somewhere inside the Rules dir, perhaps in a subdir called "NDD" or "Tree-Generators"? > 7. Decide for each ruletable/ndd algorithm whether we want > to distribute a .trans or .ndd (the .trans is more readable, > but the .ndd executes somewhat faster). We can have both can't we, at least for the beta release? If RuleTable is the current algo and the user (or rle/mc file) requests "WireWorld" then WireWorld.table will be loaded. If RuleTree/NDD is the current algo then WireWorld.tree/ndd will be loaded. (If neither algo is current then Golly will switch to the one that appears earlier in the algo menu.) > 8. Decide if we want to pick up .color and/or .icon files > for the file-based algorithms (I think this would be a > relatively easy thing to do, and allow people to easily > configure an algorithm-based default color/icon set). We already have algo-based default colors/icons. What you want is rule-based default colors/icons. I agree that this is desirable but it might be trickier than it seems -- I'll have to think about it a bit more. I'm happy to give it a go if you're happy to wait a little bit longer for the beta release. > Note that we need to keep Generations (because it uses > parameterized rules) and JvN (because Hutton32 doesn't > generate a reasonably compact .ndd file). Yep, I'm happy with that. > The notion of a "default rule" falls apart somewhat for NDD > and ruletable, but that's okay. I'd like to make a suggestion about that. Could both those algos use a built-in table/tree for the default rule (presumably a very simple rule, like "Life") that *doesn't* require loading any file? Golly's GUI code assumes that switching to the default rule can never fail, so at the moment if a user does something silly like rename/remove the Rules folder then all hell breaks loose. Not only did Golly crash when I was testing this, it actually crashed my Mac (something I've never seen before!). Andrew |
From: Tom R. <ro...@gm...> - 2008-09-29 01:17:35
|
> Tim committed a Loops subdir in Patterns with a number of examples, > including Evoloop.rle. How did I miss that? Very nice! (But very slow. Hashlife just does not do well with this pattern, for some reason.) I tried the Evoloop.rle pattern with both the rule_table and the ndd algorithms. Clearly, rule_table can be made much faster, and I don't intend this to be any sort of competition, but I timed things. To go to generation 32,768 stepping by 1,024 with 256MB of hash memory took: RuleTable: 5m58s NDD: 2m11s Upping the memory to 2GB but all the same parameters otherwise gave: RuleTable: 3m21s NDD: 1m44s So it turns out slowcalc *does* matter for those patterns where hashlife can't gain traction. (And indeed, hashlife abuses slowcalc a fair bit, due to the nature of its recursion; it calculates overlapping squares, so each cell-generation may be computed more than once.) Of course this is hardly a fair fight; ndd is *intentionally* made to make slowcalc as simple and fast as possible, and ruletable is meant to be much more user accessible, and certainly performance improvements are possible in its implementation. Nonetheless, right now with hashlife, and I think even more later when we get the other meta-algorithms in, NDD will be quite faster. BTW, evoloop is quite cool to watch! Try it with NDD at a step of 8. Andrew, I've been messing with your color controls; I like them a lot! I think I'm going to go ahead and check in the .ndd stuff, everything except the bgolly-generation-of-ndd files (which we really don't need) and the Hutton-32 .ndd (which is best done with the native JvN anyway). This way people can play with it more easily. |
From: Andrew T. <an...@tr...> - 2008-09-29 00:18:59
|
> I have implemented and tested n-ary decision diagrams for specifying > arbitrary Golly rules, and I think this idea has significant > potential. For most rules (fewer than 10 states in 8-neighborhood > automata, and fewer than 100 states in 4-neighborhood automata), we > can automatically transform a user-written function (in virtually any > language) into a simple data file that Golly can quickly load and > quickly execute. Great work Tom -- this sounds very promising. I haven't had time to actually try it out yet (you caught me at a bad moment -- I'm in the middle of making changes to allow users to load icon files), but it's good to hear that .ndd files are fast to load. One (minor) problem with the RuleTable algo is that there is a small but annoying pause whenever setrule is called. Andrew |
From: Andrew T. <an...@tr...> - 2008-09-28 23:48:45
|
> (I need to find an Evoloop pattern somewhere . . .) Tim committed a Loops subdir in Patterns with a number of examples, including Evoloop.rle. Andrew |
From: Tom R. <ro...@gm...> - 2008-09-28 22:38:21
|
Dave, Looking more closely at your diagram, I have to mention that for the level 1 nodes, the values in the line are *states*, not pointers to other nodes. That's why your diagram has edges that appear to jump levels. All the level 1 nodes have no node children, just state children. I thought of eliminating this by starting the node numbering at numstates but I didn't like that much better so I stuck with 0-based numbering for the nodes. (By comparison, the mc format uses 1-based numbering for the nodes, and all empty trees are always represented by 0 no matter what level they are at.) -tom |
From: Tom R. <ro...@gm...> - 2008-09-28 22:23:50
|
Howdy Dave! Glad to hear from you; I've been hoping for some feedback. > http://cranemtn.com/life/files/B3S23Life-NDD-tree.png Very pretty diagram, and it does illustrate the idea very well. > Just for the record, here are the extra little details I had to > explain to myself about the .ndd format: Next time I'll try to give some more of these details. I'll add some of them to the README for now. > -- Actually I'm not quite sure what good this first number is, > exactly; I didn't seem to need it to trace the logic through Life.ndd, It's definitely redundant and not at all necessary, but it does provide a small amount of error checking, and makes it somewhat easier to read the file, although it's a minor thing. When reading the file I actually treat the states (at level 1) differently than the downpointers (at level 2+) and this number clues me in. It's also almost identical to the .mc format, by the way. >> I am not sure what is happening in the Hutton-32 rule. > My vague summary would be that those modifications to the rule table > that made the constructor arm simpler and more efficient must also > prevent a lot of parallel chains of nodes from collapsing into one > chain. Kind of the same thing that would make the .ndd file for > B37/S23 bigger (I think) than for plain old B3/S23. I think you're right, but that's a pretty big jump in size. > It does seem as if there ought to be something simpler than that > 32-node tree for B3/S23, though. Most of the complexity in the > decision diagram has to do with sneakily at the last minute getting to > the same node for OFF-due-to-overpopulation as for > OFF-due-to-loneliness and OFF-due-to-center-state. Yep. > ... So would it work at all to have a separate lookup table at the > outermost level of recursion, to assign a new state based on the > current node and the center state instead of having to use the same > function all the way through? For the B3/S23 case, I think this would > allow the 32 nodes to be cut down to 5: > > return (state)lookup[a[a[a[a[a[a[a[a[base+nw]+ne]+sw]+se]+n]+w]+e]+s]+c] ; > > state4 4 3 0 0 > state3 3 2 0 0 > state2 2 1 0 1 > state1 1 0 1 1 > state0 0 0 0 0 This works, but perhaps more for count-based rules In general, "ndd" and "bdd" and even the canonicalized quadtrees themselves are just a single simple compression scheme; other compression schemes can give greater compression either by being more complex or by reflecting particular domains better. The neat thing about ndd is it is so fast to calculate; you don't need to do any "thinking"; just create each node and see if an identical one has been seen before. I would not be against using something more complex, but I really like the simplicity and transparency of the .ndd format, and I like the fact that we can generate them easily. There's a lot more I haven't mentioned about the ndd's. Just like bdds themselves, you can perform logical, arithmetic, and other operations directly on the tree itself. For instance, it is not hard at all to automatically go from Tim's transition format directly to a ndd *without* enumerating the state space; each additional transition rule is just another operation on the ndd itself. This is similar to how bdds can be used directly to do boolean function operations on relatively complex circuitry without ever getting too large. > I'll bet Hutton32 could be condensed quite a bit with this > method, possibly making a separate JvN algorithm unnecessary. I'd be willing to take that bet; I think you might be able to get 2x or maybe 3x, but not too much more. If you look at the Hutton32 ndd, almost all the nodes are at the bottom (level 1). I don't see how your mechanism helps to reduce the count of level 1 nodes, since each unique level 1 node corresponds to at least one node in your system. > Should I try to tackle that interesting question -- or would I have to > write an automatic translator into this format first to prove that the > idea was any good? Or will lookups in two small arrays be much less > efficient for some reason than the current one bigger array, anyway? I think the major win here is actually just automatic generation of ndd files from user-written functions rather than the details of the ndd format itself; it could be considered a blob of binary data (or a precompiled dll if you prefer) rather than anything of value to anything but Golly. I envision a window where you code the user function in Python or Perl and hit a button and then you can single step with that function---and edit and iterate. I think for most rules that Golly could potentially support, the ndd format gives us essentially a compiler into an intermediate form that Golly can quickly execute. *That's* what I'm excited about; the ability for people to put their own rules (historical life, colored life, dead boundaries around rectangles to give finite fields, new 2d multistate rules, hex multistate rules, and on and on) without needing to download wxWidgets, Python, Perl, the MS 2008 SDK, and so on and so forth. *That's* what I like about ndd. Thanks Dave for thinking about this and clarifying it so well! (I need to find an Evoloop pattern somewhere . . .) -tom |
From: Dave G. <dav...@gm...> - 2008-09-28 22:01:23
|
> I have implemented and tested n-ary decision diagrams for specifying > arbitrary Golly rules, and I think this idea has significant > potential. > ... > The basic concept is simple---it is canonicalized (or hash-consed) > trees, much like what hashlife itself uses. But instead of quadtrees > representing 2D areas of space, the nodes are n-ary tree nodes > representing the transition function of the automata. Very interesting -- it certainly does look very simple... from the computer's point of view if not the user's. > To be fair, ndd is not as user-friendly as transition tables (in the > sense that people can author transition tables directly, but they are > unlikely to be able to author .ndd files directly). Yup, or at least they're unlikely to want to! I took a look at the Life.ndd file, and my first reaction was "...Huh?" -- But once I got the idea of starting from the last node in the list and feeding in one neighbor-state at a time, it started looking like a nice simple decision diagram (binary in this case) after all: http://cranemtn.com/life/files/B3S23Life-NDD-tree.png The diagram is kind of rough, but anyone interested should get a fair idea of how the .ndd file works: start from the top of the diagram and work down, and the number of the node you end up in after 9 steps is also the output state. (Tom, please chime in anywhere here if I've gotten something wrong.) Just for the record, here are the extra little details I had to explain to myself about the .ndd format: 1) Below the header section ending "numnodes = N" is a zero-based list of nodes, one node per line. The nodes aren't explicitly numbered in the file, they're just listed in order starting with #0. 2) "base" in the slowcalc() formula just means the last node -- so if the NW neighbor state is 0, you'll jump to the first child node (26, or generally the second number on the last line of the .ndd file). If it's 1, you go to the second child node (30, or third number), etc. 3) The *first* number for each node represents a "level", meaning (I think, more or less) that you'll get to the node at that level of recursion in the formula. For example, "a[base+nw]" in slowcalc() is at the innermost (ninth) level of recursion. That last level-9 node points to the two level-8 nodes, 26 and 30, which collectively point to three level-7 nodes, and so on until things got a little confusing down at the bottom. -- Actually I'm not quite sure what good this first number is, exactly; I didn't seem to need it to trace the logic through Life.ndd, though it was convenient for drawing the diagram. What am I missing there? If it's just a convenient label for the node, I think the actual node number would be even more convenient, in terms of human readability. > I am not sure what is happening in the Hutton-32 rule. My vague summary would be that those modifications to the rule table that made the constructor arm simpler and more efficient must also prevent a lot of parallel chains of nodes from collapsing into one chain. Kind of the same thing that would make the .ndd file for B37/S23 bigger (I think) than for plain old B3/S23. In regular Life, you can head straight for the 0 state once you've seen 4 ON neighbors, but in B37/S23 you can't start narrowing the tree back down until you get to the last couple of neighbors -- e.g., in the diagram link above, there would have to be two nodes below node 27, not just one, and the same for the next two levels (have to count to 7 instead of just to 4). -------------------------- It does seem as if there ought to be something simpler than that 32-node tree for B3/S23, though. Most of the complexity in the decision diagram has to do with sneakily at the last minute getting to the same node for OFF-due-to-overpopulation as for OFF-due-to-loneliness and OFF-due-to-center-state. ... So would it work at all to have a separate lookup table at the outermost level of recursion, to assign a new state based on the current node and the center state instead of having to use the same function all the way through? For the B3/S23 case, I think this would allow the 32 nodes to be cut down to 5: return (state)lookup[a[a[a[a[a[a[a[a[base+nw]+ne]+sw]+se]+n]+w]+e]+s]+c] ; state4 4 3 0 0 state3 3 2 0 0 state2 2 1 0 1 state1 1 0 1 1 state0 0 0 0 0 You can kind of see the B3 and S23 in the penultimate and final columns, respectively -- the part after the wide space is the final "lookup" table, for center-OFF and center-ON respectively. But obviously even if I've gotten the above network right, that doesn't mean there's an easy way of building this minimal trie _automatically_ from a user-written function. Haven't looked into this part at all yet. The only possible reason to wrestle with this is that I'll bet Hutton32 could be condensed quite a bit with this method, possibly making a separate JvN algorithm unnecessary. Should I try to tackle that interesting question -- or would I have to write an automatic translator into this format first to prove that the idea was any good? Or will lookups in two small arrays be much less efficient for some reason than the current one bigger array, anyway? Keep the cheer, Dave |
From: Tom R. <ro...@gm...> - 2008-09-28 17:05:02
|
I think we should do the following things for the release, with respect to the algorithms: 1. Integrate nddalgo (and of course keep ruletable_algo). 2. Change the .txt extensions for ruletables to .trans. 3. Change the rule format for nddalgo and ruletables to just be the rule itself (WireWorld, for instance) rather than requiring ndd: or ruletable:. 4. Eliminate WireWorld and SlowLife as separate algorithms (WireWorld is easily done with either ndd or ruletables.) 5. Do *not* modify bgolly to generate .ndds from the built-ins (we don't need that anymore). 6. Write the ndd generators for Java, Python, and Perl; collect them and the c++ generator with docs in some directory somewhere. 7. Decide for each ruletable/ndd algorithm whether we want to distribute a .trans or .ndd (the .trans is more readable, but the .ndd executes somewhat faster). 8. Decide if we want to pick up .color and/or .icon files for the file-based algorithms (I think this would be a relatively easy thing to do, and allow people to easily configure an algorithm-based default color/icon set). Note that we need to keep Generations (because it uses parameterized rules) and JvN (because Hutton32 doesn't generate a reasonably compact .ndd file). What do you guys think? BTW I've modified the .ndd stuff to be a bit more efficient (it uses state* instead of int* for the lowest level, so if no compression for a particular rule is possible, at worst it requires space the size of the transition table). The notion of a "default rule" falls apart somewhat for NDD and ruletable, but that's okay. -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-28 04:10:46
|
N-ary Decision Diagrams for Golly I have implemented and tested n-ary decision diagrams for specifying arbitrary Golly rules, and I think this idea has significant potential. For most rules (fewer than 10 states in 8-neighborhood automata, and fewer than 100 states in 4-neighborhood automata), we can automatically transform a user-written function (in virtually any language) into a simple data file that Golly and quickly load and quickly execute. The basic concept is simple---it is canonicalized (or hash-consed) trees, much like what hashlife itself uses. But instead of quadtrees representing 2D areas of space, the nodes are n-ary tree nodes representing the transition function of the automata. This is like binary decision diagrams, only each node has n successors instead of 2, where n is the number of states in the automata. In the file http://tomas.rokicki.com/ndd.zip I have collected the source files I have constructed so far; I am not quite ready to check them into the cvs repository because I'd like to get some feedback first. (Source control branches would help here.) The files are: ndd.{h,cpp}: The basic data structure and two routines; one takes a user-written function and converts it into an internal ndd, and the other writes out that ndd in a format suitable to be read by Golly. lifemin.cpp: Sample file demonstrating how to use the above routines to convert a user-written function to an .ndd file. nddalgo.{h,cpp}: The glue logic for reading and evaluating these files in Golly. The rule format is just ndd:Life and this says to read the file Rule-Tables/Life.ndd. bgolly.cpp: Modified bgolly to use nddalgo, and also to automatically generate .ndd files for any other algorithm and rule that Golly already knows about. gen.bat: File showing how to use the modified bgolly to generate .ndd files. wxalgos.cpp: Modified algorithm file that knows aboug golly. makefile: My personal makefile for building the modified golly. Rule-Tables/*.ndd: ndd files for all the standard Golly algorithms (including the transition table ones). To be fair, ndd is not as user-friendly as transition tables (in the sense that people can author transition tables directly, but they are unlikely to be able to author .ndd files directly). In addition, going from a function to a .ndd for rules with more than 10 states (in eight-neighbor rules) and 100 states (in four-neighbor rules) is extremely difficult to do by simple evaluation of the user function. (Although it is possible to automatically convert transition tables to .ndd files *without* enumerating all states, but that's another topic.) The evaluation function is particularly simple; the nddalgo.cpp class has an integer array (int *a) and a integer base; the actual evaluation function is precisely state nddalgo::slowcalc(state nw, state n, state ne, state w, state c, state e, state sw, state s, state se) { if (num_neighbors == 4) return (state)a[a[a[a[a[base+n]+w]+e]+s]+c] ; else return (state)a[a[a[a[a[a[a[a[a[base+nw]+ne]+sw]+se]+n]+w]+e]+s]+c] ; } This is all straight-line code; the only branch is on the number of neighbors and that's handled by the branch prediction mechanism of modern CPUs. Other than that, it's just additions and array references, and the array tends to be quite small. This means that evaluation will be quick; this is important both for chaotic patterns, and for our later implementation of other meta-algorithms that don't depend on (or suffer from) hashlife. How small? Here are some statistics on the algorithms I've examined: Rule States Neighbors Nodes BriansBrain 3 8 27 Byl-Loop 6 4 152 Caterpillars 4 8 38 Chou-Reggia-1 8 4 195 Chou-Reggia-2 8 4 101 Evoloop 9 4 377 Hutton32 32 4 7075 JvN29 29 4 67 Langtons-Loops 8 4 222 Life 2 8 32 Nobili32 32 4 118 SDSR-Loop 9 4 339 StarWars 4 8 36 WireWorld 4 8 28 With the exception of Hutton32, all the rules have very compact representations; the full set of nodes easily fit in the processor cache. The basic John von Neumann 29-state rule requires only 67 nodes to represent. I am not sure what is happening in the Hutton-32 rule. The code is quite small; ndd.c (which computes the trees by iterating a user-written function) is only 46 lines long; nddalgo.cpp is only 166 lines long. Indeed, ndd.c is so short and simple it can easily be coded in Java, C++, Perl, Python, Ruby, Haskell, OCaml, and whatever other languages people might use, so that transition functions written in any of these languages can easily be turned into ndd files. -- Check out Golly at http://golly.sf.net/ |
From: Tom R. <ro...@gm...> - 2008-09-26 23:14:58
|
It's really frustrating, that is. I encounter that myself. I think we should spend a few minutes and see if there isn't a solution. Ideally one that integrates the bulk of the makefile into a common, shared, platform- and system-independent file that is included by the three main regular makefiles. I believe all the makes we use support includes. Maybe I'll spend a few minutes on this over the weekend. On Fri, Sep 26, 2008 at 4:12 PM, William R. Buckley <bil...@gm...> wrote: > Thanks for help with my compilation problems. > The error was indeed the use of an improperly > maintained make file. > > wrb > >> -----Original Message----- >> From: Dave Greene [mailto:dav...@gm...] >> Sent: Friday, September 26, 2008 12:38 AM >> To: golly test list >> Subject: Re: [Golly-test] Fixed compile problem >> >> On Fri, Sep 26, 2008 at 3:10 AM, Tom Rokicki wrote: >> > Works for me on linux and windows. >> >> Same here, for my Windows box; yesterday's mysterious compile >> problems have disappeared. >> >> Old object files are evil -- how come nmake doesn't notice a >> newer date stamp on the relevant source file and recompile >> automatically? >> That would seem to be the civilized thing to do. >> >> I've put up a new Windows executable at >> >> http://cranemtn.com/life/files/Golly.exe >> >> with folders and source files at >> >> http://cranemtn.com/life/files/golly-2.0b-current.zip >> >> as per sensible suggestion from Tom. The .7z version was >> smaller by 25%, which seemed like an impressive improvement, >> but of course it's pretty pointless to worry about a few >> hundred K in these decadent days >> -- >> >> Keep the cheer, >> >> >> Dave >> >> -------------------------------------------------------------- >> ----------- >> This SF.Net email is sponsored by the Moblin Your Move >> Developer's challenge Build the coolest Linux based >> applications with Moblin SDK & win great prizes Grand prize >> is a trip for two to an Open Source event anywhere in the >> world http://moblin-contest.org/redirect.php?banner_id=100&url=/ >> _______________________________________________ >> Golly-test mailing list >> Gol...@li... >> https://lists.sourceforge.net/lists/listinfo/golly-test >> > > > ------------------------------------------------------------------------- > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > -- Check out Golly at http://golly.sf.net/ |