The architecture of w-ai.org – 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 w-ai.org – Introduction

I’ve introduced WAI (http://w-ai.org) 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 Socket.io, 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

最后两周的题目不多,所以写在一起吧。KD-Tree是一个对我来说比较不熟悉的东西,视频里没有讲一些关键复杂度的证明,但是这个东西给我的感觉不美……不过对于那样的问题也没有什么太好的办法了吧。还讲了一个线段组成的BST,不过功能上和ACMer常用的线段树相比真是弱爆了啊。

Inverview Questions:

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

答:首先遍历文档建立一个索引:对每个词,记录一个表示它在文档里出现的位置的列表。然后维护M个指针指向M个检索词对应的列表。向后移动相应指针得到第一个满足顺序要求的解(即M个指针指向的位置值是递增的且尽可能小),这样就找到了一个片段。继续向后移动指针找下一解,直至扫描完所有列表。建索引时如果借助hash表,复杂度就是O(N)。扫描的总复杂度也是O(N)。

Interview Questions: Hash Tables

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

答:枚举所有数对的和,用hash表判断是否出现重复即可。“下标不同”这个要求可能需要一点处理,不过我懒得想细节了……囧

(完)

Coursera: Algorithms, Part I: Week 4

前段时间事情较多,所以进度跟不上了,我会尽快把剩下的补完。

第四周的内容是优先队列和二叉搜索树。只记得最后提到,如果用普通的BST(非平衡的)进行随机的插入和删除,期望复杂度会是O(sqrt(N)),这个我之前倒是不知道,只知道故意构造的最坏情况会变成O(N)。已经不记得有什么其它的有趣的点了,直接看题目吧。

Interview Questions: Priority Queue

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

答:实际上我见过一道类似的ACM题。我们假定在集合中有偶数个元素时,中位数是指较小的那个中间数。用两个堆,一个大顶堆包含集合里较小的(N+1)/2个数,另一个小顶堆包含集合里较大的另一半数。查询中位数时,直接看大顶堆的堆顶元素即可。插入元素时,先将其与两个堆顶元素比较,以决定插入哪个堆。如果插入之后两堆的元素个数之差超过了1,就把多的那个堆的堆顶元素插入到另一堆里。删除元素时,将中位数删掉之后,同样调整两个堆的元素个数。

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

答:因为堆用连续的一段数组表示,随机访问只需要随机得到一个[0,N-1]之间的数组下标即可。随机删除元素和删除堆顶元素其实是一样的,把最后一个元素放到被删除的元素的位置,然后把它向下沉直到合适为止。

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);  
}