Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

关于改进算法 #34

Open
HuntingBot opened this issue Feb 4, 2021 · 5 comments
Open

关于改进算法 #34

HuntingBot opened this issue Feb 4, 2021 · 5 comments
Labels
enhancement New feature or request

Comments

@HuntingBot
Copy link

第一,应该有一个选项,对于 gutter-symmetric 的规则(也就是没有 B2i,B4i,B4c,B6i),打开之后,搜到某一行(按行搜时)或某一列(按列搜时)在所有代都为死时停止搜索(因为可以用它自己稳定那一行)。除了震荡子,搜索方向与移动方向相互正交的飞船也可以用这个选项(这样搜 Spider 之类的就很容易)
第二,应该有另一个选项,对于 Choice of state for unknown cells 为 Dead 的搜索,结果的 hash 会被记录在一个表里(不包括离最近的活细胞距离超过2的部分),然后(在搜索过程中)剪掉所有符合表中任意一条记录的分支。不只要用 hash,可能还要用到别的高科技(因为要检测是否“符合表中任意一条记录”)
第三,应该还有一个选项(好吧,这个算是 Feature request),要求第一个 strictly-volatile 或者不对称等等的行/列/行加列出现在前 N 行,如果当前假定的前 N 行/列/行加列都没有 strictly-volatile 或者不对称等等的行/列/行加列,则放弃。

第四,我以前用的那些 save 现在都会提示 Broken saved file.

@AlephAlpha AlephAlpha added the enhancement New feature or request label Feb 4, 2021
@AlephAlpha
Copy link
Owner

前一段时间更新比较多,基本每一次更新都会导致 save file 不兼容……

春节期间可能还有一系列导致 save file 不兼容的更新……

这里的几个改进都涉及到行/列的概念,但 rlifesrc 本身其实是没有行/列的概念的,只有第一行/第一列的概念……涉及到的改动会比较大。如果要实现的话可能要等到比较久之后了(比如说明年春节?)。

@AlephAlpha
Copy link
Owner

AlephAlpha commented Feb 5, 2021

更新后不兼容的问题有一个简单的解决办法:

  1. 忽略掉意义不明的 field(比如更新后不再需要的 field);
  2. 该有而没有的 field (比如更新后新增的 field)直接用默认值。

这周六应该就能实现。 已实现,不知有没有 Bug。Gitee 镜像没法实时更新(滞后之大我怀疑它会人工审核)。

@HuntingBot
Copy link
Author

@AlephAlpha 这个回跳是什么玩意?

@AlephAlpha
Copy link
Owner

@AlephAlpha 这个回跳是什么玩意?

从冲突驱动子句学习算法(CDCL)里学来的;就是我们一起翻译的 https://github.com/HuntingBot/Celluar-Automata/issues/100 这个。

CDCL 主要就是两部分:冲突来源的子句学习(clause learning from conflicts),和非时间顺序回溯(non-chronological backtracking)。后一部分就是回跳。不过我只实现了回跳,没实现学习(确切地说,是学了就忘,只把学到的子句用于一次回跳,不作记录),效果很差……不知道实现了学习会怎么样,不过那部分的实现很复杂,而且 Logic Life Search 在很多情况下也没有 rlifesrc 快。

@AlephAlpha
Copy link
Owner

关于第三点,可不可以改成第一个 strictly-volatile 或者不对称出现在前 n 个细胞,或者干脆限定为前一半/前三分之一?那样会比较容易实现。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants