游戏设计理论：教会电脑玩游戏

geekman

首先，这并不是什么“人工智慧”理论教学。事实上我也不会使用“智慧”这两个字，因为这里面牵涉的程式设计根本离“智慧”太遥远了。这个教学/讨论的目的只是集中于让电脑理解一个游戏的规则，并根据这些规则，计算出最佳的行动，从而战胜对手（玩家）。

这个教学里面，我选择了TicTacToe这个游戏作为示范，原因有几个：
1）这是个大家都很熟悉的游戏，游戏规则大家都知道了，所以我就不必再花费唇舌来解释了。
2）这游戏的规则简单，容易消化（你真的会相信我这么说吗？嘿嘿嘿。。。）。
3）这是典型的对战型游戏。
4）游戏的玩法有一个固定的轨迹，容易归纳整理出一套运算规则。

首先，我们来整理出这个游戏的规则：

。。。呃，等等，还是先列出我们设计这“规则”的规则：
1）这套程式的目的就是让电脑“毫不容情的胜利”。
2）电脑会在确定最大胜利可能下尽可能阻止玩家胜利。

在以上的大前提之下，这是电脑要做的：
1）逐个的检查9个格子的胜利比数，也就是每一个格子的达成胜利的可能性。
2）在确定以上的比数之后，再检查这些行动是否会造成玩家的胜利（比如说一旦采取了这些行动，玩家就能在下一步获得胜利），并完全否定这些行动选择，不管它原本是否带有极大的胜利比数（这听来好像很矛盾，不过根据我设计的胜利比数的计算法，这种情形的确是会发生的），这就是所谓的围堵玩家的胜利机会。
3）在完成以上两个计算后，从计算结果里面选出最高胜利比数的格子，投入自己的符号。
4）重复以上的计算，直到任何一方获胜，或者出现和局为止。

1. +---+---+---+
   
2. | 1 | 2 | 3 |
   
3. +---+---+---+
   
4. | 4 | 5 | 6 |
   
5. +---+---+---+
   
6. | 7 | 8 | 9 |
   
7. +---+---+---+

复制代码

这是代表游戏“棋盘”的九个格子。下面是这九个格子各自的胜利可能性：

1. 格子1：
   
2. +---+---+---+
   
3. | + | - | - |  可能性：3
   
4. +---+---+---+  格子：1，2，3  1，5，9  1，4，7
   
5. | | | \ |   |  
   
6. +---+---+---+
   
7. | | |   | \ |
   
8. +---+---+---+
   
9. 
   
10. 格子2：
    
11. +---+---+---+
    
12. | - | + | - |  可能性：2
    
13. +---+---+---+  格子：1，2，3  2，5，8
    
14. |   | | |   |
    
15. +---+---+---+
    
16. |   | | |   |
    
17. +---+---+---+
    
18. 
    
19. 格子3：
    
20. +---+---+---+
    
21. | - | - | + |  可能性：3
    
22. +---+---+---+  格子：1，2，3  3，5，7  3，6，9
    
23. |   | / | | |
    
24. +---+---+---+
    
25. | / |   | | |
    
26. +---+---+---+
    
27. 
    
28. 格子4：
    
29. +---+---+---+
    
30. | | |   |   |  可能性：2
    
31. +---+---+---+  格子：1，4，7  4，5，6
    
32. | + | - | - |
    
33. +---+---+---+
    
34. | | |   |   |
    
35. +---+---+---+
    
36. 
    
37. 格子5：
    
38. +---+---+---+
    
39. | \ | | | / |  可能性：4
    
40. +---+---+---+  格子：1，5，9  2，5，8  3，5，7  4，5，6
    
41. | - | * | - |  
    
42. +---+---+---+
    
43. | / | | | \ |
    
44. +---+---+---+
    
45. 
    
46. 格子6：
    
47. +---+---+---+
    
48. |   |   | | |  可能性：2
    
