小明思考

高性能服务器端计算
posts - 70, comments - 428, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2012年9月20日

介绍

黑白棋,又叫反棋(Reversi)、奥赛罗棋(Othello)、苹果棋或翻转棋。黑白棋在西方和日本很流行。游戏通过相互翻转对方的棋子,最后以棋盘 上谁的棋子多来判断胜负。它的游戏规则简单,因此上手很容易,但是它的变化又非常复杂。有一种说法是:只需要几分钟学会它,却需要一生的时间去精通它。

黑白棋的棋盘是一个有8*8方格的棋盘。下棋时将棋下在空格中间,而不是像围棋一样下在交叉点上。开始时在棋盘正中有两白两黑四个棋子交叉放置,黑棋总是先下子。   

下子的方法:
把自己颜色的棋子放在棋盘的空格上,而当自己放下的棋子在横、竖、斜八个方向内有一个自己的棋子,则被夹在中间的全部翻转会成为自己的棋子。并且,只有在可以翻转棋子的地方才可以下子。

估价函数

黑白棋中最重要的是电脑对局势的判断,如何写好这样的估价函数是黑白棋人工智能程序的重点。

所谓的“金角银边草肚皮”,说明了子的位置的重要性是不同的。最最要的点是四个角,而和角相邻的三个点,则是不应该占领的,其次是四条边,占领后的好处也很多。

当然了除了子的位置,自由度也比较重要。
你的目标是限制对手的自由度(即棋步数量),同时增加自己的自由度




搜索算法

如果只是凭估价函数来走棋,是很难赢的,好的AI必须能够向前看几步,看得越深,棋力就越强。

这就涉及到博弈树搜索了,最经典是极大极小算法。

 

Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的方法。而开始的时候总和为0。
伪代码:
function minimax(node, depth)
   
if node is a terminal node or depth = 0
       
return the heuristic value of node
   
if the adversary is to play at node
       let α :
= +
       foreach child of node
           α :
= min(α, minimax(child, depth-1))
   
else {we are to play at node}
       let α :
= -
       foreach child of node
           α :
= max(α, minimax(child, depth-1))
   
return α

 


实现

 

用javascript和html5写了一个黑白棋,实现了人机对战,有还不错的智能, 我自己已经很难下赢了。

请用chrome或者firefox打开,chrome的javascript性能更好~

演示地址:  https://yshan.github.io/othello/

 


posted @ 2012-09-20 12:50 小明 阅读(13407) | 评论 (11)编辑 收藏

2012年5月31日

闲来无事,搞搞逆向工程分析一下三国群英2,今天的目标是去掉光盘提示,并让游戏正常进行。因为我玩的是原版,所以每当直接运行sango2.exe会弹出如下对话框:



我使用的工具是大名鼎鼎的OllyDBG。

首先,打开OD,打开sango2.exe, 运行程序,当出现对话框时暂时程序,发现停在此处:


仔细看以下几行代码,可以看出在40B207处有一个判断,如果EAX=0,则不显示对话框,并跳转到40B21F,那如果我们把B207的“JE SHORT 0040B21F”改为“JNE SHORT 0040B21F”,是否就可以不显示对话框呢?经测试,确实不显示了,但是游戏也直接退出了,并没有达到我们要的效果。看来这个地方只是出错后的程序处理,我们要找到更深的源头,才能解决这个问题。



上断点!我们要结合单步调试来理解程序的运行逻辑才能发现真正的解决方案。

观察对话框出现的时候,程序的堆栈如下:



发现这个函数的入口在40B00A,我们在此设置断点开始单步调试,会发现在调用4300F0出现对话框,跟踪进去。


用这样的方法跟踪进去,保持耐心和清醒的头脑,最终会发现4302C8会进行错误处理,导致对话框的出现,只要跳过即可。我们修改4302C1的代码为"JZ short 004302D1",即可跳过对话框,直接进行游戏。



