从零开始的代码评测系统设计与实践(四) —— 特殊评测

0x00 背景

传统的评测模式下，判题机按照固定的顺序执行：运行被测程序，获取运行结果，比对结果数据。由于是严格比较，结果数据和答案属于有任意一个字节（除常用格式字符外）不匹配，都将被判定为WA。

有些时候，这种方式太过于苛刻。在涉及到浮点数运算的题目，如计算圆的面积时，我们不得不面对计算结果的精度误差，这将导致原本正确的程序，被判定为WA，显然这不符合我们的逾期。

在特殊评测功能还没能设计开发出来之前，我们通常的解决办法是固定使用一种数据类型出题，比如要求选手使用double来存储浮点数，这样可以确保最终打印的小数精度和我们设定的答案一致。

我们知道，数据检查工具是判题机的一部分，那么是否能让判题机支持调用出题者编写的数据检查工具呢？

0x01 特殊评测

特殊评测中，判题机在数据检查阶段，将控制权交给出题者预定好的数据检查工具。出题者需要按照判题机的文档编写对应的程序，从运行参数列表里接收判题机传过来的输入数据、用户输出数据、答案数据和日志文件等参数，并进行读写、判定，必要时还可以记录日志。所有工作完成后，返回特定的退出代码。判题机接收到将以退出代码作为判题结果。

当然，作为判题机，也要监控这个检查工具的执行情况。如果长时间没有反馈，或者返回了错误的信息，需要及时进行错误标记，并通知出题者等。特殊评测的实现比较简单，这里不再赘述了，需要深入了解，请直接阅读判题机源码即可。

0x02 交互判题

交互式判题是一种新颖的特殊评测形式，它支持特判程序和选手的程序进行互动。

例如，我们可以出一题猜数字游戏：特判程序随机在[0, 1000]内生成一个数，要求被测程序在10次询问内，告知特判程序这个数是什么。每次询问，判题机会告诉你是“>”、“<”还是“=”。如果10次内没有猜到这个数，那么特判程序会直接返回WA，表示被测程序错误了。

上述问题相信大家都知道怎么解答吧。从技术的角度来看，在这个“猜数字”的过程中，特判程序和被测程序之间建立了一个“数据通道”（标准输入输出流），特判程序只要生成一个数，然后通过scanf获取被测程序发来的数，比对后返回结果。比对成功则返回AC，超过10次错误，直接返回WA。**而判题机，只需要作为一个旁观者，无须参与实际的数据判定。**但如果特判程序结束了，无论被测程序是否执行完毕，都应该直接结束掉。

// 特判程序

#include <stdio.h>
#define AC 0
#define WA 4

int main() {
    int ans = rand() % 1000;
    int ques = 0;
    int err = 0;
    while(~scanf("%d", &ques) && err < 10) {
        if (ques < ans ) {
            printf("<\n");
        } else if (ques > ans ) {
            printf(">\n");
        } else {
            printf("=\n");
            return AC;
        }
    }
    return WA;
}

// 选手程序

#include <stdio.h>
int main() {
    int left = 0, right = 1000, half = (left + right) / 2;
    char ans;
    printf("%d", half);
    fflush(stdout);
    while(~scanf("%c%*c", &ans)) {
        if (ans == '<') {
            right = half;
        } else if (ans == '>') {
            left = half;
        } else {
            return half;
        }
        half = (left + right) / 2;
        printf("%d", half);
        fflush(stdout);
    }
}

下面来讲这个比较有意思的功能是如何实现的。

0x03 数据重定向

要想实现交互判题功能，我们需要对特判程序和被测程序的输入输出流进行重定向。在Linux中，进程之间进行通讯(IPC)的方式常见的有两种：一种是使用pipe管道，另外一种是sockerpair。前者是半双工的，即只能一个发送一个接收；后者是全双工的，可以同时进行发送和接收工作。我们目前只讨论第一种，即pipe方式。

// int pipe(int pipefd[2]); 

int judger[2], program[2];
pipe(judger);   // 特判程序用于读取的管道
pipe(program);  // 被测程序用于读取的管道

pipe函数将会把参数中列表的值分别设置为对应的文件描述符，其中fd[0]为读取，fd[1]为写入。这个很关键，它决定了数据的流向，即fd[1] —> fd[0]。然后，我们就可以拿出之前的dup2函数，将对应的文件描述符指向对应的输入输出流：

// 被测程序
dup2(program[0], STDIN_FILENO);
dup2(judger[1], STDOUT_FILENO);
// 特判程序
dup2(fdjudge[0], STDIN_FILENO);
dup2(program[1], STDOUT_FILENO);

// 数据流向：
// 被测程序 --judger--> 特判程序
// 被测程序 <--program-- 特判程序

这样，我们就完成了交互评测中最核心的逻辑。当然，除了这些核心逻辑，判题机依然需要监控程序的运行状况。因为特判程序和被测程序都是不稳定的，并不知道谁会出错，也难免存在卡住的情况，都需要进行及时的处理。

0x04 更佳的实践

通常情况下，编写特殊评测、交互评测检查器，对于出题者来说无疑是一项并不容易的工作，出题者需要全方位考虑到问题可能发生的各种情况、数据是否符合题目要求等，还得保证接收到一些奇怪的数据时尽量不崩溃。

在我个人的认知里，交互评测功能应该是出自于著名的ACM竞赛网站CodeForces，而该网站推出了一款很强大的评测辅助工具：Testlib。该工具最早是Pascal语言开发的，后用C++重写。它引入了Generator、Validator、Interactor和Checker四个概念，为了便于理解，我将它们分别描述为：输入数据生成器、输入数据校验器、交互评测检查器、普通特判检查器。

它们可以让出题人更加专注于出题，不会被繁琐的校验工作难倒。这里只是简单的描述一下这个工具，如果你需要开发一套完整的判题系统，我非常推荐你尝试支持这套工具的使用，提前代表出题者感谢你的支持。

支持这套工具并不难，你只需要支持出题者上传相关的程序代码，将代码和testlib.h一同编译并运行即可。对于判题机内核，只需要关心interactor和checker的运行和输出。对于OJ网站（出题），能调用shell执行Generator和Validator即可。具体实现了哪些功能，你可以打开cf的polygon网站了解一下。

0x05 畅想未来

判题这块核心的内容讲的差不多了。总的来说，原理并不复杂，往往开发实现的时候会遇到很多的坑，这是必经的过程，不必惊慌。

在人工智能技术不断突破发展的今天，我们完全可以利用这些技术打造一个更加智能的判题程序。这是我设计和开发WeJudge系统的时候，听过最多的建议。因为WeJudge本身面向的群体是学生、教师团体，而不是ACM的参赛者，学生最需要的是学习代码实现的思路、代码风格，注重过程，而不是仅仅局限在精确无误的数据上。严苛的评测机制本身会对这学生带来心理上的压力，也对教师造成的许多不便，毕竟很多时候出现的莫名其妙的问题，老师也难以向学生解答。

总之，在原有的基础上进行突破和超越，是每一位开发者所追求的共同目标。

非常欢迎有想法的你参与到开源判题机的建设上来。

参考和引用：

Testlib中文简介：https://oi-wiki.org/tools/testlib/
Testlib英文博客：https://codeforces.com/testlib
致谢项目：https://github.com/dojiong/Lo-runner
我开发的判题内核deer-executor：https://github.com/LanceLRQ/deer-executor