Chess@home: 打造最厉害的国际象棋AI
by yuanyi
at 2011-09-09 08:38:46
original http://item.feedsky.com/~feedsky/heikezhi/~8608072/564698635/6713895/1/item.html
Chess@home项目是在一个叫做Node Knockout的48小时编程竞赛上由Joshfire团队打造的一个分布式的Javascript 国际象棋AI应用，他们受到SETI@home项目（一个通过分布式计算寻找外星人的项目）的启发，决定利用Node.js在I/O方面的优势，探索使用Javascript来打造一个高度可扩展的分布式计算平台的可能，这样，用户只要通过浏览器进行访问就可以加入计算。
但是应该计算什么东西呢，他们在吉尼斯记录中发现了一个叫做“最大象棋AI网络”的条目，目前的记录只有2070个节点，他们认为这条记录是时候被刷新了，于是 Chess@home项目就诞生了，只要访问它们的网站，你就已经加入了一个分布式的象棋AI网络，并且你可以看到你当前对战的电脑数量，咱么样，赶快去杀一盘吧！
挑战
Chess@home同时也分享了他们在打造这一平台时遇到的挑战，技术控请继续往下看：
1. 延迟，国际象棋的标准比赛规则是90分钟，也就是说只要平均一分钟计算出一步就可以了，但这对没有耐心的Web用户显然是不合适的，由于游戏窗口需要与服务器实时交互，但是大部分分布式计算架构都没有考虑这种高吞吐量的情况，因此他们需要寻找新方案，WebSocket显然是个不错的选择
2. 并行，为了减低延迟，他们需要寻找一种方法将每一步移动的计算量分割成几千份，以保证每一个Worker的计算量尽可能的小。
3. Javascript性能，State-of-the-art 象棋AI可以每秒扫描1500万个节点（NPS），但是他们使用的开源Javascript AI GarboChess只能做到100K NPS，相差了150倍，不过作为一个48小时的实验项目，单台机器100K节点已经足够他们实现刷新吉尼斯记录的目标了，所以他们没有在这块浪费太多时间。
另外要说的是，打败卡斯帕洛夫的IBM深蓝也只有200m NPS，所以他们认为，只要给他们2070个阶段，超越深蓝也不是没有可能。
4.容错/安全，在第三方客户端运行Javascript意味着你不能完全信任它们，不管是从可达性还是可靠性上来说，所以它们将任务单元以一个FIFO的队列保存在了MongoDB中，如果有一个节点在5秒中内没有返回计算结果，那么就将有第二台机器来接手计算。
整个系统的原型设计如下：
其中使用了以下技术：
1. dnode，一个node的异步双向远程方法调用库，它可以通过socket.io同时支持网络Socket和Websocket通讯，这就保证了服务器端的进程可以使用同样的接口来和客户端或是和其它服务端进程进行通讯。
2. Web Workers，Javascript是单线程的，这就意味着你不可能同时运行多个脚本而不影响UI的响应，Web Workers提供了一种机制，可以让javascript运行高计算量的任务而不阻塞客户端UI和用户交互，并且Web Worker还有一个Node.js的实现node-webworker，这就保证了它们可以在服务端使用同样的接口。
3. MongoDB，使用MongoDB只是因为MongoHQ赞助了活动，所以它们决定试试这个键值数据库
4. Node，整个架构的核心，Node让它们可以快速开发，并在服务端和客户端共享代码，同时为高性能的I/O提供可靠保障。
5. Master上的AI，尽管这可能会妨碍可扩展性，但是因为APHID算法需要先生成一个小的计算树然后才能在客户端分派任务，所以还是需要对服务器上的AI进行一些调用，这个问题会在以后的版本解决。
最后，如果你对它们的实现感兴趣，可以在Github查看项目源代码：http://github.com/joshfire/chessathome
想和我们一道传播黑客精神？快来加入吧！
| 无觅猜您也喜欢： | |||
 贪吃蛇AI挑战赛第二季 |
 IfItWereMyHome: 如果我生在这个国家 |
 一个绝对新手的绘画和素描学习之旅 |
 220美元让你摆脱纸张 |
| 无觅 | |||
