note

年度读书计划-总结

Posted on by hawk

去年11月份给自己定了一年的读书计划，结果可以说实现得非常糟糕。

决定当年读完的《linux内核》和《编译原理》两部书，都没有认真看完。只是概略翻了翻。

不过也不是说自己一点书都没有读。

图书馆借到的两本书，就看得津津有味。

一部是《linux设备驱动程序》，我一直都没找到合适的学习linux内核的书籍，才发现学习驱动是认识内核的一个非常好的切入点。而这一部书原理介绍的非常清晰，更容易从学习中抓到内核脉络。

另一部是《C专家编程》。年少无知的我一直认为自己对C语言了解已经足够了，接下来不再需要阅读语言相关的书籍了。看了这部书之后我的看法大大转变。可以说学无止境这句话用不能忘吧。这部书是Solaris系统程序员所写，风趣生动，包含大量系统开发过程中遇到的实际案例，同时介绍了C 语言标准、编译链接等等众多细节和trick。看这本书那两天，我几乎一直在捧腹大笑。实在是好书。尤其这本书言谈中吐露出的黑客文化，对我也是再一次的激励。

说到黑客文化，这里强烈推荐的是emacs中附带的advanture文字冒险游戏。相信喜欢tbbt的同志们应该已经看到Sheldon玩过了，“动用全球最先进的图形渲染引擎，AKA 大脑”，;)

新的一年一定要努力读书了，否则书架上书看不完也带不走，那就太浪费了！！

linux发烧

Posted on by hawk

最近玩linux比较hi，虽然没有什么正式的成果，但还是很开心～

先说说最近的吧，终于下定狠心把ubuntu上的gdm关掉了。以后进linux就全面进入黑屏时代。但说实话不能上网搜索材料的话，光有命令行也没什么用处。。因此找了几个重要的工具～

  • w3m 命令行下的网页浏览器 可嵌入emacs
  • freetalk 支持jabber的聊天工具～可以gtalk啦～
  • dfbsee DirectFB See 使用framebuffer的图片浏览程序，貌似还能播放视频～

基本上我对日常学习工作的需要也就是这些了。本来在emacs上配Gnus, 虽然配好了，但是很难用，尤其是似乎不是很适应gmail的标签风格，经常是显示不出来新邮件。我尝试在gmail里面设置规则，给所有邮件都加上一个inbox标签，才丑陋地解决了这个问题，但是还是很难用的一个东西。尤其是附件下载的方式也很糟糕。

现在有了w3m，可以直接访问gmail了，就没有这个问题了。w3m对下载的支持也很棒～唯一的问题就是不支持css吧。不过在命令行下面主要看的是文本，就算有css支持又怎样…反正命令行下面也没有字体字号什么的设置。

我其实最原始的在命令行下面看网页的想法是直接用wget把网页下载下来，再用脚本解析之后取出内容放纯文本里面看。可是wget只能下载，没法填写表单发送请求之类。我本以为可以直接在路径后面加?=什么的让他支持，但似乎失败了。例如尝试


wget google.com/search?q=hello

就失败了。收到403 forbidden 但是直接


wget google.com

是成功的。不知道是为什么……是google主动封锁了这样的读取方式吗？不知有没有解。。

freetalk没什么说的啦，纯粹好东西，还支持文件传输（未测试），比某些版本的gtalk客户端都好用。（不过不支持语音就是了。。）测试过聊天之后，进gmail一查，果然聊天记录也存在邮箱里了。可谓完美。加上使用@rainux同学的twitter gtalk机器人twimeido，还能发推。当然，用w3m连dabr也行。用不了web推，因为js太复杂的关系。。在命令行模式下直接ssh连上墙外的主机就可以建立tunnel，之后就在墙外了很方便。

dfbsee是我折腾了最久的一个东西。一直没找到好的命令行下看图工具。后来查到zgv，没来得及尝试，又发现了这个dfbsee。网上对dfbsee的评论是，因为使用splash的关系，很可能你的机器已经启用了framebuffer,那么为了看图去装另外一个图形驱动来运行zgv就不划算了。因为顾名思义，dfbsee是建立在fb上的看图工具。

ubuntu上没找到dfbsee的支持包，直接去官网下了源码。然后编译。要先编译安装DirectFB的代码库，很简单configure – make – make install就行了。然后就遇到问题了。官网下载的最新版的dfbsee源码和最新的dfb库居然是不兼容的，某个叫做DFBCardCapbilities的结构（后来发现貌似是个enum）找不到。网上搜了搜找到某个邮件列表里的讨论，原来开发人员把这个接口改名叫做DFBGraphicsDeviceDescription了，而dfbsee似乎还没来得及更新。按照他说的搞了个全文替换，要改这个结构还有一个get函数名。继续编译还有问题，有个叫做rotate.c的代码里面有很多形如