最后一步,出补丁。使用右键功能【copy to executable】,然后另存为可执行文件就可以了。运行修改过后的sango2.exe,就会发现已经破解成功了。


posted @ 2012-05-31 21:53 小明 阅读(2280) | 评论 (2)编辑 收藏

2012年4月27日

     摘要: 最近遇到一个Windows Office Communicator 2007 崩溃的问题,有些意思,写下来跟大家分享。【现象】我们公司内部使用office communicator来做内部人员的IM工具,使用的是一个定制版本(plugin), 可以跟公司内部的组织架构做整合。我使用的OS是Windows 7 32bit,一开始使用并无问题,在某次windows update之后,发现没法添加好友,...  阅读全文

posted @ 2012-04-27 15:34 小明 阅读(3024) | 评论 (5)编辑 收藏

2012年3月28日

     摘要: leveldb中内存管理的技巧  阅读全文

posted @ 2012-03-28 18:00 小明 阅读(9132) | 评论 (1)编辑 收藏

2008年11月17日

     摘要: When program crashed ...  阅读全文

posted @ 2008-11-17 13:54 小明 阅读(3266) | 评论 (0)编辑 收藏

2008年9月27日

     摘要: 如何让char *p=new char[10];p[10]=10;报错?  阅读全文

posted @ 2008-09-27 10:59 小明 阅读(8506) | 评论 (5)编辑 收藏

2008年8月18日

     摘要: LeakDiag是微软一款检测memory leak的工具  阅读全文

posted @ 2008-08-18 19:12 小明 阅读(23381) | 评论 (4)编辑 收藏

2008年8月13日

     摘要: 奇怪的g++的行为  阅读全文

posted @ 2008-08-13 16:56 小明 阅读(3601) | 评论 (18)编辑 收藏

2008年7月30日

     摘要: 关于注册表中REG_MULTI_SZ类型  阅读全文

posted @ 2008-07-30 14:57 小明 阅读(2111) | 评论 (2)编辑 收藏

2008年7月28日

     摘要: 介绍远程调试技术  阅读全文

posted @ 2008-07-28 15:20 小明 阅读(7495) | 评论 (3)编辑 收藏

2008年4月18日

     摘要: VS2005 SP1的编译兼容性问题  阅读全文

posted @ 2008-04-18 18:01 小明 阅读(2801) | 评论 (0)编辑 收藏

2008年3月12日

     摘要: 使用完成端口的一些基本技巧  阅读全文

posted @ 2008-03-12 11:51 小明 阅读(6957) | 评论 (7)编辑 收藏

2008年3月10日

     摘要: 多进程服务端实现-共享socket  阅读全文

posted @ 2008-03-10 14:09 小明 阅读(11164) | 评论 (3)编辑 收藏

2007年10月12日

     摘要: 如何写printf的wrapper函数  阅读全文

posted @ 2007-10-12 14:13 小明 阅读(3005) | 评论 (0)编辑 收藏

2007年6月19日

     摘要:   阅读全文

posted @ 2007-06-19 16:31 小明 阅读(7600) | 评论 (1)编辑 收藏

2007年6月6日

     摘要:   阅读全文

posted @ 2007-06-06 17:44 小明 阅读(9526) | 评论 (13)编辑 收藏

2007年5月15日

     摘要: 从lua源码中学到的一点小东西  阅读全文

posted @ 2007-05-15 13:38 小明 阅读(10384) | 评论 (7)编辑 收藏

2007年5月5日

     摘要: D3D的摄像机动画  阅读全文

posted @ 2007-05-05 07:55 小明 阅读(1899) | 评论 (1)编辑 收藏

2007年5月4日

     摘要: D3D的画线能力  阅读全文

posted @ 2007-05-04 13:33 小明 阅读(3781) | 评论 (0)编辑 收藏

     摘要: D3D的画点能力  阅读全文

posted @ 2007-05-04 12:19 小明 阅读(3042) | 评论 (0)编辑 收藏