关于搜算法,除了基本的alphaBeta 算法和常用的后期剪枝,黑白棋的引擎中最重要的手段是一种被称为 Multi-prob-cut 的前期剪枝手段 <- 中国开发网

CNDEV.ORG

当前在线

论坛

CBD
- 程序员情感CBD
- 程序员见面交流会
CBD开发区
- Java/J2ME
- .NET/C#
- 数据库
- Delphi/BCB
- Visual C
个人
- 袁国术的个人网站
- 翟旭东网!!!
其它
情感
游戏
- CNDEV-CS/WOW
- 浩宇长空
生活
论坛系统

bjwf：

关于搜算法,除了基本的alphaBeta 算法和常用的后期剪枝,黑白棋的引擎中最重要的手段是一种被称为 Multi-prob-cut 的前期剪枝手段

[阅读: 1682] 2007-05-31 03:11:14

而 multi-prob cut 技术就需要对大量高质量的对局进行统计分析,再用线性回归的方法计算估值和剪枝时的参数,相关的论文可以看
Michael Buro 发表的相关论文
http://www.cs.ualberta.ca/~mburo/publications.html
期中最重要的是:
ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm,
和Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello
这两篇.

由于论文里大量的数学专用术语,我把关键部分翻译了一下:

http://bjwf2000.googlepages.com/probcut.doc

相关信息:

同学们,谁能帮我跑个程序计算些数据. (821字) (bjwf [1268] 2007-05-29 14:08)
- 晚上可以，白天可能有别人用机器 (空) (coolbjwolf [495] 2007-05-29 14:15)
- 没这么快的机器 (空) (beijingshizi [491] 2007-05-29 14:16)
- 什么操作系统下的程序？我可以晚上帮你算一点 (空) (wuyan [725] 2007-05-29 14:29)
  - linux windows都可以,但都只能是x86的版本. (空) (bjwf [512] 2007-05-29 14:30)
    - xp x64, gentoo x64没问题吧 (空) (wuyan [546] 2007-05-29 14:31)
      - 没试过,可能不行,是32位编译器编译的. (空) (bjwf [528] 2007-05-29 14:41)
        试了一下，27分钟算了133 games (空) (wuyan [492] 2007-05-29 17:24)
        我的程序是单线程的，你的ＣＰＵ在这个程序上大约相当于E6300的水平． (288字) (bjwf [615] 2007-05-29 17:28)
- 召唤机器人 (空) (好望角 [550] 2007-05-29 14:44)
  - 非x86架构 (空) (Apache [509] 2007-05-29 14:45)
    - ╭∩╮（︶︿︶）╭∩╮ (空) (ycm0263 [464] 2007-05-29 19:46)
  - 的P133 (空) (leejd [485] 2007-05-29 14:46)
    - 。 (空) (ycm0263 [512] 2007-05-29 19:47)
  - . (空) (ycm0263 [453] 2007-05-29 19:46)
- 我把程序和一部分输入数据放在这里,能帮忙的下载试一下. (895字) (bjwf [883] 2007-05-29 14:57)
  - 人工对弈的优选走法库？ (49字) (haitao [563] 2007-05-29 15:01)
    - 你那几十万棋谱哪里来的? (空) (Apache [500] 2007-05-29 15:04)
    - 差不多吧,是计算32万局黑白棋,包括1980---2003年的世界锦标赛的所有对局, 用一个程序找出最后24步的最优走法. (28字) (bjwf [670] 2007-05-29 15:10)
      - 黑白棋也用这么算么？在联众黑白棋几乎没人能赢过我的 (15字) (没脾气2x [877] 2007-05-29 15:15)
        pda版的程序8成是zebra,并不是最历害的,zebra的算法所需的参数在一台xp 3000+的机器上算了几个星期. (空) (bjwf [598] 2007-05-29 15:17)
        zebra不是最历害的黑白棋程序,但是是最历害的共像程序，其它几个更历害的是研究性质的，没有得下载． (空) (bjwf [881] 2007-05-29 15:19)
        什么叫“共像”程序？ (空) (没脾气2x [523] 2007-05-29 15:20)
        共享，写错了． (空) (bjwf [487] 2007-05-29 15:21)
        我以为是他们动态计算的呢…… (34字) (没脾气2x [643] 2007-05-29 15:19)
        是动态计算的，但运态计算的算法需要的参数要提前算好． (空) (bjwf [587] 2007-05-29 15:20)
        fcl rs dn fcp j ld o gg tt , ybf rs dn wqj bn j ld o gg tt ,klf klf (空) (没脾气2x [645] 2007-05-29 15:24)
        动打成运是因为五笔，享打成像也是因为五笔，嘿嘿．我是五笔和拼音混用． (空) (bjwf [708] 2007-05-29 15:32)
        下黑白棋是用来锻炼大脑的，你这个下法，纯粹的耽误时间 (空) (狒狒 [1084] 2007-05-29 15:59)
      - 黑白棋好像已经是逻辑上遍历过每一种情况的了吧 (7字) (haitao [577] 2007-05-29 15:24)
        你记错了． (空) (bjwf [528] 2007-05-29 15:31)
