Author Archives: roba

The architecture of – Protocol

I’ll describe how to run a match, and how to implement a judge (and a player) if you want to add a new game to WAI.

Running a match is very simple. Each judge (an executable complied from *_judge.cpp) and players (executables complied from users’ submissions) are isolated. To run a game, just run match.exe with three parameters:

./match.exe judge player1 player2

where judge, player1, player2 are three executable file.

When match.exe starts, three processes will be forked, i.e., one judge process and two player processes. (Actually it’s six because of the sandbox, but we will ignore this for now.) There processes interact with the master process through stdin and stdout.

Let’s take the othello for example. At first, You should refer the protocol spec and sample player code here. Initially, the judge should tell one player to move firstly, and tell the other player to move secondly. He should write two messages to stdout, ”>1: first” and “>2: second”. The prefix “>x: ” indicates sending the following message to player x. (The two players are numbered 1 and 2.) So the player 1’s first scanf(“%s”, buf) will receive string “first”, while the player 2 will receive “second”. Another command for the judge is “<x“, indicating that the judge is expecting player x‘s response, and the judge’s following read from his stdin will get the string which outputted by player x. You can refer the code of othello judge.

There is another common approach for this kind of ‘interactive’ program – providing a public library interface (for example, a header file), and requiring user’s program to call the library functions for communication. However, it make user’s local debugging more difficult, because the users have to link their codes with the given library to run. And another problem is how to give out the library. We can’t just put the binary file, because the ABI may be not compatible for different C/C++ compiler, let alone for different languages in future. I believe communicating through stdin/out is simple and robust, not only for the user, but also for the platform itself.

In next post, I’ll describe the magical match.exe in detail.

The architecture of – Introduction

I’ve introduced WAI ( in my previous post. You can find the source code at github. To help someone who may be interested in contribution to this project, I’ll write a series of posts about the architecture of the system.

There are four main components of WAI:

1) Sandbox and other stuff which tightly depends on specified OS

This component is similar with the judge service of traditional ACM-ICPC online judge systems. The main function is providing permission control, timing and the communication between user’s AI process and outside world.

Because it is full of system calls (ptrace() and pipe(), for example), this part is implemented in C++.

2) Web server (based on Node.js)

I have to admit that Node.js may not be the best choice for this project, for WAI is CPU-tensive, which usually can’t take advantage of Node’s asynchronous behavior. In fact, I wrote the web server in Python in the first place, but later I found I need a bi-way real-time communication between client-side and server-side (for the HvC feature), and the only simple method I can find is, which is based on Node. Another reason of choosing Node is, I want to learn it, and it sounds cool :)

There is also another component in Node – the scheduling module, to decide which two AI should fight next.

3) Client side code (JavaScript / HTML5)

The UI is based on Twitter’s Bootstrap. Obviously, I’m not an expert at UI design, and the current UI is almost the best I can make. I’ll be very glad if you can help improving it.

And the most complicated code in this part is the logic of interaction with users for each specific game. For example, drawing the chess board in canvas (yes, HTML5), responding user’s mouse click, showing computer AI’s moving, and so forth. Some games are more complicated to show (for example, TankCraft) than others.

4) Judges for each game

Once a new game is added, the corresponding judge should be provided, which will receive the AI’s moving and determine who is the winner. There is a simple protocol based on std i/o, and the judges are designed to be interchangeable easily.

I’ll describe the details of each component in the future posts. Stay tuned~

Some updates and my first English post

I’ve been in US for about two months, and here comes a serious problem: My English really SUCKS.

I’ve never come to US before, even never think about studying or working outside China before I got Facebook’s offer. So I have little experience in English. We do study English in China, but just for standardized test, which contains mostly multiple choice problems. So, the situation is, I can read (with the help of dictionary) and write (in spite of tons of spelling/grammar error), but I have much difficulty in listening and speaking.

For improving my written English, I’ll post blogs in English in future. The English posts will basically about technique, because I think it’s even more difficult to express the `kuso’ of daily-life in English instead of Chinese.

Feel free to correct me if you find any typo or other errors in my article. I’ll appreciate your help.Thanks. :)

Coursera: Algorithms, Part I: Week 5 & 6


Inverview Questions:

2. 文档中依次有N个词,现在有一个依次包含M个词的检索串,要求在文档中找到一个包含最少词数的连续片段,使得检索串里的M个词依序出现在这个片段中(当然,可以不连续)。


Interview Questions: Hash Tables

1. 4-SUM: 给定一个长为N的数组a,要求找出不同的四个数满足a[i]+a[j]=a[k]+a[l]。要求时间复杂度是O(N^2)



Coursera: Algorithms, Part I: Week 4



Interview Questions: Priority Queue

1. 设计一个表示动态集合的数据结构,使得插入元素是对数时间,查询中位数是常数时间,删除中位数是对数时间。


2. 设计一个优先队列,支持两种额外操作:随机访问队列里一个元素,随机删除队列里一个元素。


3. 找出所有的四元组(a,b,c,d),满足a^3+b^3=c^3+d^3 (a,b,c,d <= N)。要求O(N^2*logN)的时间,O(N)的空间。

答:先看另外一道很有趣的问题:给定两个排好序的数组A和B,两数组长度都为N,我们从两个数组各取一个元素求和,这样就得到了N^2个和,要求把这N^2个和按序输出,空间不能超过O(N)。方法是建立一个堆,开始时堆中的元素A[1]+B[1], A[1]+B[2], …, A[1]+B[N],每次从堆中取最小元素输出,然后看看这个元素是怎么来的,假设是A[i]+B[j],就把A[i+1]+B[j]插入堆。回到本问题,现在只是A,B数组都是1^3, 2^3, … N^3而已,用同样算法,如果发现相邻两次输出的值相同,说明找到了一组解。空间显然是O(N),因为共输出N^2个元素,每次堆操作是O(logN),所以时间是O(N^2*logN)

Interview Questions: Elementary Symbol Table

2. 判断一个树是否是BST。要求使用O(h)的空间,h是树的高度。


int check(Node *p, int low, int high) {
  if (low > high) return 0;
  if (p == NULL) return 1;
  return check(p->left, low, p->value) && check(p->right, p->value, high);