## 介绍

2048这游戏已经被玩坏了，有人把它和Flappy Bird杂交，玩不过不能忍，于是写了个AI玩之。

## 游戏源码修改

• 使用game.jump()跳跃
• bird的状态：

game.birdpos 顶端的y坐标，$[0, 1]$之间，0为顶端
game.birdspd y方向速度，向下为正
• 在任意时刻，只有4个block分别称为a, b, cdab,cd成组，有相同的水平坐标，两组block之间一直保持2个tile的距离。每组block只有3种可能状态：全在上、全在下以及一上一下，因此block的状态由两个0~2之间的数字game.ab, game.cd确定。

## Q-Learning

Q-Learning是一种强化学习算法，能用于寻找Markov决策过程(MDP, Markov decision process)的最优解。 MDP问题模型由一个agent，状态$S$以及每个状态对应动作(action)集合$A$构成。Agent通过完成一个动作，从一个状态$S$跳转到另一个状态$S'$，获得一定的奖励。Agent的目标就是使奖励最大化，通过学习在每个状态下最优的动作，达到这个目的。

$$Q: S \times A \rightarrow \mathbb{R}$$

$$Q_{t+1}(s_t, a_t) = Q_{t}(s_t, a_t) + \alpha_{t}(s_t, a_t) \times [ R_{t+1} + \gamma \max Q_{t}(s_{t+1}, a) - Q_{t}(s_t, a_t) ]$$

• $Q_{t+1}(s_t, a_t)$: 新的$Q$值
• $Q_{t}(s_t, a_t)$: 上一时刻$Q$值
• $R_{t+1}$: 在$s_t$时执行$a_t$后获得的奖励
• $\alpha \in [0, 1]$: learning rate
• $\gamma$: 折扣率

## 算法设计

• 状态：

• $\Delta y$: bird到能安全通过当前block最高点的垂直距离
• $\Delta x$: bird到下一个block的水平方向距离
• 动作：

• jump: 跳跃
• idle: 不动作
• 奖励：

• 死亡：-100
• 存活：1
• $Q$的初始化

• 对所有$\Delta y < y_{min}$的$s$，初始化jump的reward为-100。即在上端时禁止跳跃
• 对所有$\Delta y > n * BirdHeight$的$s$，初始化idle的reward为-5n接近1。即离最高点的距离小于bird自己高度的时候，倾向于跳跃。注意这里的reward值较小，是因为在某些组合下（如当前block在下，下一个block在上），跳跃会挂掉，值如果过大，$Q$值无法及时对惩罚做出反馈。

• 不定状态时的随机参数

jumpaction的reward相等时，无法通过$Q$做出决策，这个时候需要随机决定采取何种行为。

## 介绍

• 通过原URL的访客不会死链，会自动跳转到新URL
• 搜索引擎能自动重新索引，不会降低页面排名

## 使用

• 创建一个hexo博客文件夹的副本
• 在副本文件夹中安装这个主题：
• 修改副本站点的_config.yml文件，使用主题：
• 修改副本站点的_config.yml文件，添加如下行指定新域名：
• 修改副本站点的部署配置，部署到blog.catx.me(老域名)
• 修改原站点的部署配置，部署到catx.me(新域名)

## 源代码

hexo-theme-redirect

## 介绍

Sequence Diagram

Robustness Diagram

## 初始化

_config.yml文件中添加：

## 语法

diagram_type可以取的值为：

• sequence
• robustness

## 示例

Jumly的表达式规则详见：Jumly Reference Manual

## 编译vmulti

1. 安装WDK
2. 运行以管理员权限WDK build environment
3. 进入vmulti工程文件夹，运行
1. 把编译生成的vmulti.sysmulti.infhidkmdf.sys文件放到同一个文件夹
2. 把WDK中的WdfCoInstaller01009.dll, devcon.exe也放到这个文件夹

## 驱动签名

Windows x64系统上无法安装无签名的驱动，需要进行self sign。所有操作需要在管理员权限的WDK build environment中执行。

### 签名

• *.sys文件
• *.inf中引用的*.cat文件

vmulti需要签名的文件有vmulti.sys、hidkmdf.sys和kmdfsamples.cat，运行：