49. +---+---+---+  格子：3，6，9  4，5，6
    
50. | - | - | + |
    
51. +---+---+---+
    
52. |   |   | | |
    
53. +---+---+---+
    
54. 
    
55. 格子7：
    
56. +---+---+---+
    
57. | | |   | / |  可能性：3
    
58. +---+---+---+  格子：1，4，7  3，5，7  7，8，9
    
59. | | | / |   |
    
60. +---+---+---+
    
61. | + | - | - |
    
62. +---+---+---+
    
63. 
    
64. 格子8：
    
65. +---+---+---+
    
66. |   | | |   |  可能性：2
    
67. +---+---+---+  格子：2，5，8  7，8，9
    
68. |   | | |   |
    
69. +---+---+---+
    
70. | - | + | - |
    
71. +---+---+---+
    
72. 
    
73. 格子9：
    
74. +---+---+---+
    
75. | \ |   | | |  可能性：3
    
76. +---+---+---+  格子：1，5，9  3，6，9  7，8，9
    
77. |   | \ | | |
    
78. +---+---+---+
    
79. | - | - | + |
    
80. +---+---+---+

复制代码

《待续》

Squall_Chua

一樣的東西我以前做過了
不過都是hard code的
其實我還滿想挑戰用neural network來做的
用自己寫的neural network

cskoom

是不是小学玩的3个XXX 3个OOO

geekman

呃。。。玩tic tac toe也需要用到牛肉网？？太夸张了吧？

晨天

期待geekman的教学

Squall_Chua

是拿來實驗neural network的learning algorithm吧了
我個人覺得很有趣

cskoom

我也很期待这教学。。

24hours

哈哈
其实alogarithm很简单，只是很复杂
一个bug可以玩死你

我自己有做一个，然后帖了又洗掉
我做时老师给我一个rule
1）这套程式的目的就是让电脑“毫不容情的胜利” < 就是不可以有这个
所以就。。。哈哈很简单

其实可一用另外一种方法玩，就是要让对方嬴
可行性没想过，不过应该很好玩

tensaix2j

原帖由 Squall_Chua 于 27-9-2008 04:48 PM 发表
是拿來實驗neural network的learning algorithm吧了
我個人覺得很有趣

neural network 都有很多種， 你是指哪一種？&#160;
棋類 這種 通常 都是 用 minimax + tree pruning的方式 來演算的。。

[ 本帖最后由 tensaix2j 于 28-9-2008 09:27 AM 编辑 ]

geekman

这几天暂时不会更新，事忙，请多包涵。

iquit

网上有很多programing games, 没玩过不妨下载来玩玩。

geekman

好不容易终于得空了，却赫然发现家里的电脑罢工了。。。哭啊

power supply老化导致电压不稳，结果RAM貌似损坏了，导致windows在不断被侵蚀损坏的情形下硬碟里的资料完全无法挽救，所有的project代码都救不回了。。。

今天还得花大笔钱购买新的电脑零件，然后还得组装，安装所有的软件，安装更新。。。可能还得好几天才能够完成，然后还得从头重写相关的project。。。

给我几天的时间为电脑和钱包哀悼一下吧。。。

cskoom

你回来啦 等了你好几天...期待这教学...

为你的钱包默哀1分钟。。。。

恭喜你有新电脑用了

geekman

新电脑已经安装好，软件也终于灌好了，只是这几天没有办法上网（前天发生在峇株吧辖的夺命火灾就在我家附近，把电话线都烧断掉了，TM 的大老爷们还没出现来维修电话线。。。考虑要割掉 Streamyx，换 3G 上网了）无法更新，上班时间也比较忙，没时间继续做这个project，大家还得等多几天。。。

tensaix2j

tic tac toe 有这么复杂meh

很久以前我想出一个蛮简单的 algorithm
电脑，每次会先 以下次序来check and 填