- 前几天写的那个用到流水线的程序是不是为这个准备的？ (空) (没脾气2x [573] 2007-05-29 15:23)
  - 那是研究代码优化的时候想到的事情． (空) (bjwf [552] 2007-05-29 15:30)
- 编号为180-199的数据． (58字) (bjwf [711] 2007-05-29 17:44)
  - 更多的数据和说明. (56字) (bjwf [569] 2007-05-29 21:06)
    - 280－289我算，有重复吗 (空) (UnKnow365 [503] 2007-06-01 09:32)
  - 这个我来 (空) (Apache [482] 2007-05-29 22:09)
    - 多谢 ,http://bjwf2000.googlepages.com/resolveStatus ，我会每天更新 (57字) (bjwf [596] 2007-05-29 22:42)
      - 看来我的神舟笔记本不够强劲，运行一个半小时就已经烫手了，不敢再跑下去了。 (11字) (Apache [653] 2007-05-29 23:35)
  - 文件坏了？ (10字) (Apache [568] 2007-05-30 09:42)
    - winrar 3.62的版本是不是太低了 (92字) (Apache [602] 2007-05-30 09:46)
- 晚上算70~79，其它BTer有兴趣的也吱一声，免得重了 (空) (品雪 [487] 2007-05-29 21:38)
  - 多谢. (空) (bjwf [478] 2007-05-29 22:00)
    - 不用客气，现在算到076，平均一下差不多2.5小时一个。啥时候科普一下你用的算法？ (空) (wuyan [587] 2007-05-30 13:29)
      - 有源代码,事实上我用的是zebra的搜索引擎,自已写了个wraper,自已定义了一下输入输出的格式, 要的话发给你. (61字) (bjwf [676] 2007-05-31 10:59)
        thx，我对那个搜索算法有点兴趣 :-) 070-079的发给你了，一会收收 (空) (wuyan [535] 2007-05-31 11:01)
        关于搜算法,除了基本的alphaBeta 算法和常用的后期剪枝,黑白棋的引擎中最重要的手段是一种被称为 Multi-prob-cut 的前期剪枝手段 (411字) (bjwf [1681] 2007-05-31 11:11)
        收到,源代码也发给你了. (空) (bjwf [517] 2007-05-31 11:23)
  - 开始算80-89 (空) (wuyan [478] 2007-05-31 11:02)
    - 已搞定 (空) (wuyan [487] 2007-06-01 10:09)
- 发过来巴,明天一天有两台机器用. (空) (大字报 [516] 2007-05-29 21:43)
  - 多谢,到这里下载数据和说明:http://bjwf2000.googlepages.com/resolveStatus (56字) (bjwf [621] 2007-05-29 22:05)
- 建议你做成那个寻找外星人一样的分布式计算程序，然后做成病毒发布。估计用不了几天就帮你算完了。 (空) (pcplayer [560] 2007-05-30 13:34)
- 下边这几个有算得没有？偶有台P4 3.0 可以用偶算270-279 (7字) (softdream [601] 2007-05-30 19:24)
  - 目前没有人,多谢. (空) (bjwf [475] 2007-05-31 11:00)
- 这么大？ (13字) (茶壶 [516] 2007-05-31 15:53)
  - 我算290-299 (空) (大字报 [448] 2007-05-31 16:50)
  - 当然能． (空) (bjwf [468] 2007-05-31 20:35)
- 我算那个290-299,直接运行那个BAT文件即可吧 (空) (大字报 [464] 2007-05-31 16:52)
  - 看了一下，不好意思，那个BAT文件第一行写错了．稍微改一下就行了． (281字) (bjwf [578] 2007-05-31 20:37)
    - 已计算了290-293 (14字) (大字报 [579] 2007-06-01 09:14)
      - 来了一台新机器,继续294~299. (空) (大字报 [472] 2007-06-01 09:16)
- 算完了吗？发一个给我算吧 (空) (UnKnow365 [476] 2007-06-01 09:22)
  - 开始算280－289 (空) (UnKnow365 [496] 2007-06-01 09:36)
    - 从早上9：30到现在才算2个。机器不行暂停了 (空) (UnKnow365 [456] 2007-06-01 23:51)
- 160-179有人算了么？没有的话，我就开始了。上一个已算完。 (空) (softdream [443] 2007-06-01 14:11)
  - 多谢,160-179没人算,这是最后一个无人的数据包了. (空) (bjwf [444] 2007-06-01 16:14)
    - 哈，真巧，不过时间恐怕要周一了，我发现我的机子算的慢， (空) (softdream [432] 2007-06-01 17:54)
      - 完成，已发。 (空) (softdream [427] 2007-06-04 08:13)
- 290-299算完了,怎么发给你? (空) (大字报 [445] 2007-06-02 11:22)
  - 多谢,把resoloveLogs和ResolvedGames两个目录打包发给我 bjwf2000@gmail.com (空) (bjwf [454] 2007-06-02 12:13)
    - 已发,查收. (空) (大字报 [487] 2007-06-02 23:29)
- 感谢以上各位同学的大力相助，已经基本完工了． (空) (bjwf [540] 2007-06-04 10:56)

欢迎光临本社区，您还没有登录，不能发贴子。请在这里登录

页面内容处理时间: 0.018 - 583288