## 测试

vmulti工程中包含了一个测试程序testvmulti.exe，用于测试驱动功能：

## 介绍

Hexo不支持数学公式，网上可以找到很多人肉修改theme使其支持用MathJax渲染公式的方法，主要分为两个步骤：

• 在文章中用inline math插入公式

• 需要人肉进行的工作太多
• 遇到特殊符号需要人肉escape，否则会被markdown parser吃掉

• 自动部署MathJax
• 添加MathJax Tag

## 初始化

_config.yml文件中添加：

## 使用

MathJax Inline:

Simple inline $a = b + c$.

MathJax Block:

$$\frac{\partial u}{\partial t} = h^2 \left( \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} + \frac{\partial^2 u}{\partial z^2}\right)$$

Tag inline:

This equation $\cos 2\theta = \cos^2 \theta - \sin^2 \theta = 2 \cos^2 \theta - 1$ is inline.

Tag Block:

\begin{aligned} \dot{x} & = \sigma(y-x) \\ \dot{y} & = \rho x - y - xz \\ \dot{z} & = -\beta z + xy \end{aligned}

## 源代码

GitHub

GitHub Pages的博客框架有很多选择，最终决定用基于Node.Js的Hexo，速度比官方的Jekyll系框架要快，并且不用折腾ruby。在使用hexo-migrator-wordpress迁移文章后，发现所有图片依然是保持外链。翻了下Hexo的文档，自己写了个migrator迁移所有外链图片，流程很简单：

• 打开所有.md文件
• 扫描并解析Markdown插入图片的tag
• 下载所有非本站的图片（包括本地图片）到images目录
• 更新所有引用的url

## 问题描述

C#中经常会遇到通过单一入口动态调用对象或服务的情况，形如：

## 实现要点

• .Net CLR是基于栈的虚拟机
• .Net CLR（在生成C#类时）是强类型的
• 参数顺序入栈
• 非static method的第一个参数总是this指针

1. 有参数的constructor

2. Array的初始化 由于Invoke的长相，决定了这个生成器中需要大量的生成object[]对象，并把参数装进去。 创建一个local variable，首先需要declare：

• ldloc.?将array入栈
• ldci4?将当前元素的index入栈
• 将需要赋给元素的值入栈（本例中为参数用ldarg_s，注意参数0为this指针）
• 如果是value type需要box
• stelem.ref指令完成赋值

## 源代码及使用方法

GitHub

In part 1 we discussed the design goals of Sarcasm and devised a grammar specification that covers most of Irony's features.

Continuing from commit 15c9e6, in which I implemented the grammar specs by hand with Irony, we will discuss the following topics:

• Construction of abstract syntax tree
• Generator workflow
• MarkDown generator
• Having some fun with visualization

## AST Overview

After grammar class is implemented, the first thing you are going to do is to create a parser instance:

With the Parser instance, we can parse source code by simply:

If something is wrong with the grammar or source code, parseRoot and astRoot will be null. For now I will not go into error handling.

Two kinds of trees are generated when Irony parses the source code: parsing tree and optional abstract syntax tree. To create an AST, you must do the following:

1. Set language flag in grammar class's constructor

2. Create a bunch of AST node class deriving from Irony.Interpreter.Ast (also remember to add reference to assembly Irony.Interpreter.dll).

3. Assign AST node class to each Terminal/NonTerminal instances.

4. Override AST node's Init method to handle initialization.

That's almost all you need to know about how to construct an AST. However, if you mess it up, things can get ugly since the debug information is extremely not helpful. The most common exception on can get is:

System.NullReferenceException: Object reference not set to an instance of an object. at Irony.Ast.AstBuilder.BuildAst(ParseTreeNode parseNode) in f:\Dev\Tool\Irony_2013_12_12\Irony\Ast\AstBuilder.cs:line 97 This will not help you at all. But I will tell you that this always has to do with forgetting to set AST node type to one of your Terminals/Non-Terminals.