1. 格子 i（一到九)  ， 若填下i去可以直接至胜，就填i ，return，
若没 ，继续以下
2. 格子 i (一到九) ， 若对手填下去i 对手可以直接至胜，就顶 i return ；若没 ，继续以下
3。抢中间 （5）return ,  ；若没 ，继续以下
4.  抢corner （1，3，7，9)；条件， adjacent corner 不可以两边都是敌人的 （例如 3，7 是敌人的，就不可以填1 或9）;若没 ，继续以下
5.  step 1-4 还没填到，才任填一个空的格。


这个algo 至少电脑不会输咯。。

Squall_Chua

defence比較容易
但是如果電腦不agressive的話也不好玩

tensaix2j

tic tac toe 只有9 个格， 这种 抢中间 玩法 其实已经是最offensive 也是最defensive 了。。

geekman

我这个project的目的是展示如何教导电脑了解一个游戏的原理和规则，换句话说，就是规划出一个游戏的规则，然后根据这些规则设计出一个运算方式，让电脑能够有效率的计算出最佳的步法，所以才需要分析每一个格子的可能性。我的目的并不是要唬大家，误导大家tic tac toe 是什么复杂的游戏，这在我一开始所列出的条件和规则里面已经有提过了。如果你有更高效率的原理，可以让电脑每战必胜，欢迎你另开一楼来展示你的高见，但请明白我这个楼的目的并不是写一个必胜的，或什么“我有更简单的运算方式” 的 tic tac toe，而是和大家分享如何让电脑了解一个游戏的规则，以及如何针对游戏规则拟定策略，以及如何做出决定。

我了解大家都有自己心目中的最佳计算原理，但是我现在还是很忙，暂时无法继续进行这个project，我会尽量抽出时间，但是请让我有足够的时间把整个project写完，大家了解了这个project的本质之后才来推翻我的原理，好吗？

geekman

由于不想拖得太久，我现在只好先把我暂时还没时间进行检测的，尚未验证的理论写下来吧：

根据之前提出的每一个格子的可能性，检测九个格子，并选出最佳的下一步：
1）检测格子是否尚未被占据，如果已经被占据，就不必继续检测，直接放零分。
2）如果格子是空的，根据其可形成直线的可能性，给与分数，例如四个角落的格子都有三个可能性，所以就可得3分，中央有四个可能性，所以有4分，其他格子各自只有两个可能性，所以的两分，这个规则可让中央格子拥有最高优先选择性，四个角落次之，其他格子将是最后考虑的选择。
3）每一个可能形成直线的格子里面，如果有敌对的符号，则扣五分。因为这代表这一直线已经没有胜利的可能性了。
4）如果在可形成直线的任何一个格子里有己方符号，这意味着这一直线的胜利可能性提高了，加五分。
5）如果任何一直线上有两个己方符号，加五百分。因为这代表走这一步就能够获胜。
6）如果任何一直线上有两个敌方符号，加一百分。这是为了围堵敌方的胜利可能，宁可放弃制造己方的胜利机会，也不能让对方胜利，平局总好过输掉。

加减的分数可能需要调整，因为我还没时间去验证这些分数是否存在着矛盾的可能性。

完成九个格子的计算后，就选择分数最大的格子作为下一步。如果有超过一个格子有相同的最高分数，可选择：
1）随机任选一个
2）以敌方的角度，进行第二层次的计算，预测对方最可能选择的下一步，再综合现有的结果，选出能够尽可能减低对方获胜可能的一步。当然这个选择将会十分复杂，并不会很容易做。

检验胜利（一直线三个相同符号，八个检测）在算出胜算，填入新符号后才来检验胜利。

有兴趣地可以根据上面所列出的规则，自己写一个计算胜利分数的program出来，大家一起讨论，至于我自己，现在实在抽不出足够的时间来编写一个program 来验证以上的理论。

[ 本帖最后由 geekman 于 29-10-2008 01:22 AM 编辑 ]

Qchoc_yeQ

謝謝lz的心得， 期待lz的續帖