void * d;
(__u8*)d = ...;

的代码。首先那啥__u8,__u16,__u32之类的缺少定义，搞个typedef就行了，当然是对应的uchar,ushort和uint。接着那个类型强转在gcc眼里不算是lvalue,不能赋值。只好弄了个临时变量，中间倒腾了一下就行了。


void *d, __u8 *ptemp;
ptemp = (__u8*)d;
ptemp = ...;
d = (void*)ptemp;

其实也许改改编译选项也就过去了，但是实在懒得改就这么乱动代码蒙混过关了。编完了居然还不能跑，原来是某些so库它默认的路径和安装的路径不一样。用whereis找到那些库，然后ln -s 直接在对应地址下面建立符号链接，总算能跑了。其实本应该在configure的时候设置正确的路径的，但是实在懒得折腾了，就这样再次蒙混过关了。

这么折腾了半天之后这劳什字终于跑起来了。运行起来看看果然没白花时间。我的framebuffer设的1024*768*16bit，显示那些下载下来的墙纸什么的都很完美。还能一定程度地缩放。惟一缺点就是键盘处理有点问题，似乎是把按下一个键和抬起一个键当作两个事件处理了，结果按一次pagedown它要往后跳两幅图片。我一开始还以为文件夹里面有一半的图片他现实不了呢！后来用了他的slide-show功能，看到全部图片了～

不知道能不能把dfbsee设置成w3m的图片显示器，那样就太完美啦～不过这个以后再考虑吧。。

现在终极问题就是纯命令行模式下打不了中文。。这个实在不爽。看google就用英文当然也就算了，但是给人回信总不能总卖弄外国语吧囧。。。别跟我提zhcon,那东西太难用了。当然显示中文终于勉强能显示了。但是打字打不进去。打进去也是乱码。。况且现在我起zhcon只能sudo zhcon –utf8，结果是在zhcon里面搞的东西权限全是root的。这个很不爽。还要去弄那些中文字体的权限才能让zhcon不必跑在root下面，又要花时间折腾啊。。我准备再找找看有没有别的中文命令行，再试试看。最好是也是支持framebuffer的。“自己写一个”。。偶尔也会跳出这种想法。。但是最近这么忙不可能有时间折腾了。自己编译的内核还没跑成功过，正在试着写的linux驱动模块也有不少问题要调试。。所以其他想法先往后排吧。。

所以假如最近一段时间我给大家回邮件或者gt聊天总是跳英文，请不要生气。。我不是在卖弄英文。。。是懒得startx。。或者是正在备考12月底的英语机考。。妈的那玩意考不过就得明年重修。。抱歉爆粗口了囧|||

说到编译linux内核和学写linux驱动这回事，还有几句话想说。以前一直没想过要先写驱动。总觉得要先好好学会linux内核之后，在去学写驱动。结果买了些讲内核甚至讲源代码的书。不是说看不懂，而是说不知看来干嘛，有种无从下手的感觉。结果就晾在那里了。现在学写驱动，发现其实写驱动是学习内核的最佳手段，严重向大家推荐。这是一个很好的切入点，让你有事做，有一个目标，能去实践一些事情，然后你会遇到问题，就会想要做调试（当然就是内核调试），然后就会熟悉很多很多东西。现在我学的还浅，只知道些Oops啦panic啦什么的，strace也是刚刚学会用。接下来要试着弄user mode linux(这个也叫UML哈哈), 试着弄xen，还要试着弄很多好玩的东西。相信能学会更多吧。目前只能用用virtualbox，在x下是个好东西～不过既然决定要争取不进x，那还是要试着弄点更高级的！

于是自己加嘞个油吧。。（这么非主流。。。@ @）

php网页代理实现原理笔记

Posted on by hawk

去年冬天我说过要改一改phproxy让他能够正常浏览twitter和facebook。到现在马上要一年过去了我还没动静。。作出承诺而不执行实在糟糕。这里先做个笔记希望接下来能继续做下去。假如有同学愿意帮助我的话则极其欢迎！！

