这是一个讨论围棋变化数目的程序，请你帮我分析一下算法时间复杂度。提出建设性意见的都给分!
21 个解决方案
#1
原文贴出吧，看来大家都懒：
围棋的合理变化有几种及一个粗浅的java程序
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
所以很久以前我曾经在论坛上提出过“围棋合理的变化到底有几种”的问题。我原先想从纯组合数学的角度来解决，试图得出一个简单的表达式结果来。但想了半天，也没有一种合理的思路。写个程序来计算当然是可能的，但当初论坛上似乎所有人都说这没意义。我心有不甘，最近终于借着学习java的机会写了个这么粗浅的程序(http://marsd.mofile.com/9279267877819340/7373955099011419/2/AFBB2BF33C56E76ECE0BA56D7EF0F128/GoCount.java.txt)。
这个程序的算法无疑是很直接和低效的，它就是对一个n*n的棋盘，枚举所有3^(n*n)种情况，对每种情况判断每个点是否都是活棋，如果每个点都是活棋，则全局是一个合理的局面。对每个点是否活的判断标准(对应isAlive函数)是一个递归：一个点存活当且仅当它是一个空点或与这个点相邻的点上有空点或同色活棋。
这个程序的效率分析如下：
enumAllStatus函数枚举所有状况，共执行3^(n*n)次。在每一次执行enumAllStatus中，要调用isValid函数（判断是当前局面是否合理），它又调用：resetVisited函数(重置每个点的访问标志)，执行n*n次； isAlive函数（判断每个点是否活），也执行n*n次。IsAlive函数又是一个递归函数，它的递归深度不太好估计，我感觉它大概会是与n线性阶的一个数。所以isAlive总共执行次数会是o(n^3)，相对于resetVistied，它起主要作用。所以整个算法的时间复杂度是o(3^(n*n)*n^3)。
我计算了一些结果，设一个n*n的棋盘，它的所有合理变化的数字用V(n)表示的话，则V(1)=1,V(2)=57, V(3)=12675,V(4)= 24318165. 在我的机器上，计算V(3)用了125ms，计算V(4)用了498907ms，约8分多钟。而如果用计算V(3)的时间和前面的时间复杂度估算计算V(4)的时间（忽略次要项和常系数），结果将是648000ms，与实际情况在同一数量级上，所以我感觉我的时间复杂度估计还是大致准确的。
但这样的话，估计计算V(5)需要的时间大约在几百天的数量级上。另一个问题是，目前我用的是int的变量来计数，java中int型最大值是2^31-1，它只能处理n=4的情况。即使改成long型，它也只能处理n=5，你可以自己算一下。当然，这是一个次要问题，算法的低效才是主要问题。
另一个有趣的思考是考察V(n)/3^(n*n)的值，也就是合理的变化占所有变化的比值。根据目前结果：
n=2: V(2)=57, 57/3^4= 0.7037
n=3: V(3)=12675, 12675/3^9= 0.6440
n=4: V(4)=24318165, 24318165/3^16=0.5649
似乎是越来越小，那它最终会不会去趋向于一个常量呢？我感觉如果乐观估计的话V(n)/3^(n*n)会趋向于一个大于0.5的值，至少也是1/3，但苦于找不出证明。我很希望谁能先给出一个它不会趋向于0的证明。
另一方面，你也可以帮我优化一下算法，但主要的优化是要使程序不必枚举3^(n*n)种变化，否则程序不会有质的改善。
围棋的合理变化有几种及一个粗浅的java程序
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
所以很久以前我曾经在论坛上提出过“围棋合理的变化到底有几种”的问题。我原先想从纯组合数学的角度来解决，试图得出一个简单的表达式结果来。但想了半天，也没有一种合理的思路。写个程序来计算当然是可能的，但当初论坛上似乎所有人都说这没意义。我心有不甘，最近终于借着学习java的机会写了个这么粗浅的程序(http://marsd.mofile.com/9279267877819340/7373955099011419/2/AFBB2BF33C56E76ECE0BA56D7EF0F128/GoCount.java.txt)。
这个程序的算法无疑是很直接和低效的，它就是对一个n*n的棋盘，枚举所有3^(n*n)种情况，对每种情况判断每个点是否都是活棋，如果每个点都是活棋，则全局是一个合理的局面。对每个点是否活的判断标准(对应isAlive函数)是一个递归：一个点存活当且仅当它是一个空点或与这个点相邻的点上有空点或同色活棋。
这个程序的效率分析如下：
enumAllStatus函数枚举所有状况，共执行3^(n*n)次。在每一次执行enumAllStatus中，要调用isValid函数（判断是当前局面是否合理），它又调用：resetVisited函数(重置每个点的访问标志)，执行n*n次； isAlive函数（判断每个点是否活），也执行n*n次。IsAlive函数又是一个递归函数，它的递归深度不太好估计，我感觉它大概会是与n线性阶的一个数。所以isAlive总共执行次数会是o(n^3)，相对于resetVistied，它起主要作用。所以整个算法的时间复杂度是o(3^(n*n)*n^3)。
我计算了一些结果，设一个n*n的棋盘，它的所有合理变化的数字用V(n)表示的话，则V(1)=1,V(2)=57, V(3)=12675,V(4)= 24318165. 在我的机器上，计算V(3)用了125ms，计算V(4)用了498907ms，约8分多钟。而如果用计算V(3)的时间和前面的时间复杂度估算计算V(4)的时间（忽略次要项和常系数），结果将是648000ms，与实际情况在同一数量级上，所以我感觉我的时间复杂度估计还是大致准确的。
但这样的话，估计计算V(5)需要的时间大约在几百天的数量级上。另一个问题是，目前我用的是int的变量来计数，java中int型最大值是2^31-1，它只能处理n=4的情况。即使改成long型，它也只能处理n=5，你可以自己算一下。当然，这是一个次要问题，算法的低效才是主要问题。
另一个有趣的思考是考察V(n)/3^(n*n)的值，也就是合理的变化占所有变化的比值。根据目前结果：
n=2: V(2)=57, 57/3^4= 0.7037
n=3: V(3)=12675, 12675/3^9= 0.6440
n=4: V(4)=24318165, 24318165/3^16=0.5649
似乎是越来越小，那它最终会不会去趋向于一个常量呢？我感觉如果乐观估计的话V(n)/3^(n*n)会趋向于一个大于0.5的值，至少也是1/3，但苦于找不出证明。我很希望谁能先给出一个它不会趋向于0的证明。
另一方面，你也可以帮我优化一下算法，但主要的优化是要使程序不必枚举3^(n*n)种变化，否则程序不会有质的改善。
#2
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
怎么说考虑的太简单了把，提过子的地方还可以再下，打劫的话不知要提多少次呢
怎么说考虑的太简单了把，提过子的地方还可以再下，打劫的话不知要提多少次呢
#3
我知道啊，但我只考虑所有变化，不是考虑一盘棋的过程。所有变化的上限是3^(19*19)不会错的。
#4
你计算是有多少对局状态。
#5
不错不错 只得鼓励
不过 好的方法才是关键 像这个样子下去可不行啊
我也曾经想过 但是 同样苦于没有好的办法
现在还没有听说 谁能够过得了这关那
这关过了 围棋恐怕也要人输给机器了~~~
不过 好的方法才是关键 像这个样子下去可不行啊
我也曾经想过 但是 同样苦于没有好的办法
现在还没有听说 谁能够过得了这关那
这关过了 围棋恐怕也要人输给机器了~~~
#6
我最近在考虑证明v(n)/3^(n*n)不会趋向于0，似乎有点眉目了，都有时间的话，写出来让大家看看。我知道用程序来分析是很没意思的，所以我希望能用数学来分析围棋，这样有助于我们发现围棋中的一些隐含性质。
#7
兄弟 这个我还没有想到算法 在存储上 我就给难住了
不知道你是怎么存储棋局状态的 我看一盘器怎么也得90多字节啊
这可不是小数目 啊 你就是想保存9*9的棋盘所有的状态 也费劲啊
算法 就更谈不上了 不知道 你有什么好的办法
哦对了 顺便说上一句 我想的是 活棋之间是可以相互演化的 也就是说 从一盘活棋经过有规律的改动应该可以变为另一盘活棋 或者死棋 这样的判断应该少很多的计算.并且 所有的活棋 都可以相互的演化(这个没有论证 不知道对不对 现在是假设)
不知道你是怎么存储棋局状态的 我看一盘器怎么也得90多字节啊
这可不是小数目 啊 你就是想保存9*9的棋盘所有的状态 也费劲啊
算法 就更谈不上了 不知道 你有什么好的办法
哦对了 顺便说上一句 我想的是 活棋之间是可以相互演化的 也就是说 从一盘活棋经过有规律的改动应该可以变为另一盘活棋 或者死棋 这样的判断应该少很多的计算.并且 所有的活棋 都可以相互的演化(这个没有论证 不知道对不对 现在是假设)
#8
为什么要保存所有棋局状态呢？我的算法是判断完某个局面是否合理后，这种状态就被抛弃了。不过你要考虑棋局的演化，那就得保存棋局状态了。
如果你是说我证明"v(n)/3^(n*n)不会趋向于0"，那肯定是用纯数学的方法，不会用程序分析的。
如果你是说我证明"v(n)/3^(n*n)不会趋向于0"，那肯定是用纯数学的方法，不会用程序分析的。
#9
o 才明白 你是要最后的结果 只是知道又多少种棋局就可以了!!
呵呵
呵呵
#10
呵呵，应该是趋向0的
如果一个2n*2n的棋局，我们可以将棋盘划分成4个n*n的小棋局。
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”，因为在合并
后，每块棋都只能增加气（边界（没有气）变成对方棋子（没有气）或空格(气）或自己的棋子（可能有气））。
记r(n)=v(n)/3^(n*n)
所以我们得到r(2n)>=r(n)^4.
但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高
可以假设有个常数C,使得r(2n)<=C*r(n)^4
这样，我们可以得出r(n)的渐进式为
r(n)=A*exp(-b*n^2)
我估计b大概在0.04左右，也就是说是收敛到0的，但是要n大于10左右才比较明显
如果一个2n*2n的棋局，我们可以将棋盘划分成4个n*n的小棋局。
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”，因为在合并
后，每块棋都只能增加气（边界（没有气）变成对方棋子（没有气）或空格(气）或自己的棋子（可能有气））。
记r(n)=v(n)/3^(n*n)
所以我们得到r(2n)>=r(n)^4.
但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高
可以假设有个常数C,使得r(2n)<=C*r(n)^4
这样，我们可以得出r(n)的渐进式为
r(n)=A*exp(-b*n^2)
我估计b大概在0.04左右，也就是说是收敛到0的，但是要n大于10左右才比较明显
#11
没看懂你怎么得出r(2n)>=r(n)^4的。
你已经得出v(2n)>=4v(n)，很不错的思路。接下去：
r(2n)=v(2n)/3^(2n*2n)=v(2n)/3^(4*n*n)>=4v(n)/(3^(n*n)*3^(3*n*n))=4*r(n)/3^(3n*3n).
即r(2n)>=(4/3^(3*n*n))*r(n)
你的结论我看不懂。
你已经得出v(2n)>=4v(n)，很不错的思路。接下去：
r(2n)=v(2n)/3^(2n*2n)=v(2n)/3^(4*n*n)>=4v(n)/(3^(n*n)*3^(3*n*n))=4*r(n)/3^(3n*3n).
即r(2n)>=(4/3^(3*n*n))*r(n)
你的结论我看不懂。
#12
哦，我懂了为什么r(2n)>=r(n)^4，其实按我的式子推理下去就可以了。
可你后面还是给出一个假定：“但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高”，所以不是严格的证明。
你看，我也可以说4个n*n的不合理局面拼成一个2n*2n的合理局面也很常见啊。
还有，你数学很强！
可你后面还是给出一个假定：“但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高”，所以不是严格的证明。
你看，我也可以说4个n*n的不合理局面拼成一个2n*2n的合理局面也很常见啊。
还有，你数学很强！
#13
怎么都成了熵增原理啦。
#14
是很不严密的。主要是"合理的"棋局不好描述。
不过可以知道，我们分析数列
log(r(n))/n^2比较好。
我上面的猜测就是说 log(r(n))/n^2的极限是存在的，而且小于0。
不合理的局面可以拼成合理的是不少的。
而如果你的结论成立，那么必然有log(r(n))/n^2趋向0。
也许实际上用log(r(n))/n更好一些:)
不过可以知道，我们分析数列
log(r(n))/n^2比较好。
我上面的猜测就是说 log(r(n))/n^2的极限是存在的，而且小于0。
不合理的局面可以拼成合理的是不少的。
而如果你的结论成立，那么必然有log(r(n))/n^2趋向0。
也许实际上用log(r(n))/n更好一些:)
#15
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”
在3*3棋盘中(1,1)与(2,2)是空格，(3,3)是黑子，其余都是白子，这应该是合理的吧。但通过垂直与水平翻转得到另外三个3*3棋盘后，再合并成一个9*9棋盘就不合理了。(中间有4个黑子，其余是白子或空格)
在3*3棋盘中(1,1)与(2,2)是空格，(3,3)是黑子，其余都是白子，这应该是合理的吧。但通过垂直与水平翻转得到另外三个3*3棋盘后，再合并成一个9*9棋盘就不合理了。(中间有4个黑子，其余是白子或空格)
#16
3*3棋盘不合理。黑子无法存在
#17
to liem(阿明)：
而且你说的3*3棋盘确实是不合理的。如果n*n的棋盘是合理的，9个这样的棋盘拼成3n*3n也肯定是合理的。
而且你说的3*3棋盘确实是不合理的。如果n*n的棋盘是合理的，9个这样的棋盘拼成3n*3n也肯定是合理的。
#18
hehe,还有一个结论
将2n*2n的合理棋盘分成4个小棋盘后，在n*n小棋盘的新边界后面添加一行(和一列)
而且它们上面不放置任何棋子，可以形成一个(n+1)*(n+1)的合理棋盘。
所以
v(2n)<=v(n+1)^4
将2n*2n的合理棋盘分成4个小棋盘后，在n*n小棋盘的新边界后面添加一行(和一列)
而且它们上面不放置任何棋子，可以形成一个(n+1)*(n+1)的合理棋盘。
所以
v(2n)<=v(n+1)^4
#19
和前面的结合，就是
v(n)^4<=v(2n)<=v(n+1)^4
就是放松过头了
v(n)^4<=v(2n)<=v(n+1)^4
就是放松过头了
#20
我觉得要解决v(n)/（n*n）的极限问题，有一个方法实现解决如下问题：
一个n*n的棋盘上，放p颗棋子，最多可以将棋盘分成几个“区域”？
“区域”是这样定义的：盘面上一些空点，如果这些空点放满同色棋子，则这些棋子属于同一块棋，也就是要么一起活，要么一起死。
说这么罗嗦，其实用围棋行话来说，“区域”就是“一块空”而已。
显然要把棋盘分割成最多的空，从角上开始分割最好，比如19*19的棋盘，两颗棋子，可以划出两个区域，4颗棋子，可以划分出3个区域，6颗棋子可以划分出5个区域等等。
我的要求是把最多的区域数用p和n表示出来，如果不能精确表达，至少给出个比较精确的上限。我感觉是需要用分段函数的。
我后面几天不能上网，希望下周有谁能给出一个结果。
一个n*n的棋盘上，放p颗棋子，最多可以将棋盘分成几个“区域”？
“区域”是这样定义的：盘面上一些空点，如果这些空点放满同色棋子，则这些棋子属于同一块棋，也就是要么一起活，要么一起死。
说这么罗嗦，其实用围棋行话来说，“区域”就是“一块空”而已。
显然要把棋盘分割成最多的空，从角上开始分割最好，比如19*19的棋盘，两颗棋子，可以划出两个区域，4颗棋子，可以划分出3个区域，6颗棋子可以划分出5个区域等等。
我的要求是把最多的区域数用p和n表示出来，如果不能精确表达，至少给出个比较精确的上限。我感觉是需要用分段函数的。
我后面几天不能上网，希望下周有谁能给出一个结果。
#21
这是不可能精确计算的。
#1
原文贴出吧，看来大家都懒：
围棋的合理变化有几种及一个粗浅的java程序
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
所以很久以前我曾经在论坛上提出过“围棋合理的变化到底有几种”的问题。我原先想从纯组合数学的角度来解决，试图得出一个简单的表达式结果来。但想了半天，也没有一种合理的思路。写个程序来计算当然是可能的，但当初论坛上似乎所有人都说这没意义。我心有不甘，最近终于借着学习java的机会写了个这么粗浅的程序(http://marsd.mofile.com/9279267877819340/7373955099011419/2/AFBB2BF33C56E76ECE0BA56D7EF0F128/GoCount.java.txt)。
这个程序的算法无疑是很直接和低效的，它就是对一个n*n的棋盘，枚举所有3^(n*n)种情况，对每种情况判断每个点是否都是活棋，如果每个点都是活棋，则全局是一个合理的局面。对每个点是否活的判断标准(对应isAlive函数)是一个递归：一个点存活当且仅当它是一个空点或与这个点相邻的点上有空点或同色活棋。
这个程序的效率分析如下：
enumAllStatus函数枚举所有状况，共执行3^(n*n)次。在每一次执行enumAllStatus中，要调用isValid函数（判断是当前局面是否合理），它又调用：resetVisited函数(重置每个点的访问标志)，执行n*n次； isAlive函数（判断每个点是否活），也执行n*n次。IsAlive函数又是一个递归函数，它的递归深度不太好估计，我感觉它大概会是与n线性阶的一个数。所以isAlive总共执行次数会是o(n^3)，相对于resetVistied，它起主要作用。所以整个算法的时间复杂度是o(3^(n*n)*n^3)。
我计算了一些结果，设一个n*n的棋盘，它的所有合理变化的数字用V(n)表示的话，则V(1)=1,V(2)=57, V(3)=12675,V(4)= 24318165. 在我的机器上，计算V(3)用了125ms，计算V(4)用了498907ms，约8分多钟。而如果用计算V(3)的时间和前面的时间复杂度估算计算V(4)的时间（忽略次要项和常系数），结果将是648000ms，与实际情况在同一数量级上，所以我感觉我的时间复杂度估计还是大致准确的。
但这样的话，估计计算V(5)需要的时间大约在几百天的数量级上。另一个问题是，目前我用的是int的变量来计数，java中int型最大值是2^31-1，它只能处理n=4的情况。即使改成long型，它也只能处理n=5，你可以自己算一下。当然，这是一个次要问题，算法的低效才是主要问题。
另一个有趣的思考是考察V(n)/3^(n*n)的值，也就是合理的变化占所有变化的比值。根据目前结果：
n=2: V(2)=57, 57/3^4= 0.7037
n=3: V(3)=12675, 12675/3^9= 0.6440
n=4: V(4)=24318165, 24318165/3^16=0.5649
似乎是越来越小，那它最终会不会去趋向于一个常量呢？我感觉如果乐观估计的话V(n)/3^(n*n)会趋向于一个大于0.5的值，至少也是1/3，但苦于找不出证明。我很希望谁能先给出一个它不会趋向于0的证明。
另一方面，你也可以帮我优化一下算法，但主要的优化是要使程序不必枚举3^(n*n)种变化，否则程序不会有质的改善。
围棋的合理变化有几种及一个粗浅的java程序
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
所以很久以前我曾经在论坛上提出过“围棋合理的变化到底有几种”的问题。我原先想从纯组合数学的角度来解决，试图得出一个简单的表达式结果来。但想了半天，也没有一种合理的思路。写个程序来计算当然是可能的，但当初论坛上似乎所有人都说这没意义。我心有不甘，最近终于借着学习java的机会写了个这么粗浅的程序(http://marsd.mofile.com/9279267877819340/7373955099011419/2/AFBB2BF33C56E76ECE0BA56D7EF0F128/GoCount.java.txt)。
这个程序的算法无疑是很直接和低效的，它就是对一个n*n的棋盘，枚举所有3^(n*n)种情况，对每种情况判断每个点是否都是活棋，如果每个点都是活棋，则全局是一个合理的局面。对每个点是否活的判断标准(对应isAlive函数)是一个递归：一个点存活当且仅当它是一个空点或与这个点相邻的点上有空点或同色活棋。
这个程序的效率分析如下：
enumAllStatus函数枚举所有状况，共执行3^(n*n)次。在每一次执行enumAllStatus中，要调用isValid函数（判断是当前局面是否合理），它又调用：resetVisited函数(重置每个点的访问标志)，执行n*n次； isAlive函数（判断每个点是否活），也执行n*n次。IsAlive函数又是一个递归函数，它的递归深度不太好估计，我感觉它大概会是与n线性阶的一个数。所以isAlive总共执行次数会是o(n^3)，相对于resetVistied，它起主要作用。所以整个算法的时间复杂度是o(3^(n*n)*n^3)。
我计算了一些结果，设一个n*n的棋盘，它的所有合理变化的数字用V(n)表示的话，则V(1)=1,V(2)=57, V(3)=12675,V(4)= 24318165. 在我的机器上，计算V(3)用了125ms，计算V(4)用了498907ms，约8分多钟。而如果用计算V(3)的时间和前面的时间复杂度估算计算V(4)的时间（忽略次要项和常系数），结果将是648000ms，与实际情况在同一数量级上，所以我感觉我的时间复杂度估计还是大致准确的。
但这样的话，估计计算V(5)需要的时间大约在几百天的数量级上。另一个问题是，目前我用的是int的变量来计数，java中int型最大值是2^31-1，它只能处理n=4的情况。即使改成long型，它也只能处理n=5，你可以自己算一下。当然，这是一个次要问题，算法的低效才是主要问题。
另一个有趣的思考是考察V(n)/3^(n*n)的值，也就是合理的变化占所有变化的比值。根据目前结果：
n=2: V(2)=57, 57/3^4= 0.7037
n=3: V(3)=12675, 12675/3^9= 0.6440
n=4: V(4)=24318165, 24318165/3^16=0.5649
似乎是越来越小，那它最终会不会去趋向于一个常量呢？我感觉如果乐观估计的话V(n)/3^(n*n)会趋向于一个大于0.5的值，至少也是1/3，但苦于找不出证明。我很希望谁能先给出一个它不会趋向于0的证明。
另一方面，你也可以帮我优化一下算法，但主要的优化是要使程序不必枚举3^(n*n)种变化，否则程序不会有质的改善。
#2
围棋有几种变化是一个老问题了，比较粗浅的说法是3的19乘19次方，意思就是棋盘上每个点有空、黑、白三种状态，总共有19*19个点，所以得出这个结果。但实际上并没有那么多，因为在那么多状态中，有很大一部分是不可能出现的状态，也就是盘面上有死棋的状态。比如整个棋盘上布满棋子的状态都是不可能的，而这种状态就有2的19*19次方之多。
怎么说考虑的太简单了把，提过子的地方还可以再下，打劫的话不知要提多少次呢
怎么说考虑的太简单了把，提过子的地方还可以再下，打劫的话不知要提多少次呢
#3
我知道啊，但我只考虑所有变化，不是考虑一盘棋的过程。所有变化的上限是3^(19*19)不会错的。
#4
你计算是有多少对局状态。
#5
不错不错 只得鼓励
不过 好的方法才是关键 像这个样子下去可不行啊
我也曾经想过 但是 同样苦于没有好的办法
现在还没有听说 谁能够过得了这关那
这关过了 围棋恐怕也要人输给机器了~~~
不过 好的方法才是关键 像这个样子下去可不行啊
我也曾经想过 但是 同样苦于没有好的办法
现在还没有听说 谁能够过得了这关那
这关过了 围棋恐怕也要人输给机器了~~~
#6
我最近在考虑证明v(n)/3^(n*n)不会趋向于0，似乎有点眉目了，都有时间的话，写出来让大家看看。我知道用程序来分析是很没意思的，所以我希望能用数学来分析围棋，这样有助于我们发现围棋中的一些隐含性质。
#7
兄弟 这个我还没有想到算法 在存储上 我就给难住了
不知道你是怎么存储棋局状态的 我看一盘器怎么也得90多字节啊
这可不是小数目 啊 你就是想保存9*9的棋盘所有的状态 也费劲啊
算法 就更谈不上了 不知道 你有什么好的办法
哦对了 顺便说上一句 我想的是 活棋之间是可以相互演化的 也就是说 从一盘活棋经过有规律的改动应该可以变为另一盘活棋 或者死棋 这样的判断应该少很多的计算.并且 所有的活棋 都可以相互的演化(这个没有论证 不知道对不对 现在是假设)
不知道你是怎么存储棋局状态的 我看一盘器怎么也得90多字节啊
这可不是小数目 啊 你就是想保存9*9的棋盘所有的状态 也费劲啊
算法 就更谈不上了 不知道 你有什么好的办法
哦对了 顺便说上一句 我想的是 活棋之间是可以相互演化的 也就是说 从一盘活棋经过有规律的改动应该可以变为另一盘活棋 或者死棋 这样的判断应该少很多的计算.并且 所有的活棋 都可以相互的演化(这个没有论证 不知道对不对 现在是假设)
#8
为什么要保存所有棋局状态呢？我的算法是判断完某个局面是否合理后，这种状态就被抛弃了。不过你要考虑棋局的演化，那就得保存棋局状态了。
如果你是说我证明"v(n)/3^(n*n)不会趋向于0"，那肯定是用纯数学的方法，不会用程序分析的。
如果你是说我证明"v(n)/3^(n*n)不会趋向于0"，那肯定是用纯数学的方法，不会用程序分析的。
#9
o 才明白 你是要最后的结果 只是知道又多少种棋局就可以了!!
呵呵
呵呵
#10
呵呵，应该是趋向0的
如果一个2n*2n的棋局，我们可以将棋盘划分成4个n*n的小棋局。
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”，因为在合并
后，每块棋都只能增加气（边界（没有气）变成对方棋子（没有气）或空格(气）或自己的棋子（可能有气））。
记r(n)=v(n)/3^(n*n)
所以我们得到r(2n)>=r(n)^4.
但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高
可以假设有个常数C,使得r(2n)<=C*r(n)^4
这样，我们可以得出r(n)的渐进式为
r(n)=A*exp(-b*n^2)
我估计b大概在0.04左右，也就是说是收敛到0的，但是要n大于10左右才比较明显
如果一个2n*2n的棋局，我们可以将棋盘划分成4个n*n的小棋局。
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”，因为在合并
后，每块棋都只能增加气（边界（没有气）变成对方棋子（没有气）或空格(气）或自己的棋子（可能有气））。
记r(n)=v(n)/3^(n*n)
所以我们得到r(2n)>=r(n)^4.
但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高
可以假设有个常数C,使得r(2n)<=C*r(n)^4
这样，我们可以得出r(n)的渐进式为
r(n)=A*exp(-b*n^2)
我估计b大概在0.04左右，也就是说是收敛到0的，但是要n大于10左右才比较明显
#11
没看懂你怎么得出r(2n)>=r(n)^4的。
你已经得出v(2n)>=4v(n)，很不错的思路。接下去：
r(2n)=v(2n)/3^(2n*2n)=v(2n)/3^(4*n*n)>=4v(n)/(3^(n*n)*3^(3*n*n))=4*r(n)/3^(3n*3n).
即r(2n)>=(4/3^(3*n*n))*r(n)
你的结论我看不懂。
你已经得出v(2n)>=4v(n)，很不错的思路。接下去：
r(2n)=v(2n)/3^(2n*2n)=v(2n)/3^(4*n*n)>=4v(n)/(3^(n*n)*3^(3*n*n))=4*r(n)/3^(3n*3n).
即r(2n)>=(4/3^(3*n*n))*r(n)
你的结论我看不懂。
#12
哦，我懂了为什么r(2n)>=r(n)^4，其实按我的式子推理下去就可以了。
可你后面还是给出一个假定：“但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高”，所以不是严格的证明。
你看，我也可以说4个n*n的不合理局面拼成一个2n*2n的合理局面也很常见啊。
还有，你数学很强！
可你后面还是给出一个假定：“但是我认为2n*2n的“合理”棋局中，划分成4个棋局后出现不合理的小棋局的比例不高”，所以不是严格的证明。
你看，我也可以说4个n*n的不合理局面拼成一个2n*2n的合理局面也很常见啊。
还有，你数学很强！
#13
怎么都成了熵增原理啦。
#14
是很不严密的。主要是"合理的"棋局不好描述。
不过可以知道，我们分析数列
log(r(n))/n^2比较好。
我上面的猜测就是说 log(r(n))/n^2的极限是存在的，而且小于0。
不合理的局面可以拼成合理的是不少的。
而如果你的结论成立，那么必然有log(r(n))/n^2趋向0。
也许实际上用log(r(n))/n更好一些:)
不过可以知道，我们分析数列
log(r(n))/n^2比较好。
我上面的猜测就是说 log(r(n))/n^2的极限是存在的，而且小于0。
不合理的局面可以拼成合理的是不少的。
而如果你的结论成立，那么必然有log(r(n))/n^2趋向0。
也许实际上用log(r(n))/n更好一些:)
#15
如果4个小棋盘上的棋局都是“合理的”，那么大棋局肯定是“合理的”
在3*3棋盘中(1,1)与(2,2)是空格，(3,3)是黑子，其余都是白子，这应该是合理的吧。但通过垂直与水平翻转得到另外三个3*3棋盘后，再合并成一个9*9棋盘就不合理了。(中间有4个黑子，其余是白子或空格)
在3*3棋盘中(1,1)与(2,2)是空格，(3,3)是黑子，其余都是白子，这应该是合理的吧。但通过垂直与水平翻转得到另外三个3*3棋盘后，再合并成一个9*9棋盘就不合理了。(中间有4个黑子，其余是白子或空格)
#16
3*3棋盘不合理。黑子无法存在
#17
to liem(阿明)：
而且你说的3*3棋盘确实是不合理的。如果n*n的棋盘是合理的，9个这样的棋盘拼成3n*3n也肯定是合理的。
而且你说的3*3棋盘确实是不合理的。如果n*n的棋盘是合理的，9个这样的棋盘拼成3n*3n也肯定是合理的。
#18
hehe,还有一个结论
将2n*2n的合理棋盘分成4个小棋盘后，在n*n小棋盘的新边界后面添加一行(和一列)
而且它们上面不放置任何棋子，可以形成一个(n+1)*(n+1)的合理棋盘。
所以
v(2n)<=v(n+1)^4
将2n*2n的合理棋盘分成4个小棋盘后，在n*n小棋盘的新边界后面添加一行(和一列)
而且它们上面不放置任何棋子，可以形成一个(n+1)*(n+1)的合理棋盘。
所以
v(2n)<=v(n+1)^4
#19
和前面的结合，就是
v(n)^4<=v(2n)<=v(n+1)^4
就是放松过头了
v(n)^4<=v(2n)<=v(n+1)^4
就是放松过头了
#20
我觉得要解决v(n)/（n*n）的极限问题，有一个方法实现解决如下问题：
一个n*n的棋盘上，放p颗棋子，最多可以将棋盘分成几个“区域”？
“区域”是这样定义的：盘面上一些空点，如果这些空点放满同色棋子，则这些棋子属于同一块棋，也就是要么一起活，要么一起死。
说这么罗嗦，其实用围棋行话来说，“区域”就是“一块空”而已。
显然要把棋盘分割成最多的空，从角上开始分割最好，比如19*19的棋盘，两颗棋子，可以划出两个区域，4颗棋子，可以划分出3个区域，6颗棋子可以划分出5个区域等等。
我的要求是把最多的区域数用p和n表示出来，如果不能精确表达，至少给出个比较精确的上限。我感觉是需要用分段函数的。
我后面几天不能上网，希望下周有谁能给出一个结果。
一个n*n的棋盘上，放p颗棋子，最多可以将棋盘分成几个“区域”？
“区域”是这样定义的：盘面上一些空点，如果这些空点放满同色棋子，则这些棋子属于同一块棋，也就是要么一起活，要么一起死。
说这么罗嗦，其实用围棋行话来说，“区域”就是“一块空”而已。
显然要把棋盘分割成最多的空，从角上开始分割最好，比如19*19的棋盘，两颗棋子，可以划出两个区域，4颗棋子，可以划分出3个区域，6颗棋子可以划分出5个区域等等。
我的要求是把最多的区域数用p和n表示出来，如果不能精确表达，至少给出个比较精确的上限。我感觉是需要用分段函数的。
我后面几天不能上网，希望下周有谁能给出一个结果。
#21
这是不可能精确计算的。