ITPUB第3届“盛拓传媒杯”SQL数据库编程大赛第2题及附加题参考解题思路

demonat

想像一下，有个军师把N种后续棋局的答案都搞到手了，于是N个空位都被标上了获胜者以及步数。那么为了回答第二题，只需按如下顺序查看这N种后续棋局：
A.如果存在当前棋手能获胜的棋局，那么最终胜者为当前棋手，步数则是各种获胜走法中最少的步数加一。因为当前棋手有主动权选择对他最有利的走法。
B.如果不存在当前棋手必胜的棋局，但存在和棋，那么最终答案为和棋。
C.如果N种结局都是对手取胜，那么答案是对手胜，步数则取最大的获胜步数。因为当前棋手会选择支撑最久的走法，而步数只算胜者的，不用加一。

不明白，第一条不用考虑对方起手走错才能获胜吗

〇〇

demonat 发表于 2015-12-21 10:23
不明白，第一条不用考虑对方起手走错才能获胜吗

必胜要尽快取胜,明知必输要拖延到底

Naldonado

第二题结果完全正确的有多少？

Naldonado

BITAND(t.o+cells.b,win.win_bits)=win.win_bits

这里不太懂，大叔能不能仔细讲一下如何用二进制来解决的。

赤霄剑

膜拜大神
赞 ！

uc_jmh

如果存在当前棋手能获胜的棋局，那么最终胜者为当前棋手，步数则是各种获胜走法中最少的步数加一。因为当前棋手有主动权选择对他最有利的走法。

这句话的依据是什么？

uc_jmh

能不能用一种更直白的思路呢？
试着往每一处可落子的位置落子，根据一定的游戏规则来给这一处的落子一个分值，来代表这一处落子的一个权重，然后每一步都用rank出来权重最高的继续循环下去？

uc_jmh

还是拿你的443来举例


从图上可以看到，除了你说的第一子落在第二排第二个（也就是6）之外 还可以落在 7  11  10 这都可以
总共要落5个子 也就是你说的x3。。。。
p.s.：在另一个贴我们讨论出来的我的输出是x4是因为有个bug....我擦
当然我现在的也可能有大量bug 我只是讨论一下另一种思路

uc_jmh

简单说一下思路：
我们当7 8 5来看问题
当落一个字的时候要判断：
1.自己是否自己能赢  如果自己能赢的话 游戏结束 （攻）                                          
2.是否能马上阻挡别人能赢 如果是 则放在这里 （防）
3.自己是否能造成活4  即当前点处于四子之中 并且这四个子的两边都能组成5个子   （攻）
4.自己是否能造成死4  即当前点处于四子之中 并且这四个子的一边都能组成5个子，另一边可是尽头 ，也可以是别人的子  （攻）
5.别人是否能活4  （攻）
6.别人是否能死4  （攻）
7.自己是否能造成活3  （攻）
8.自己是否能造成死3   （攻）
9.别人是否能活3  （防）
10.别人是否能死3（防）
11.自己活2   （攻）
12:自己死2   （攻）
13.别人活2（防）
14:别人死2（防）
15;自己活1（攻）
16:自己死1（攻）
17:别人活1（防）
18:别人死1（防）

简单按照以上规则  复杂来说不考虑  并不预测出更多的步数用代码来实现的话：
----------------------------------------
1.自己是否自己能赢  如果自己能赢的话 游戏结束 （攻）
判断当前落子的位置向上下左右以及四个斜边 包含自己在内的是否有连续的5个子
2.是否能马上阻挡别人能赢 如果是 则放在这里 （防）
判断当前落子的位置向上下左右以及四个斜边 是否有别人连续的四个子
3.自己是否能造成活4  即当前点处于四子之中 并且这四个子的两边都能组成5个子   （攻）
判断当前落子的位置向上下左右以及四个斜边 包含自己在内的是否有连续的4个子 并且顺延下去的两个方向上都不是别人的子或者已经到了尽头
4.自己是否能造成死4  即当前点处于四子之中 并且这四个子的一边都能组成5个子，另一外可是尽头 ，也可以是别人的子  （攻）
判断当前落子的位置向上下左右以及四个斜边 包含自己在内的是否有连续的4个子 并且顺延下去的两个方向上有一个方向不是别人的子或者已经到了尽头

----------------------------------以上为落子的算法 未完成的有
1.当不能勾成K个字的时候 不去考虑那么多 直接为小
2.当都能勾成多个的时候  要根据是否有别人的在这条边上 取最优
3.当都能勾成多个的时候  根据哪个勾成的多个几活  取最优
4.当都不能赢的时候  不用随机再下子  直接报活棋  
如果我们以443或者n＝m=k或者k和nm的值相差的并不大的时候来看的话  这几个可以先忽略。最起码这样不用生成游戏树这么庞大的东西、

newkid

demonat 发表于 2015-12-21 10:23
不明白，第一条不用考虑对方起手走错才能获胜吗

对手不会出错。
你要考虑的是这N种选择中，有没有必胜的。侥幸获胜（哪怕步数很少）也不能选，因为你下完主动权就轮到对方了。
如果有多种必胜的，则考虑步数少的。
就这么简单。