这里用访问网页的流程作为引子说明一下php网页代理的简单原理。
首先用户提交一个url给服务端。这里有个trick就是这个url以name为q的一个GET方法传入服务端。后面这个trick有很有效的应用。
服务端接到请求后读取这个url，需要做url的parse。这个在php里有现成的函数parse_url。需要解析的东西是很多的。比如要知道他是http还是https。要拆分出主机名和后面的路径。假如有端口号要记录下来，否则http赋以80端口，https赋以443端口。等等。
分析完成之后需要建立连接，然后发送请求。建立连接使用的是fsockopen。之后需要根据http协议建立请求。http协议其实是用\r\n分隔的一系列文本行。要说明的东西很多，比如GET还是POST方法，访问域名和路径是什么，cookie和session定义等等涉及到方方面面非常细节的东西。我还没有完全看完，不过如果只是想要读取一个简单的页面的话只需最基本的几个项目定义好就可以了。将这些内容做成一个字符串，然后使用fwrite写入到前面打开的socket中去。
发送请求之后就使用fread读取socket等待响应。需要用一个while循环不断读取，因为他可能一次发送不完。前面发送的东西是一个http头，跟上面提到的内容一样也是一系列\r\n分隔的文本项。需要根据协议依次处理这些内容。我在实验中完全忽略了这些内容只是将后面的网页显示出来。但phproxy的代码里面已经将处理http头的工作做得非常细致了。
理论上来说读取到的网页信息（也就是<html>标签包含的那一堆东西）只需直接echo出来就可以在页面上显示了。做到这里最原始的一个网页代理就做完了。但事实上这是远远不够的。首先发现的就是很多链接无法打开，css和js文件没能加载，很多图片也显示不了。为什么呢，因为他们使用了相对路径，而现在的主机域名已经变成phproxy架设的域名了。即使他们使用了完整路径，但是由于不经过代理的缘故客户端很可能还是无法加载。
因此必须将那些资源依次下载到服务器上，并将路径改成服务器上的路径，才能使用户正确的读取。
这里就用到了最开始的那个trick了。最佩服作者的地方就在这里。直接遍历下载下来的html脚本代码，找出所有可能出现网络路径的位置，例如src=啦，url(啦，background-image啦等等。并直接在这些路径前面加上phproxy路径加?q=就可以了。也就是本来

http://twitter.com/api/

这个路径就变成

http://phproxy.host.net/index.php?q=http://twitter.com/api/

这个形式。从而递归的调用了自己，将网站需要的资源全部下载下来。

当然这个简述简化了太多细节，尤其是http头的处理部分。但那些并不是我关心的。我关心的东西主要有两个。一个是为什么他不能访问facebook，一个是他为什么打开twitter之后无法发推（新版twitter只能显示标题栏）。

不能访问facebook原因很简单，问题出在用户通过form发送请求时使用的是明码传输。即使使用了base64编码也无济于事，因为那并不是一个加密算法。必须在用户输入url地址后通过javascript在客户端加密之后发送到服务端才能解决问题。这很简单，我昨晚尝试了一下，仅仅使用了每个字符的ascii码减1这种方式，就轻松穿过了防火墙。而服务端发回的数据$_response_body也使用某种简单算法加密，然后urlencoding之后放到一段javascript代码里面。

<script language="javascript">
function my_decode(body){...}
document.write(my_decode(decodeURIComponent("$_response_body")));
</script>

上面这个是拼接完的效果省略了很多单引号和字符串连接。当是伪代码来看吧。
这样客户端接收到数据后就会先解密然后显示出来。加密算法本身没有必要很复杂，只用最弱智的加密就可以。至少目前是这样。需要注意的是$_response_body里面的东西必须urlencoding，否则它里面有双引号啥的的话就会把整个javascript毁掉了。

但后续的工作并不轻松。因为前文提到整个网页中的全部资源都必须重新下载，因此必须修改代码中每一处可能用到url的地方，调试工作还需要一些时间。这两天正好是秋学期期末考试，考完试的空闲时间应该可以搞定。

另外一个问题是他为什么能上推但是不能发推。原因很简单那就是他还不支持ajax。要让他支持ajax稍微有点难度。当然说起来很容易那就是去parse 全部javascript代码，发现ajax的code就给他加上一前述proxy前缀就好了。但问题没那么简单。javascript实在太灵活了，任何地方都可能出现url。换句话说，要想完成这个功能要做javascript的语义分析。我想说那个工作的复杂度已经远远超出做网页代理的范围了。当然什么时候有空可以搜搜看有没有开源的js分析工具。但我不清楚有没有php版本的。假如有js版本的也可以，嵌一段js code到网页里在客户端解析。但无论如何是个大工程。至少对目前的我来说是。（假如有人愿意帮忙的话非常欢迎～～～）

如果totally放弃这个思路换一个想法呢？能不能在客户端发起ajax请求的时候去劫持他到另外一个服务器呢？那当然难度就简化多了，但那就不是一个网页代理可以做的事情了。需要我们自己写一个浏览器才行。。但，只是再多想一步，是不是做一个浏览器插件可以解决问题呢？说不定真可以！可惜我没有做浏览器插件的经验，目前还不好说。假如哪位同学有兴趣欢迎讨论～～

以上

年度读书计划

Posted on by hawk

读书明明是享受的，本来从不想把读书这种事情做成计划的。。。

十一回上海把寄存在同学那里的两箱书运回来了。大三的时候心血来潮，天天从书店往寝室运书，结果都看不完，去北京实习也不可能把书都运过去，毕业的时候看着一堆看不完的书，也舍不得卖舍不得扔，就想等读研时候好好看。。

本来觉得读研应该挺轻松的吧，应该有时间可以慢悠悠读读书看看小说吧…没想到项目这么紧，论文压力这么大，课程安排这么密。。时间真的是铺得满满的了，想要再拿出时间看书的话，实在是不得不制定计划了。。。现在必须在宁波把这堆书看个差不多了，剩下的书不能超过一个书包的容量。。否则以后运来运去要死人了。。

我看书的习惯是第一遍粗略翻看，第二遍细读感兴趣的章节。所以一本书看两遍才可以考虑扔不扔这个问题。下面的书单上依次放个优先级放个进度百分比，200%算是看完。做个单子自勉吧。。

理论类
Graph Theory 中度优先 0%
混沌与分形 不急不急 0%
自动机理论和计算导论 中度优先 0%
编译原理（龙书） 尽快看完 20%
算法
算法艺术与信息学竞赛（黑书） 中度优先 50%
数据结构与算法分析 中度优先 50%
语言
Effective and More Effective C++ 不急不急 160%
C陷阱与缺陷 不急不急 60%
C++对象模型 不急不急 120%
C++程序设计语言 不急不急 20%
系统
windows驱动开发 尽快看完 0%
深入理解Linux内核 尽快看完 20%
深入理解.Net 中度优先 0%
Windows核心编程 不急不急 160%
网络
TCP/IP协议栈 中度优先 20%
堆栈攻击 不急不急 60%
Google Hacks (快过时了) 60%
编程经验
编程珠玑 I, II 中度优先 160%
设计模式 不急不急 120%
人月神话 不急不急 0%
集体智慧编程 暂未上架 40%
历史
史记 看不完的 20%
三国志 看不完的 20%
伯罗奔尼撒战争史 中度优先 40%

呼。。这样看来，尽快看完的是 编译原理 和 windows驱动、Linux内核。
争取12月之前搞定！

单汇图的环的处理

Posted on by hawk

最近还在搞 SC AI。

由于每个单位仅能攻击敌人，所以其攻击链类似一个树（其每一个节点都是多源单汇的，类似于树的有一个父亲但有多个儿子的情况）。唯一不同的是这个树的树根也可能攻击一个敌人，从而形成环。但是由于一个单位只能攻击一个敌人，所以在一个独立的联通分量里面，最多只有一个环。

现在我在考虑使用递归来遍历这个图，然后得出每个单位在目前情形下再有多少轮会被消灭的报告。之所以要遍历，是因为有这种情况：a攻击b。c和d都攻击a。b攻击a。c和d又各自同时被两个单位攻击。在这种情况下，表面上看a遭受的攻击最多，他应该选择撤退。但是假如考虑到c和d的血量，或许c和d会在a之前被消灭。之后a遭受的攻击就不比b多了。所以在某种情况下，a应该采取的策略是继续进攻而不是撤退。

以上是我决定计算攻击链的理由。

于是在采取递归遍历这个图的时候，关键问题是怎样避开这个环。首先是如何发现这个环，然后是如何处理他。关于发现，我现在采取了一种非常低级的办法。我使用了一个静态的数组，记录每一次递归遍历到的节点。假如下一次递归遇到了这个数组里面的节点，则表示发现了环，并开始调用处理环的函数。我相信关于发现环一定有更好的算法。可惜暂时没有时间做了，加上问题都是节点数量在20以下的，所以也没有必要做得很复杂。
至于处理环的方法，我决定在这个环上寻找最早被消灭的节点。由于仅可能有一个环，所以先把除了环之外的分支计算完毕，之后将这些分支的贡献都先计算掉。此时得出的最先被消灭的单位，在环贡献也计算的情况下一定也是最先被消灭的。因此此时可以先计算这个节点的消灭轮次，然后在这个位置将环打开，并按照无环的逻辑去计算每一个节点。

这个问题抽象出来是个很有趣的图论问题，今后应该可以继续深入思考他的意义，并跟其他图论问题做一些比较，不过暂时先放在这里吧。

sc ai 估值ANN初步完成，计划作战模块的GA

Posted on by hawk

连续熬了几天夜，SC AI的估值函数神经网络和训练架构终于搭建完成了，现在就是还有一些代码中的小问题需要小修小补一下，然后就是再做一个自动反复启动的程序让他自己跟自己反复对战就行了。不过要自我对战的话，需要借老爸的电脑连成局域网才行。。那之前先让他和电脑AI练练再说吧。。

这部分只做了估值函数，也就是说只是不断预测比赛谁的胜率更大，而没有让他参与到决策之中（所以决策模块仍然是最基本的“勇气值”模型）。这里我为了能够将各个单位的位置信息形成输入放到神经网络中去，花了很多时间。。直接把横纵坐标放进去肯定是没有意义的。需要一些能够更好的刻画战场情形的特征值才能有效的训练神经网络。结果是我没有采用经典的ANN三层模型，而是使用了一种动态更改的模型。

现在我使用最小生成树来刻画战场特征，并将每一个最小生成树的边当作一个输入，这个边是一个复杂输入，包含对方的hp,护盾值，是否处于攻击状态，与自己的距离等信息，对每一个信息，都需要给定一个对应的权值用于训练。因此这个神经网络的神经元就是每个单位。我再将攻击和锁定目标也作为这个神经网络的输入边，来增加刻画战场状态的特征值。为了防止神经网络出现回路，我将神经元复制一遍，分别作为输入层和隐藏层，将前面介绍的最小树边和攻击边由输入层的对应单位连接到隐藏层的目标对应单位。这样做就保证了没有回路。最后我在输出层放了两个神经元，分别代表玩家0的胜利期望和玩家1的胜利期望。最后，由于所有的单位目前都是zealot, 因此他们的特征权值应该是共享的。我参照《机器学习》上介绍的方法，每次反响传播之后将其权值求平均值再一次赋值，使其能够更快的学习和避免过度耦合。

我使用了我自己同电脑对战的一个录像用于训练。首先写了一个解析录像的小程序，将每一帧的特征信息提取出来写入文件中。之后利用另外一个程序依次将这些特征信息进行计算和处理，将简单的坐标信息转换为最小生成树和攻击边等信息。然后将这些信息作为输入来训练神经网络。目前遇到的障碍是在比赛结束之前，无法给出比赛谁胜谁负的准确信息。如果一次比赛只能根据结果训练一次，则训练周期过长，是不可胜任。我采取《涌现》一书中提到的说法，认为根据估值函数求出的估计值，越接近比赛胜利时估计值越为准确。因此可以利用后面一帧的估值作为前面一帧估值的参照量，并依此进行反向传播。为了能够得到更快的训练速度，我设置当单位数量超过敌军，或单位数量相等而总血量大于敌军时，就认为本方处于优胜状态。这或许并不完全准确但已经是非常保守的估计了。我根据书中提到的标准，设置0.9为优胜，0.1为失败（前述神经网络中所有输出均通过sigmoid函数挤压到(0,1)区间）。至少在昨晚的几次实验中，这套方案得到了较好的成效，接下来的就是要继续训练他直到稳定为止了。为此我还需要再做更多录像，然后就是要想办法让他自己跟自己对战了。

接下来要做的就是决策部分了。这部分我准备使用GA, 即遗传编程。可以根据士兵处于不同情形时（危险/安全，接敌/后方，被包围/被保护，是否接触边界等等）分别设定不同的行为（攻击，攻击移动，移动，原地不动等等），然后通过遗传编程来找到最好的组合。当然好与不好的估值，则通过前述神经网络得出。

现在最愁的一部分就是如何决策移动。因为移动是一个几乎是非离散的量。不可能去考虑地图上的全部点。一定要给出合适的特征值来刻画好的和不好的移动目标。这包括了是否被包围，是否阻碍了友军等等。然而这样的特征值仍然没有找到。前面提到的最小生成树似乎有些意义，但对整体有意义的东西用在局部上有些困难。目前还在思考对策。。。

SC AI设计的强力纠错

Posted on by hawk

昨天熬了一夜之后，在非常兴奋以及脑袋糊掉的状态下写了最近的工作进展和思路。。可惜大多数都是语无伦次。。
今天在仔细读过之后，发现，大多数的想法，都是在写前面几个段落的时候和快要写完的时候不一样，结果导致前后很多矛盾，再加上使用了很多似是而非的术语，让整篇文章几乎没有说对的地方。。

这里也不可能把所有的毛病都改掉了，不过也好上一篇文章成了只有我自己才能看懂了胡言乱语。。。

先说说神经网络吧。上一篇文章多次提到神经网络，其实是指的几个不同的东西。并且这几处都没有给出神经网络的构造。而真正给出构造的一处，即采取各单位相连以广播行为等的那个构造，其实不是神经网络，最多只能说是一个参考神经网络而设计的通信模型。在Holland的一本叫做emergence的书中曾经提到过一种称之为元胞结构的构造，可能这个设计更近似于那个构造，但也还是有很多不同之处。应该说这是一个实验性的构造，也只是我的一时想象，暂时不能说他能够给AI设计起多大的帮助。

而至于使用神经网络结构来学习几项重要的特征，比如是否被封闭（能否逃离），目标健康程度能否在一击内消灭（计算护甲、hp、shield等），同理也可用上述原理计算自身是否安全。这些特征采用神经网络学习是有可能的。神经网络是一个相对静态的结构，必须用于学习能直接得到结论的结果。当然这里我说的神经网络是指没有环路的单馈三层神经网络了。这是一种成熟的技术，可以在AI学习中有很多应用。但也正是这个原因，使得他无法应用于博弈模型这样的无法立即得到反馈的机器学习中来。

昨天文章中说到的“估值函数”也是笔误，其实我想说的只是找到了几个重要的特征值，而没有希望直接设计估值函数。其实我昨天的想法是，通过设置神经网络或者类似于神经网络的其他模型，只要找到了估值特征值，令模型自行学习权值，则估值函数可以通过机器学习得到。这点也是昨天没有说清楚的。。

总之目前的状态是初步的想法有了，但是很多具体细节还没有想清楚。并且前面提到的最重要的部分，也就是类似于“元胞结构”的部分，还有很多没有明确定义的东西。这些地方还需要继续想清楚。

以上

SC AI 神经网络模型和遗传编程

Posted on by hawk

今天wp升级，手欠顺便升级了一下theme，结果忘记备份导致原先的更改全部消失，又重新折腾了好久。bo的外观稍稍有点变。。

昨天由于一整天没有干正事，导致晚上相当悲剧。。熬了一整夜，不过 SC AI的神经网络模型基本上有了框架了。接下来就可以根据各种YY往里面增加参数、估值函数和各种加权了。

目前仍然以考虑zealot为主，不过我发现对zealot适用的模型，对dragoon同样适用，只是需要让他重新适应一次估值函数的权值就可以了。因此这里还是继续仅讨论zealot。首先，确定每个单位拥有进攻和溃逃两套互不相干的策略机，然后给定一个决定是进攻还是溃逃的决策机制，就可以了。

这个决策机制我称之为勇气。当估值函数超过阈值的时候，认为这个单位士气高涨，会继续进攻，而当估值函数低于阈值的时候，这个单位士气低落，会决定溃逃。如果以zealot的攻击范围为单位，将zealot周围区域分成8个方格，则可将每个方格内是否有敌军或友军单位，作为一个神经元输入，更远的敌军或友军单位，通过更多的神经元相连间接得到，任何单位决定进攻任何目标或溃逃都需要作为一个信号向外部发送并引起这个神经网络内的其他神经元的策略改变。参考神经网络模型的疲劳机制，当单位持续士气高涨的时候，会将阈值按照一定的因子提高，使之勇气下降，同理，当单位持续溃逃的时候，会将阈值相应降低，使之变得较为容易参战。这个可变的阈值，可称为单位的勇气。

勇气的估值参数主要有如下几点：自身hp和shield，正在攻击自己的敌对单位数量（以及他们的被攻击情况和健康情况），自己正在攻击的敌对单位hp和shield。考虑这些的目的主要是为了估算自己能否在生存情况下消灭正在攻击的敌人。当然这个逻辑我不准备放入估值函数中，而令其通过神经网络训练学习得到。通过给定不同的加权估值，经过训练应该能得到和人思考出的相似的结论。

假如勇气决策为进攻，则选取攻击决策机，并令其给出一个攻击指令。攻击指令可以是：攻击最近的敌人，攻击hp和shield按照某种权值计算后健康程度最差的敌人（这和需要几次攻击才能消灭敌人有关系，需要折算护甲，攻击类型和目标体积的关系等复杂内容，例如Dragoon拥有20的damage，可是攻击被打光shield的zealot时一次攻击只能造成9hp左右的伤害，这是因为dragoon的爆炸攻击类型对zealot的小型单位只能造成一半伤害，而同时未升防御的zealot拥有1的armor，会抵消10%左右的伤害），攻击盟友正在攻击的敌人，攻击威胁最高的敌人，以及保持目前攻击目标不变。而得到这个攻击指令的效果，又可以采用：攻击单位命令，移动攻击命令，巡逻命令，移动/待命等命令来实现。因此想要使用一个模型来模拟全部的可能性，实在不可能。这里必须采用遗传编程的方式，令不同的策略模型在竞争中互相杂交和进化，最后得到较优的结果。

溃逃机制主要需要考虑的是两种特殊情况，即被友军封闭和被敌军封闭。假如溃逃单位被友军封闭，最好的策略是能够通过该单位向四周发送一条信号，而使合适的单位为其让路。这个信号同样可以用于保持阵型，即“最佳防御位置”的确定。而假如溃逃单位被敌军封闭，则应该立刻变为英勇，因为无论如何也逃不出去了，应该给敌人以最后的伤害。但如何确定某单位是否被封闭了？BWAPI似乎提供了函数，但我暂时还没有测试。否则使用周围单位的位置和权值，让神经网络自己去学习也是可行之道，不过似乎大材小用了……

以上就是最近一段时间测试和思考的内容。另外经过很多测试，对BWAPI和星际争霸游戏的各种特点也慢慢熟悉了，相信对接下来的开发会有帮助吧……

寻找第四维

Posted on by hawk

今天想了很久，感觉我们世界的维度不只有三个维度应该是一个相当合理而自然的事情。反倒是这个世界仅有三个维度，是一种令人难以信服的说法。

当然了，这其实是早就有人证明的了。比如因为引力导致的空间扭曲，会让光线的运行轨迹发生弯曲，就是一个好证据。根据广义相对论，引力导致空间扭曲。这句话我一直没有好好理解过。假如三维的平坦空间被扭曲，可以认为一定存在一个包含这个三维空间的四维空间，而那个三维空间是在这第四个维度上发生扭曲。当然这也仅仅是一种看法了。你也可以认为由于引力的影响，导致根本不存在平坦的空间体系。因此所有三维空间都是不平坦的。但是，假如这两种说法都是合理的，我认为前一种说法更简单。虽然多了一个维度，却让空间扭曲变得形象而自然了。

是不是说，其实我们的宇宙包含很高的维度都有可能（比如弦论推算的），只是人的感官没有感受更高纬度的能力呢？又比如，我们的宇宙应该被推断为“有限无边”的，这样的宇宙的体积是有限的，但是假如你驾驶飞船，无论如何也不可能飞到宇宙之外。这样的推断是合理的，因为宇宙体积若是无限的，将导致无穷大的质量和无穷大的引力，这是不可能的。而有限大的宇宙，假如有一个边界，那么“宇宙之外是什么”，将对前面的理论形成矛盾。因为“宇宙之外”假如还有物质，那就应该认为那些物质还属于宇宙，反复提出这个问题的结果是推出“宇宙无限”。所以“有限无边”的宇宙是一个在逻辑上较为靠谱的假设。而在这个假设下，宇宙是一个四维球体又是一个较好的解释。因为你无法想象一个三维球体或任何其他形状可以实现“有限无边”。假如是四维球体，就如同三维球体的表面实现了二维的有限无边一样，四维球体的“表面（其实应该叫做“表体”更合适）”则应该能够满足三维的“有限无边”。

以前有种说法是，更高的维度收缩了，以至于无法被发现。是否其实是反过来的，其实更高的维度是在更大的尺度上展现出来的，反倒是我们的感官可以观察的尺度太小了，以至于发现不了更高的维度呢？

寻找高纬度的好例子是古人证明地球是圆的的步骤。他们发现纬度不同的两个地区的正午日影并不等长(其实他们是观察日光是否直射到水井里啦)。地球表面是二维曲面。证明这个面在第三个维度上发生弯曲的方法，是通过考察距离遥远的两个地区。假如我们相信第四个维度是存在的，仅仅是因为尺度过大而无法发现，我们应该可以通过更大尺度的测量来得出吧。

但是，最令人担心的就是第四个维度无法通过人的感官察觉。以二维事物为例，假设存在一种无法感知第三个维度的物种，其中的两个生物叫做a和b。当a将一个二维茶杯送给b的时候，a感知到茶杯的二维移动。也就是在水平的前后左右四个方向的移动。他感觉到茶杯向b移动，并最后送到b的手中。但其实a和b是存在于三维空间中的，其实a和b在第三个维度上并不在同一个高度上。其实茶杯还略微向上移动了一点点距离。但是由于a和b都不具备感知第三个维度的能力，以至于他们没有察觉到茶杯的高度上的位移。在他们看来，茶杯经历了水平位移之后准确交给了b，一切都符合逻辑，没有存在第三个维度的可能性（结果a和b就都杯具了。。）。

假如是这样，假如由于这个缘故导致我们无法发现更高的维度，是不是我们就完全无法设计实验证实第四个维度的存在了呢？

应该还是有机会的。因为假如是那样的话，我们的世界应该是高维世界的一个三维投影。当我们在较高维度上变换角度的时候，这个投影应该会发生某种变形。只要能找到一种方式，使得我们能够观测到的东西，在更高的维度发生旋转，我们就应该能够抓住机会，发现这个新的维度。

当然了，我这里只是空谈空想而已。假如世界真的有更高的维度，我希望我能用我的双眼证实它的存在。

lisp学习笔记

Posted on by hawk

2013年重读这篇笔记，错误很多，对定义的理解有很多混淆；作为自己学习和成长的记录不再将其中的错误一一纠正了

刚刚开始学lisp，还只是开始熟悉他的语法。但是学lisp确实是开阔眼界的一个好办法，能从更高的角度来看程序语言。

至今为止任何类型的程序语言其实都是图灵机的一个实现。比如说经典的x86 CPU吧，他就是一个图灵机。这个问题我其实还是想了好久才想出来的。可能是我太愚钝了吧。。图灵机的一种描述是这样的，存在一个两边都无穷长的纸带，一个含有一系列状态和命令的指针。这个指针一次执行一个命令，或者向前或向后移动一格，或者在纸带上读取或写入一个符号，命令有可能改变指针的状态。而读取到的符号会根据指针的当前状态产生一个新的指令。循环往复。直至到达某个特定的状态（终态）停止下来。

一开始我觉得CPU的寄存器表示状态。可这样的话，寄存器的值是不确定的，于是似乎不能模拟确定有限自动机。静下心来想想，其实应该认为所有寄存器的一种取值组合就是一个状态，所以假如有m个寄存器，每个寄存器的取值数量是ni，则总的状态数量就是i从1取到m, 将所有的ni相乘。（不能打公式郁闷。。）然后应该认为汇编代码就是那个带子上的符号。这样比如

ADD a, a, b ;a=a+b

这样的一条指令，应该看作是一个符号（所有可能的汇编指令应该是有限的，可以认为每一个都给编了唯一确定的符号）。这个符号对应CPU的不同状态，（例如这里的a和b的所有不同状态组合），可以看作每个状态都有接受了这个符号之后指向一个新的状态的箭头。使得寄存器状态改变。比如对于a=1,b=3这组状态(1, 3)，这个箭头就应该指向(4, 3)，当然这里没有考虑溢出位啦。同时又存在一些其他的操作，例如处理内存或中断的操作，可以看作是向纸带上的特定位置写入字符（由于内存和中断的数量也是有限的，所以可以给他们的每一个地址对应纸带上的一个位置）。

那么lisp呢，lisp是怎样实现图灵机的呢？

根据lisp1的自解释逻辑，可以认为lisp是一个不断扫描输入纸带的一个指针。他的状态则由输入中给定的“环境”决定。可以认为lisp仅有函数定义和函数调用两种语法。对于函数定义，其实是增加了新的状态组，把它的所有形参的所有取值组合看作是一组状态加入到自动机中。而函数调用，就是将实参值带入形参，计算函数结果的过程，对应于状态接受一个输入指向另一个状态的一个箭头，即在此实参情况下，如何应该进入什么样的下一个状态（次态）。

不过很有趣的是，鉴于lisp的递归定义，可以认为他的状态机也是递归的。在运行的最初，该状态机仅有函数定义及函数调用的最基本语法。指针扫描纸带（程序源代码）一遍，生成了最外层的函数定义，这是状态机为这些新函数增加新的状态，之后指针移动到该函数调用的起始位置，第二遍扫描源码，生成新一层次的函数定义，向状态机添加新的状态，直至最终所有的函数定义全部生成结束，递归到最底层，所有的实参都被计算成为原子，再依次递回，直至最上层。

从这个角度看lisp的有趣之处在于他用自己的规则定义自己，不断充实自己。不过也因为这种灵活性，使得用c实现一个高效的lisp编译器变得有些困难。一开始我在考虑的是lisp只有递归没有循环，确实不符合c语言的常规思路。不过转念一想，尾递归优化成循环其实倒反而是一件轻松的事情，只需要将形参改成自变量，把递归调用的那一句改成goto到函数开头就可以了。然后再改成while循环即可。麻烦就麻烦在这个函数的动态声明。有没有可能一次扫描完lisp文本之后就确定全部的函数定义呢？给定两个附加条件，一是所有的函数定义必须在他的调用的同一级或外层（注意这里指的是定义这个函数的外层，而不是调用这个函数的外层），二是函数定义必须在函数调用的前面。这样就可以逐级求值而避免递归了（相当于首递归）。当然这里避免的仅仅是（相当于）编译期的递归，在（相当于）运行期的递归仍然是避免不了的（也不可能避免）。当然对于lisp而言，编译和运行是交叉进行的，也没法分得这么仔细啦。（所以才说是解释型语言嘛。。汗）当然话说回来，将lisp先编译成机器码再运行也是可能的。只是编译时间会比较长而已，而且对于变量类型可能要做一些处理。（最简单的想法是用链表，不管是树也好，字符串也好，数字也好，都可以用链式结构存，以适应lisp的list结构。）

好吧，先做这些记录，下次有了感想再写了。

呼，因为结束实习，搬家，赶毕设，一下子好久没有写博了呢。。今天终于补了一篇。。证明我这段时间也没有荒废时间啊。。以后还是要经常写博客自勉啊。。回头看了一下大半夜的逻辑有点混乱估计有写错的地方。。不过天色晚了没心情挑错了，改天再回来改吧。。