Here are some tips I learned in the hard way (the only way mostly, since Irony's documentation is poor):

• Assign AST node type to all Terminals/NonTerminals, including any intermediate/temporary ones.
• Except the ones marked as transient. They will not be created at all.
• CommentTerminals will NOT be mapped to AST at all. You will get the above error regardless the AST node type is set or not.

## Generator Workflow

AST marks the watershed between compiler's front end and back end. Although there're still some work (e.g. type validation and semantic analysis) left to be done, we can already generate something with this AST now. The most commonly used method here is the visitor pattern:

1. Declare a interface for Visitor, one overload for each AST node

2. Add virtual/abstract method to AST base class and implement in all derived class

3. Then we can create a generator by implement specific ISarcasmVisitor for different workflow, not only for target code generation but also outlining, semantic analysis.

## MarkDown Generation

MarkDown generation for Sarcasm is very straight forward, since the syntax is in MarkDown. All I need to do is remove comment delimiters, add correct amount of line endings, format grammar rule into block and escape some special characters.

Again I won't bother with the details here. Just see the code for yourself.

## Something Fun with Visualization

The original plan was to start generate C# parser class from here. Then I found an interesting project arbor.js (especially its halfviz demo) and decided to do something fun with it. The idea is to make a better tool for debug. What debug information is better than a visualized one?

The halfviz demo converts a simple language called HalfTone to a node network. With the generator framework in place, it took me less than half an hour to generate node representation from Sarcasm grammar source file. This can be used to visualize references between terminals and non-terminals:

You can play with it live here. It looks more confusing in this form, for now. But with some interaction (filtering, folding, highlighting for example), it can help develops quickly navigate though the grammar. Here's another concept of how to visualize grammar related errors in this form (click to enlarge):

Imagine view build errors in Visual Studio with this graph and navigate to the line that is responsible by click on the node. I definitely will try to create something like that later when I begin to make tool chain for Sarcasm.

## Introduction

This is not a tutorial on how to use Irony.net. When I am done with this series of articles, hopefully we will never need to deal with Irony directly ever again.

In case you didn't know what Irony is, here is the introduction on its official site:

Irony is a development kit for implementing languages on .NET platform. Unlike most existing yacc/lex-style solutions Irony does not employ any scanner or parser code generation from grammar specifications written in a specialized meta-language. In Irony the target language grammar is coded directly in c# using operator overloading to express grammar constructs. Irony's scanner and parser modules use the grammar encoded as c# class to control the parsing process.

Looks fantastic. However, after I tried for days to implement CoffeeScript grammar with it, I encountered some issues:

• While constructing grammar with C# directly sounds cool, the syntax is just not as clean and efficient as a special design DSL would be.
• There are absolutely no compile-time checking on grammar. You have to compile it into dll first, then load it with Irony.GrammarExplorer.
• It is extremely hard, if not impossible, to track any grammar errors back to source code.
• On top of that, debug information on Shift-Reduce and Reduce-Reduce conflict is almost unreadable for a complex grammar.

It's a nice concept with poor tooling, which makes it scale poorly as the complexity of grammar grows. After some painstaking efforts to make my CoffeeScript parser to work, I finally begin to do something about it. I decide to create:

Sarcasm, an EBNF-like DSL that generates Irony.

The design goals are to:

• Implement a DSL that allow developers to define grammar in a more clean and efficient syntax that looks very much like EBNF notation.
• Generate Irony grammar implementation (in C#) and a nice formatted grammar specification document (in MarkDown)
• Enable compile-time error checking and grammar validation
• Trace any errors back to the source code
• Improve the readability of debug information for grammar conflicts
• Provide necessary Visual Studio languages services, templates and tools

## Sarcasm Workflow

1. Developer writes grammar specification file (.sarc)
2. Compiler checks for syntax error and generates both Irony grammar class (in C#) and spec docs (in MarkDown)
3. VS continues build process
4. If build failed, Sarcasm tools filters though all error messages, and map related errors back to specific tokens in .sarc file.
5. If build succeeded,Sarcasm toolsloads the assembly and validates grammar.
6. Sarcasm toolstranslates any grammar conflicts, errors into a readable format and trace back to specific rule in .sarc file. The entire workflow should be seamlessly integrated with Visual Studio.

## Sarcasm Grammar

In a nutshell, the Sarcasm grammar is a hybrid of MakeDown and modified EBNF notation. Here's a quick snippet:

As you can see, the grammar consists of: