我的黑白棋实验报告

注:本文是上学期是计算概论A大作业的实验报告,偷懒直接贴过来了XD

直接跳到AI部分

计算概论大作业:黑白棋

实验报告

张孝帅 1500010716
数学科学学院 2016.01.01


概况

  • 本文是一篇实验报告,主要从主程序设计、AI设计两方面展开,介绍了两个月来我对黑白棋程序的设计和思考,其中以AI算法设计的介绍为主。

  • 经过近两个月的设计、debug及改进,JetOthello主程序已经实现了人人对战、人机对战、AI间对战等基本游戏模式,有AI参与的对战中,可以自由调整AI难度。同时实现了存读盘、悔棋、中途停止、多语言界面、丑到哭的主题更换、(可选)图形界面1等基本功能,远超过了大作业题目要求。

  • 程序的AI部分(Achilles)已经达到相当的水准,其迭代加深版本目前在Botzone天梯榜上稳居第一,其动态深度控制版目前排名第三(即将第二),其随机化版本打赢了许多声称比随机算法要强的AI。与国内最顶尖的黑白棋程序“伤心黑白棋”的对局实验显示,Achilles能够轻松战胜大师级别(5)及以下的“伤心黑白棋”AI,在最高难度特技大师(6)模式下以4子之差惜败,看来应该把它的下法写进我的局面库

  • 程序的源文件实现了跨平台兼容性,在Windows 10、8.1、8、7(编译环境为Visual Studio 2015)及Ubuntu 14.04(编译器为build-essentials中的g++ 4.9.2)、OS X 10.10(Xcode7.2)下均能正常编译通过(特定平台下可能需要额外的OpenGL库支持)。


一、源文件及其结构:

本着单个文件简单、方便管理和易于维护的原则,该黑白棋程序按功能被拆分成了多个.cpp源文件及.h头文件,具体来说,分为:

1. base.h:

主要包含一些全局的包含文件、全局常数和宏的定义、freeglut库的关联、跨平台命令支持、版本号字段、名字空间的声明等。

例如:

#define PAUSE cin.clear();cin.sync();cin.get();cin.get()

是跨平台PAUSE的实现。

#include <windows.h>
#define CLS system("cls")
#define SLP(X) Sleep(X)

#include <unistd.h>
#define CLS system("clear")
#define SLP(X) usleep(1000 * X)

分别是Windows及Linux(OS X)下清屏和等待函数的实现。

ostream& endll(ostream& strm);  

偷懒函数一次换两行函数的声明,放在base.h中以便使用。

2. elements.h

包含玩家类型、棋子状态、坐标、语言、棋盘、游戏、棋子物理模型等枚举和类的声明。

3. Achilles.h、Achilles.cpp:

主要包含AI(Achilles)及其依赖函数的实现。

4. init.h、init.cpp:

主要包含主菜单、难度设定、辅助模式设定、语言设定等一般设置项目。

5. board.h、board.cpp:

主要包含棋盘Board类的实现。

6. IO.h、IO.cpp:

主要包含游戏输入输出(鼠标和键盘)函数的实现。 (实际上控制台输出被写入了Board类,GUI输出有单独的实现,该文件中几乎只有输入控制相关的内容)

7. multilang.cpp

多语言的实现,各语言字符串的存储。 (本意是写入外置文件中,使用时再读取,由于时间有限没有做)

8. error.cpp

程序遇到致命错误或者无法处理的情况时调用fatalError退出。 (太naïve了不会用try…catch…throw…exception这么高端的东西233) 实现也很naïve:

void fatalError(unsigned ErrorCode)  
{
    switch (ErrorCode)
    {
        case 1:
            CLS;
            cerr << "Unknown Fatal Error Detected, "
                     "Program Will Now Terminate." << endl;
            PAUSE;
            exit(1);
        case 2:
            cerr << "Unsupported Platform, "
                    " Program Will Now Terminate." << endl;
            PAUSE;
            exit(2);
        ……
        default:
            exit(233);
    }
}

本来可以把fatalError写的更详细的,如将提示具体到棋盘数据有误、关键数据读取出错等,并给出可能的解决方案,但实在是精力有限,大概要放到寒假去搞了。 目前在Board类、AI中均可能用到此函数。

9. model.h、display.h、model.cpp、display.cpp

是GUI部分的模型及实现,主要通过调用freeglut库函数实现图形化,该部分主要由陈子恒完成,我只是移植了他的工作,进行了一些简化,删除了很逗逼装逼的掀桌功能,并做了很小的改动,使接口匹配。此部分应当归功于他。(开源的胜利)

10. main.h、main.cpp

程序入口函数所在,包含了主要游戏循环、自动(AIvAI)游戏循环、游戏和GUI线程创建、结束判定函数等。

二、数据类型、数据结构设计:

游戏的主要数据类型、结构都被定义在elements.h中,主要有:

① 枚举量:

enum playerType { Human, AI };  
enum Status { White, Black, Empty, Valid };  
enum language { en_us, zh_cn, zh_tw, zh_wy, jp, fr, es };  
enum gameStatus { Idle, Playing, End, Pause };  

分别是玩家类型、棋盘位置状态、游戏语言、游戏主程序状态(供GUI部分使用)的枚举类定义。 要注意其中的Status枚举能通过类型转换直接得到bool型或int型的黑白方标志:true1为黑方,false0为白方,这为程序的许多地方带来了方便。

② 基本的结构体:

struct Coord  
{
    short x;
    short y;
};

Coord是坐标结构的定义,不用pair是因为firstsecond太长2333,不知道直接用pair<short, short>是否会效率更高。

struct Cell  
{
    Status status;
    bool validDir[8];
};

Cell是棋盘上某一个位置的结构定义,包括一个位置的当前状态,和一个可行方向数组(只在fast系列方法中用到,将在Board类及AI实现中提到)。注意到与坐标的明显区别是:它是一个棋盘Board类的内部结构,落在某一棋盘上才有意义。

③ langStrings类:

用于实现多语言,由一系列string字符串和

void setLangStrings(language langFlag);

void printMenu();  
……
void help();

void EN_US();  
void ZH_CN();  
……
void JP();  

等一系列函数构成,其中setLangStrings接受一个language枚举量,并调用相关语言函数(如EN_US())给类成员的一系列字符串赋值,主程序中通过生成一个该类对象并调用其中的字符串进行输出来实现多语言。

④ Board类:

本着面向对象的自然设计思想,同时为了方便程序和AI的函数安全地操作棋盘,棋盘被设计成了一个类,其大部分数据元素都设置成private以防止误操作,所有不需要改变棋盘的方法均用const修饰,最大程度保证了棋盘数据的安全性。下面是声明部分的具体代码,其中一些方法的实现将在之后单独介绍:

class Board  
{
private:  
    bool sideFlag;
    //标记当前下子的用户,true为黑方,false为白方。

    bool passFlag[2];
    //passFlag[Black] = true表明黑方上回合pass了,同理…
    //这个Flag用于判断游戏是否结束。

    short statusCount[4];
    //statusCount[Status] 接收Status枚举得到棋盘上特定状态的位置的个数
    //例如statusCount[Empty]存储棋盘上为空的位置数目(包括Valid位置)。

    short validCountFor[2];
    //当前棋盘黑白两方分别的可行位置计数
    //(和statusCount有存储冗余,但不会增加算法的复杂度)
    //要注意的是在黑方回合,白方的可行计数没有实际意义,只用于AI分析。

    Cell cell[10][10];
    //用于记录棋盘每个位置的状态等关键数据。

    bitset<64> frontline;
    //棋局边界图,在fast系列方法中用到。

    bitset<64> sideFrontline[2];
    //黑白两方各自的边界图,在AI中用到。

    vector<Coord> validCoord;
    //setValid方法调用后,用于存储所有棋盘当前可行位置的容器。
    vector<Coord> movesRecord;
    //棋局的着子记录,PASS时推入特定坐标({-1,-1})。

public:  
int chara;  
    //当前棋盘的特征值(hash),用于匹配局面表

public:  
    Board();
    //构造函数

    void operator =(const Board&);
    //复制棋盘运算符,由于只用在AI中,为提高效率进行了简化
    //(不复制movesRecord等无关元素)

    const bool operator ==(const Status)const;
    //判断某个棋盘的状态是否是给定的Status(White, Black)
    //其实没用过
    const bool operator !=(const Status)const;
    //和上面那个相反

    const bool operator ~()const;
    //返回棋盘当前sideFlag
    //实在找不到其他合适的运算符了TAT
    const bool operator !()const;
    //和上面那个相反

    const Coord operator ^(size_t) const;
    //board^i返回board.validCoord[i]

    const Cell* operator [](const int)const;
    //board[i][j]返回board.cell[i][j]
    const Cell operator [] (const Coord&)const;
    //board[Coord C]返回board.cell[C.x][C.y]
    const short operator ()(const Status)const;
    //board(Status)返回board.statusCount[Status]
    const short operator ()(const bool)const;
    //同上,只是接收bool类型

    void init();
    //初始化游戏棋盘(设置4个初始棋子,设置sideFlag为Black等)

    void clear();
    //清空棋盘

    void flipSide();
    //翻转棋盘的sideFlag(黑<->白)
    void count();
    //更新statusCount[4](除了Valid在setValid()中更新)

    void print()const;
    //在命令行窗口绘制当前棋盘

    void recordPrint()const;
    //输出movesRecord中的棋局记录(结束时调用)

    void printFrontline() const;
    //打印allFrontline存储的棋局边界图(方便debug)

    const int charaCalc();
    //计算并更新棋盘chara特征值(哈希)

    const short validCount() const;
    //返回validCountFor[sideFlag],即当前方可行步数数目

    const short turnCount() const;
    //返回movesRecord.size() / 2,相当于Botzone上的turnID参数

    double allEvalFor(const bool)const;
    //每个坐标位置有给定的coordValue,该函数返回这些value的总和(用于估值函数)

    bool save(string saveName = "Othello")const;
    //存盘函数
    bool load(string loadName = "Othello", int UndoSteps = 0);
    //读入棋盘并撤销UndoSteps步
    void undo(int steps);
    //悔棋函数实现(此处有偷懒)↑

    inline bool end()const
    {return (!statusCount[Empty] || !statusCount[Black] || !statusCount[White] || (passFlag[Black] && passFlag[White]));}
    //判断棋局是否结束

    inline int isWin(bool side)const
    {return (end() && (statusCount[side] > statusCount[!side])) ? statusCount[side] - statusCount[!side] : 0;}
    //判断side是否获胜,获胜则返回胜子个数

    inline bool inRange(int p, int q)const { return p >= 1 && p <= 8 && q >= 1 && q <= 8; }
    inline bool inRange(Coord C)const { return C.x >= 1 && C.x <= 8 && C.y >= 1 && C.y <= 8; }
    //判断坐标是否在正常棋盘范围内

    inline short getX(int a)const { return a / 8 + 1; }
    inline short getY(int a)const { return a % 8 + 1; }
    inline short toOne(short x, short y)const { return 8 * (x - 1) + y - 1; }
    inline short toOne(const Coord &C)const { return 8 * (C.x - 1) + C.y - 1; }
    //棋盘二维坐标和bitset一维坐标互化

    //以下这些函数将在AI部分单独详细讨论其实现

    //判断是否可行
    bool isValid(const Coord&, const bool)const;
    bool isValid(int, int, bool) const;
    bool isValid_fast(const Coord&, const bool);
    bool isValid_fast(int, int, bool);
    //设置边界
    void setFrontline();
    void setFrontlineFor(const bool);
    inline void setAllFrontline(); //为统一此处先不给出定义
    //设置位置Valid与否
    void setValid();
    void setValid_fast();
    //判断是否为内部稳定子
    bool isStable(const Coord&)const;
    bool isStable(int, int)const;
    //下子的操作函数
    void move(const Coord&);
    void fastmove(const Coord&);
    //估值函数
    const double eval()const;
};

可以看到,相当多的基本操作被写入了类中,这样,AI可以安全、方便地复制棋盘,并调用Board类相关函数进行操作,这一定程度上简化了AI的设计。

⑤ Game类:

Game类中只有public属性的静态数据成员,没有成员函数,实际上为一系列游戏相关元素的存储集合,例如游戏主棋盘、搜索深度等。在一般的程序中,这些数据一般以全局变量的形式出现,但我在实际操作中,发现这样的全局变量有着不安全(易被误修改)、不方便(要extern)、易重名(与局部变量重名引发潜在错误)等诸多缺点,故将这些跨文件用到的数据全部放入了Game类,作为静态元素,实际操作效果也很好。 Game类中的元素有:游戏主棋盘、游戏语言、游戏难度、搜索深度、游戏当前状态(gameStatus枚举量)、AI标志(是否为AI对战)、UI标志(是否开启GUI)、debug标志(是否为debug模式)、辅助标志(是否为辅助模式)、输入标志(是否成功接收收入)、人类方(记录人类执黑或执白)、存档标志(记录存档是否成功)、手动标识(记录是否手动设置了参数,仅用于debug)、随机标志(是否开启AI随机性)、自动标志(是否为自动游戏)、终局搜索标志(是否开启AI终局搜索)、AI的返回值等等。

三、主程序设计:

1. 主菜单:

main()进入后,首先执行

#ifdef _WIN32
    system("mode con cols=50 lines=34");
    system("color 07");
#endif

将命令行窗口调整为合适的大小(暂时只写了Windows版本),而后通过

for (int i = 1; i < argc; i++)  
{
    if (argv[i][1] == 'g')
        Game::UIFlag = true;
    if (argv[i][1] == 'd')
        Game::debugFlag = true;
}

获取命令行参数,决定是否进入GUI模式或debug模式,而后进入菜单主循环:

while(menu());  
//menu()当且仅当用户选择Exit选项时才返回0,退出菜单主循环
//在我的程序中,所有其他这样的选单类的函数都写成了输入失败返回1,输入成功
//返回0的形式,因此调用都应采用while(my_menu());的形式以确保正常使用,

第一次进入菜单时,会自动调用语言选单,供用户选择语言:

if (firstRun)  
{
    Game::mainLang.setLangStrings(en_us);
    while(selectLang());
    isAssistMode();
}
firstRun = false;  
//firstRun的初始值为true,一旦进入过菜单,其值就被设为false
//mainLang是Game类中的langStrings类对象,用于调用相关字符串
//将mainLang初始化为en_us是必要的,否则语言选单无法正常输出错误提示

selectLang()菜单函数的实现很简单:

int selectLang()  
{
    CLS;
    fflush(stdin); //清空之前的输入缓冲区
    string in;
    cout << "Please Select Language:" << endll;
    ……
    cout << "Please Select:_\b";
    cin >> in; //输出选单,接受用户输入

    if (isValidInput(in, 1, 5)) //处理输入
    {
        switch (in[0])
        {
            case '1':
                Game::langFlag = en_us;
                break;
                ………
            default:
                fatalError(1);
        }
        Game::mainLang.setLangStrings(Game::langFlag);
        return 0; //跳出菜单
    }
    else //输出错误提示
    {
        cout << Game::mainLang.ivldipt << endl;
        PAUSE;
        return 1; //继续循环
    }
}

其中的isValidInput是用于方便制作数字选单的函数,用于快速判断用户输入是否正确:

inline bool isValidInput(string &str, short rangeFrom = 0, short rangeTo = 9)  
{
    return str.length() == 1 &&
           str[0] >= rangeFrom + '0' && str[0] <= rangeTo + '0';
}

本程序中几乎所有菜单都是这种形式,之后将不再赘述。

语言选择完毕后,将询问用户是否需要进入提示模式,输入Y/N后回车,执行:

#ifdef _WIN32
system(Game::mainLang.title.c_str());  //用c_str()方法将string转化为char*  
#endif
Game::mainLang.printVersion();  
Game::mainLang.printMenu();  
string in;  
cin >> in;  
if (isValidInput(in, 0, 7))  
    switch (in[0])

这段代码设置窗口标题并打印版本号、菜单,进入与前述selectLang()几乎相同的switch菜单结构,等待用户输入。

用户键入1时(PvP对战),执行:

case '1':  
    Game::AIFlag = NON_AI_MODE;
    Game::board.init(); //初始化棋盘
    gameThread(Human, Human); //创建游戏进程
    return 1;

显然,其中关键在于gameThread(playerType B, playerType W)这个函数,其传入两个playerType型的枚举量,启动游戏主进程。

类似的,用户键入2时(PvAI对战),执行:

case '2':  
    Game::AIFlag = AI_MODE;
    Game::board.init();
    selectSide(); //选择执黑执白
    while ((Game::diff = selectDiff()) == -1); //选择难度
    AchillesInit(); //初始化AI
    if (Game::humanSide == Black) //创建游戏进程
        gameThread(Human, AI);
    else
        gameThread(AI, Human);
     return 2;

//AI初始化函数的原型为:
//void AchillesInit(short diff = Game::diff);

可以看到,与PvP不同之处在于:PvAI模式调用selectSide()菜单让用户选择执黑执白,调用selectDiff()菜单设置难度,并将AI(Achilles)初始化。本质上仍然是调用gameThread函数创建游戏进程。

用户键入3时,理论上也可以通过之前类似的gameThread函数方式启动游戏,但为实现黑白两方AI的不同难度选择,实际上调用的是autoPlayThread函数:

case '3':  
    Game::AIFlag = AI_MODE;
    Game::autoFlag = true;
    Game::board.init();
    short diffB, diffW;
    CLS;
    cout << Game::mainLang.atplbs << endl << endl;
    while ((diffB = selectDiff()) == -1);
    CLS;
    cout << Game::mainLang.atplws << endl << endl;
    while ((diffW = selectDiff()) == -1);
    autoPlayThread(diffB, diffW);
    return 3;
//autoPlayThread原型为:
//void autoPlayThread(short diffB, short diffW)
//分别用diffB和diffW两个难度初始化黑白AI

类似的,用户键入4,5,6,7,0时,分别如下处理:

case '4':  
    Game::UIFlag ^= 1; //反转UIFlag
    return 4;
case '5':  
    if (Game::board.load()) //读取失败时返回0,否则返回1
    {
        if (Game::AIFlag) //读取成功时启动游戏进程
        { 
            if (Game::humanSide == Black)
                gameThread(Human, AI);
            else
                gameThread(AI, Human);
        }
        else
            gameThread(Human, Human);
    }
    return 5;
case '6':  
    while(settings()); //设置选单循环
    return 6;
case '7':  
    Game::mainLang.help(); //调用当前语言的帮助菜单
    return 7;
case '0':  
    return 0; //退出menu()循环
default:  
    fatalError(1); //我也不知道什么情况能进default(〜 ̄△ ̄)〜

如果之前的isValidInput(in, 0, 7)返回false,即用户输入不合法,则执行:

cout << Game::mainLang.ivldipt << endl;  
PAUSE;  
return 1;  

提示用户输入非法,并重新进入menu()循环。

以上就是menu()主菜单的主要实现。

2. 主游戏:

gameThread函数(游戏线程创建函数)定义如下

void gameThread(playerType B, playerType W)  
{
    if (Game::UIFlag) //如果GUI模式打开
    {
        thread UI(displayThread, 0, nullptr); //创建UI线程(传入空参数)
        thread game(othelloMain, B, W); //用传入的B和W创建主游戏线程
        UI.join();
        game.join(); //等待主游戏结束
    }
    else
        othelloMain(B, W); //非GUI模式直接调用主游戏函数
}

autoPlayThread函数与其几乎完全相同,只是调用的函数不是主游戏函数othelloMain而是自动游戏函数autoPlay。 下面只分析othelloMain

void othelloMain(playerType B, playerType W) //为便于理解,有精简  
{
    Game::status = Playing; //设置游戏状态为Playing
    playerType playerlist[2]{W,B};
    //生成临时的Player列表(理论上可以实现多人游戏233)
    Game::board.print(); //打印初始棋盘

    while (!Game::board.end()) //游戏可继续时进入循环,否则跳出
    {
        if (!Game::board(Valid)) //如果无处着子
        {
            CLS;
            Game::board.print(); //打印棋盘
            cout << Game::mainLang.nposm; //打印无处着子的提示
            PAUSE; //按任意键以继续…

            Game::board.move(Game::passCoord);
            //将passCoord传给游戏主棋盘的move方法,进行跳过操作
            Game::board.print() //重新打印棋盘
            continue;
        }

        getCoord(playerlist[~Game::board]);
        //将一个playerType枚举量传给getCoord函数,获取输入(输入被存储到Game::inputCoord中)
        //运算符~返回Board类对象的当前sideFlag(黑白方标志)

        while (!Game::inputFlag || notValid(Game::inputCoord))
        //输入不合法时的处理
        {
            if (returnCalled()) //如果输入的是MENU,则返回
                return;
            if (Game::inputFlag) //如果输入正确,但位置不合法
                cout << Game::mainLang.ip << Game::inputCoord.x 
                     <<char(Game::inputCoord.y + '@') << endl;
            else //如果是输入格式不对(输入的不是坐标)
                cout << Game::mainLang.ivldipt << endl;
                getCoord(playerlist[~Game::board]); //重新要求输入
        }

        Game::board.move(Game::inputCoord);
        //得到正确坐标后对棋盘进行操作
        Game::board.print(); //重新打印棋盘

        if (Game::AIFlag == AI_MODE    &&
        Game::board != Status(Game::humanSide))
        cout << Game::mainLang.aithink; //输出AI正在思考提示语

       } //end方法返回true,从while循环中跳出

    judge(); //进行判定并输出结果
}

其中while错误处理这一部分本来想在move方法中统一实现,即无论输入坐标是否合法都传给move处理,但似不如现在这样来得自然。 总体来说,由于写了人机统一的getCoord函数以获得坐标,对主棋盘的操作全部使用类成员函数实现,主游戏部分整体十分简洁。


3. 控制台获取坐标:

游戏通过统一的getCoord函数读入坐标,其代码为:

void getCoord(playerType T)  
{
    switch (T)
    {
        case Human:
            if (Game::UIFlag) //GUI开启时,从鼠标获得坐标输入
                Game::inputCoord = mouseInput();
            else //否则从键盘(控制台窗口)获得坐标输入
                Game::inputCoord = keyboardInput();
            break;
        case AI:
            if (Game::useList) //如果局面库开关打开,则尝试匹配局面库
                Game::inputCoord = savedList(Game::board.chara);
            if(!Game::useList || Game::inputCoord.x == -7) 
            //如果局面库开关关闭,或局面库无匹配(此时savedList返回特征坐标)
                Game::inputCoord = CallAI(Game::board);
                //learn();
            break;
        default:
               fatalError(1); //不知如何才可能走到这里
    }
}

其中的AI坐标获取部分我们将会在AI部分解析。

可以看到,getCoord只是沟通输入的桥梁,而用户获得输入的关键部分为keyboardInput函数:

Coord keyboardInput()  
{
    Game::inputFlag = false; //置输入成功标志为false
    cout << Game::mainLang.ytrn; //输出提示语

    string input;
    cin >> input; //获得输入

    transform(input.begin(), input.end(), input.begin(), ::toupper); 
    //将输入字母转为大写

    //检查是否输入特殊指令
    if (input == "EXIT")
        exit(0); //退出
    if (input == "MENU")
        return returnCoord; //返回特定坐标回到主菜单
    if (input == "UNDO")
        Game::board.undo(Game::AIFlag + 1);
        //调用undo方法进行悔棋操作
        //AIFlag = true(PvAI)时实际撤销两步,PvP时只需撤销一步
    if (input == "SAVE") //用户要求存档
    {
        Game::saveSuccess = Game::board.save();
        //调用save方法,Game::saveSuccess存储存档是否成功
        if (Game::saveSuccess) //如果存档成功
        {
            cout << Game::mainLang.savess << endl; //输出提示
            PAUSE; //任意键返回…
            return returnCoord; //返回特定坐标回到主菜单
        }
        else return keyboardInput();
        //如果保存失败,重新要求用户输入(保存错误在save()中处理)
    }
    if (input == "ABAB")
        debugMenu(); //特定指令调出神秘的debug菜单/微笑


    Coord tmpCoord = failCoord; //生成临时坐标

    if (input.length() == 2) //判断输入是否是合法坐标
    {
        if (isValidCoord(input[1],input[0]))
        //判断是否是B5型输入(先字母,后数字)
        {
            input.assign(input.rbegin(), input.rend()); //倒转输入
            Game::inputFlag = true; //输入成功
        }
        else if (isValidCoord(input[0],input[1]))
        //判断是否是5B型输入(先数字,后字母)
            Game::inputFlag = true; //输入成功
        else
            return tmpCoord; //否则返回特定的failCoord

        tmpCoord.x = input[0] - '0';
        tmpCoord.y = input[1] - '@'; //将input转换为合法坐标
    }

       return tmpCoord; //返回合法坐标
}

可以看到,KeyboardInput是和玩家进行控制台交互的主要途径,承担了获取输入坐标、处理特殊指令的重要作用。


4. 判定函数:

判定函数是在while (!Game::board.end())判定失败,即游戏结束时被调用的函数。其实现了结束游戏、关闭图形窗口、输出结果、打印游戏记录等功能,同时程序执行完judge()后返回othelloMain()othelloMain()执行完毕,回到主菜单循环。

void judge()  
{
    CLS;
    Game::status = End; //标记游戏结束
    if(Game::UIFlag)
        glutLeaveMainLoop(); //如果是GUI模式,关闭OpenGL创建的窗口

    Game::board.print(); //打印棋盘
    if (Game::AIFlag == AI_MODE && !Game::autoFlag) //PvAI模式下输出的提示语
    {
        if (Game::board(Game::humanSide) > Game::board(!Game::humanSide))
            cout << Game::mainLang.dftai << endll;
        else if (Game::board(Game::humanSide) < Game::board(!Game::humanSide))
            cout << Game::mainLang.toosimple << endll;
        else
            cout << Game::mainLang.tieai << endll;
    }
    else //PvP、AIvAI模式输出的提示语
    {
        if (Game::board(Black) > Game::board(White))
            cout << Game::mainLang.blk << Game::mainLang.win << endll;
        else if (Game::board(Black) < Game::board(White))
            cout << Game::mainLang.wht << Game::mainLang.win << endll;
        else
            cout << Game::mainLang.tie << endll;
    }

    Game::board.recordPrint(); //打印游戏记录
    PAUSE; //按任意键回到主菜单
}

以上的菜单循环、游戏循环、输入函数、判定函数四个部分就是主程序的主要部分。可以清晰的看出,主程序做到了模块化,不同功能都有特定函数实现,输入坐标的接口得到统一(均返回Coord类型的坐标),将棋盘封装成了一个整体,体现了一定程度的面向对象的特点。

四、AI设计:

此部分可能会包含我的心路历程233
不看前面可能会看不懂233

1. 棋盘操作及fast系列方法:

为了之后对估值函数实现的叙述更为简洁,我们在这里先介绍Board类的moveisValid等系列方法的具体实现。

① isValid

原型

bool Board::isValid(const Coord&, bool)const;  
bool Board::isValid(int, int, bool)const;  

顾名思义,该函数传入一个坐标,判断棋盘上该位置对于side这一方是否可行(可以着子)。 借助方向数组

const short dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};  

我们很容易得到一个传统而思路正常的实现:

bool Board::isValid(int x, int y, bool side)const  
{
    if (!inRange(x, y)) //判断是否在棋盘范围内
        return false;
    if (cell[x][y].status < Empty) //判断是否为空位置
        return false;
    for (int i = 0; i < 8; i++) //对于每一个方向
    {
        short nx = x + dir[i][0], ny = y + dir[i][1];
        if (cell[nx][ny].status == !side)
        //检查该方向上第一个子是否为另一方的棋子
        //如不是则显然该方向不可行
        {
            for (int p = nx, q = ny;
            inRange(p, q);
            p += dir[i][0], q += dir[i][1]) 
            //往该方向上移动一步
            {
                if (cell[p][q].status == Status(!side))
                //遇到对方棋子时continue
                    continue;
                if (cell[p][q].status >= Empty) 
                //先遇到空位置,说明该方向不可行,跳出for
                    break;
                if (cell[p][q].status == Status(side))
                //先遇到我方棋子说明该位置可行,返回true
                    return true;
            }
        }
    }
    return false; //检查完所有方向,均不可行,返回false
}

该思路简单自然,看似没有改进空间,于是也被我用了个一个来月。

后来我某一天忽然有了个奇思妙想,咔咔咔写下了如下这个方法:

bool Board::isValid_fast(int x, int y, bool side)  
{
    bool R = false; //置返回值为false
    for (int i = 0; i < 8; i++) //对于每个方向
    {
        cell[x][y].validDir[i] = false; 
        //置该方向的可行标志为false

        short nx = x + dir[i][0], ny = y + dir[i][1];
        if (cell[nx][ny].status == Status(!side))
        //检查该方向上第一个子是否为另一方的棋子
        //如不是则显然该方向不可行
        {
            for (int p = nx, q = ny;
            inRange(p, q);
            p += dir[i][0], q += dir[i][1])
            //往该方向上移动一步
            {
                if (cell[p][q].status == Status(!side))
                //遇到对方棋子时continue
                    continue;
                if (cell[p][q].status >= Empty)
                //先遇到空位置说明该不可行,跳出for
                    break;
                if (cell[p][q].status == Status(side))
                //先遇到了我方的棋子,说明该位置可行
                {
                    cell[x][y].validDir[i] = true;
                    R = true;
                    //置该方向的可行标志和返回标志为true
                    break;
                    //跳出for
                }
            }
        }
    }
    return R; //若检查完所有方向均不可行,返回初始值false
}

... 看完这段代码,你可能是这个样子的:(╯‵□′)╯︵┻━┻ 你可能会说:这不是tm几乎一样吗!!! 你可能还会说:fast尼玛,这不是更耗时了吗!!! 然后我就会抿一口茶,微微一笑,说道:“Naïve...”

首先,这个方法不会浪费很多的时间。这是因为,如果该位置不能下子,两种方法几乎不会有任何时间差别,都要完全扫描八个方向;如果该位置能够下子,也有很大几率是扫描到第7甚至第8个方向时才返回true。因此,isValid_fast()方法的确可能比isValid()方法要慢,但慢的时间几乎可以忽略不计。 但与此同时,我们很容易可以看出isValid_fast()方法的巨大优势:他相比isValid()方法,得到了更多的信息,而这些信息,能够大大加速move()方法的实现,我们将在即将介绍的move()方法中展示其对效率的提升。

② setFrontline

Frontline,指的是当前棋盘有子部分的边界。对于一个棋子,其相邻八个方向中为空的位置即视为这个棋子的边界,棋盘上所有棋子边界的并集被视为局面的总边界长,同理可以定义黑白两方各自的边界。 Frontline一开始是使用集合set<Coord>作为容器存储的,目的是为了方便去除重复,实践中发现效率奇低无比,感觉自己好傻逼,后改用bitset<64>实现,大大提高了其计算效率。
下面是setFrontline系列函数的实现:

void Board::setFrontline()  
{
    setFrontlineFor(sideFlag); //调用方法计算黑白两方边界
    setFrontlineFor(!sideFlag);
    setAllFrontline(); //调用方法计算棋盘整体边界
}
void Board::setFrontlineFor(bool side)  
{
    sideFrontline[side].reset(); //重置side方的边界图
    for (short i = 1; i <= 8; i++)
        for (short j = 1; j <= 8; j++) 
            if (cell[i][j].status == Status(side)) 
            //对于棋盘上每个side方的位置
                for (int d = 0; d < 8; d++) //对8个相邻位置
                {
                    short x = i + dir[d][0];
                    short y = j + dir[d][1];
                    if (inRange(x, y) &&
                       (cell[x][y].status >= Empty))
                       //如果其在棋盘范围内且为空,则记入边界图
                        sideFrontline[side][toOne(x, y)] = true;
                }
}
inline void Board::setAllFrontline()  
{
    frontline = sideFrontline[0] | sideFrontline[1];
    //直接利用sideFrontier的结果按位或即可
}

这一系列函数非常好理解,但是,为什么需要设置边界呢? 首先,frontierCount是AI要用到的一个重要参数,迟早得算。 其次,设置Frontline能够大大加快setValid函数的效率,这是因为,传统setValid的实现需要扫描整个棋盘上的位置,而显然,Valid位置只可能出现在Frontline上,改进的setValid_fast只需要检查Frontline上的元素是否可行即可。

③ setValid

setValid函数的存在也是自然的,因为在一个棋盘上,Empty的位置实际上有两种,一种是空且棋盘当前方不可着子的位置,一种是空且棋盘当前方可着子的位置。由于之前计算了边界,setValid函数不需要扫描整个棋盘的所有位置,只需扫描边界位置即可:

void Board::setValid_fast()  
{
    setFrontline(); //刷新边界线
    validCoord.clear(); //清空可行坐标容器
    statusCount[Valid] = 0; //当前方Valid计数清零
    validCountFor[Black] = validCountFor[White] = 0; //黑白Valid计数清零
    for (unsigned i = 0; i < 64; i++)
        if (frontline[i]) //对于边线图中为true每一个位置
        {
            short x = getX(i);
            short y = getY(i); //提取出二维坐标
            if (isValid_fast(x, y, sideFlag)) 
            //用fast系列isValid方法检查该位置对当前着子方是否可行
            {
                cell[x][y].status = Valid; //标记为Valid
                statusCount[Valid]++;
                validCountFor[sideFlag]++; //当前方Valid计数++
                validCoord.push_back({x,y}); //推入记录容器
            }
            //该位置对当前着子方不可行
            else
            {
                cell[x][y].status = Empty; //标记为Empty
                if (isValid(x, y, !sideFlag)) //如果非当前着子方可行
                    validCountFor[!sideFlag]++; //非当前方Valid计数++
            }
        }
    vector<Coord>::iterator vbegin = validCoord.begin();
    vector<Coord>::iterator vend = validCoord.end();
    sort(vbegin, vend, cmp);
}

其中cmp函数以位置估值表为根据,将validCoord容器降序排列:

inline bool cmp(const Coord &a, const Coord &b)  
{
    return coordValue[a.x][a.y] > coordValue[b.x][b.y]; 
}

注意到,setValid函数不仅将当前方可行位置记录、计数、推入容器,还对非当前方的可行位置进行了计数。这是由于AI将用到非当前方的可行位置计数。而前者使用isValid_fast是因为这样能加速move操作,后者使用isValid是因为非当前方不可能进行move操作,此时isValid函数更快。

④ isStable

其作用是判断棋盘指定内部位置上的子是不是稳定子(边角上的棋子不使用这个函数,其有另一套判断规则)。

bool Board::isStable(int x, int y)const  
{
    for (int i = 0; i < 8; i++) //对每个方向
        for (int nx = x + dir[i][0], ny = y + dir[i][1];
        inRange(nx, ny); nx += dir[i][0], ny += dir[i][1])
            if (frontline[toOne(nx, ny)]) //如果该方向有边界位
                return false;             //说明其不稳定
    return true;                          //如果所有方向上都没有边界位,说明其稳定
}

这个判断方法基于下面这个断言:

一个内部子为稳定子几乎等价于其八个方向均被棋子填满

我们只能保证断言必要性正确,事实上其充分性的反例很多(尤其是次外层位置上的棋子),但这并不影响isStable函数的总体正确性(虽然不排除极少数的伪false情况)。

⑤ move

和前面的所有的棋盘操作方法一样,move也有两个实现,这是传统的、不依赖validDir[8]数组的实现:

void Board::move(const Coord &pos)  
{
    if (pos.x == -1 && pos.y == -1) //如果传入的为特定的passCoord,不进入move主体处理
        passFlag[sideFlag] = true;

    else if (inRange(pos.x, pos.y)) //如果传入的是合法位置
    {
        for (int i = 0; i < 8; i++) //对所有8个方向
        {
            int dx = dir[i][0], dy = dir[i][1]; 
            if (cell[pos.x + dx][pos.y + dy].status == !sideFlag) //以下和isValid函数类似
            {
                for (int p = pos.x + dx, q = pos.y + dy; inRange(p, q); p += dx, q += dy)
                {
                    if (cell[p][q].status >= Empty)
                        break;
                    if (cell[p][q].status == Status(sideFlag))
                    {
                        cell[pos.x][pos.y].status = Status(sideFlag);

                        for (int r = p - dx, s = q - dy;
                        cell[r][s].status != Status(sideFlag);
                        r -= dx, s -= dy)
                            cell[r][s].status = Status(sideFlag);
                        break;
                    }
                }
            }
        }
        passFlag[sideFlag] = false; //move完成,当前side的passFlag标记为false
    }
    else
        fatalError(1); //正常情况下不可能传入非法位置,进入异常处理

    movesRecord.push_back(pos); //记录移动(passCoord也被记录)
    flipSide(); //翻转当前游戏标志方(黑<->白)
    setValid(); //重新设置可行位置(不依赖validDir[8],故不调用fast方法)
    count(); //棋子计数
    charaCalc(); //刷新棋盘特征值(hash)
}

可以看到,不使用validCoord[8]move实现冗长而复杂,要对八个方向重新扫描,并在成功时往回实现翻转操作,远不如以下的fastmove方法:

void Board::fastmove(const Coord &pos)  
{
    for (int i = 0; i < 8; i++) //对于每个方向
    {
        short x = pos.x, y = pos.y;
        if (cell[x][y].validDir[i]) //如果validDir中记录该方向可翻转
            do
            {
                cell[x][y].status = Status(sideFlag);
                x += dir[i][0];
                y += dir[i][1];
            } while (cell[x][y].status == Status(!sideFlag)); 
            //翻转到遇到我方棋子为止
    }

    flipSide(); //翻转当前游戏标志方(黑<->白)
    setValid_fast(); //重新设置可行位置(依赖validDir[8],需要调用fast方法)
    count(); //棋子计数
    charaCalc(); //刷新棋盘特征值(hash)
}

为了真正实现"fast",fastmove方法没有将输入坐标存入moveRecord容器。实际上,在程序中,getCoord方法返回的坐标(即对主棋盘的操作)是使用move方法实现的,因为整局只有60次这样的调用,move不会让用户感觉很慢(实际上一次move方法的耗时数量级太小了)。而在AI的多层搜索中,调用的是fastmove方法,据统计,AI的每次Botzone响应都要调用30000次左右的move方法,这样在搜索时节省下来的时间是相当可观的。

总的来说,fast系列方法基于frontier边界和validDir[8]可行方向数组,是一套高效的、适合AI的棋盘操作算法。很快我们就可以看到其在AI实现中起到的深远意义。

2. 估值函数的设计:

eval()Board类的成员函数,是一个由经验给出的启发式算法(heuristic algorithm)。函数接收一个Board类对象,返回该棋盘当前着子一方的一个局面评估值(double4),该返回值越高,说明(至少是我认为)对当前着子一方越有利。该函数从8个角度进行局面评估,并按照AI初始化函数设定好的系数对这八个角度的估值进行线性组合,返回最终估值,下面是Board::eval()的源代码:

const double Board::eval()const //用const修饰,不改变传入对象  
{
    //基于位置特征的估值
    double CharaEval = 0;
    if (CRFACTOR)
    {
        double myChara = allEvalFor(sideFlag);
        double opChara = allEvalFor(!sideFlag);
        CharaEval = myChara - opChara;
    }


    //基于黑白子比例的估值
    double BWRateEval = 0;
    if (BWFACTOR)
    {
        short myStoneCount = statusCount[sideFlag];
        short opStoneCount = statusCount[!sideFlag];
        if (myStoneCount > opStoneCount)
            BWRateEval = 100.0 * myStoneCount / (myStoneCount + opStoneCount);
        else if (myStoneCount < opStoneCount)
            BWRateEval = -100.0 * opStoneCount / (myStoneCount + opStoneCount);
        else BWRateEval = 0;
    }


    //基于黑白边界的估值
    double FrontlineRateEval = 0;
    if (FRFACTOR)
    {
        size_t myFrontlineCount = sideFrontlineb[sideFlag].count();
        size_t opFrontlineCount = sideFrontlineb[!sideFlag].count();

        if (myFrontlineCount > opFrontlineCount)
            FrontlineRateEval = -100.0 * myFrontlineCount / (myFrontlineCount + opFrontlineCount);
        else if (myFrontlineCount < opFrontlineCount)
            FrontlineRateEval = 100.0 * opFrontlineCount / (myFrontlineCount + opFrontlineCount);
        else FrontlineRateEval = 0;
    }


    //基于角位棋子的估值
    double CornerEval = 0;
    if (CNFACTOR)
    {
        short myCornerCount =
            (cell[1][1].status == Status(sideFlag)) +
            (cell[1][8].status == Status(sideFlag)) +
            (cell[8][1].status == Status(sideFlag)) +
            (cell[8][8].status == Status(sideFlag));
        short opCornerCount =
            (cell[1][1].status == Status(!sideFlag)) +
            //......
        CornerEval = 25 * (myCornerCount - opCornerCount);
    }


    //基于靠近角位的危险位置的估值(*位和+位)
    double DCornerEval = 0; //实际上 >= Empty 意味着该位置为空(Empty或Valid)
    if (DCFACTOR)
    {
        short myDCornerCount = //*位格外危险...根据经验给其数目乘二
        (cell[1][1].status >= Empty) && (cell[1][2].status == Status(sideFlag)) +
        (cell[1][1].status >= Empty) && (cell[2][2].status == Status(sideFlag)) * 2 +
        (cell[1][1].status >= Empty) && (cell[2][1].status == Status(sideFlag)) +
        //......(共12行)
        short opDCornerCount =
        (cell[1][1].status >= Empty) && (cell[1][2].status == Status(!sideFlag)) +
        //......(共12行)
        DCornerEval = -12.5 * (myDCornerCount - opDCornerCount);
    }


    //基于边界稳定子的估值
    double SideEval = 0;
    if (SDFACTOR)
    {
        short mySideCount = 0, opSideCount = 0;
        if (cell[1][1].status == Status(sideFlag))
        {
            for (int i = 1; i <= 8; i++)
            {
                if (cell[1][i].status == Status(sideFlag))
                    mySideCount += sideVal[i];
                else
                    break;
            }
            for (int i = 1; i <= 8; i++)
            {
                if (cell[i][1].status == Status(sideFlag))
                    mySideCount += sideVal[i];
                else
                    break;
            }
        }
        else if (cell[1][1].status == Status(!sideFlag))
        {
            //......
        }

        if (cell[1][8].status == Status(sideFlag))
        //......

        //这样的if...else一共有4个,这里从略
        SideEval = 2.5 * (mySideCount - opSideCount);
    }

    //基于内部稳定子的估值
    double StableEval = 0;
    if (STFACTOR)
    {
        short myStableCount = 0;
        short opStableCount = 0;

        for (int i = 2; i <= 7; i++)
            for (int j = 2; j <= 7; j++)
                if (isStable(i, j))
                {
                    if (cell[i][j].status == Status(sideFlag))
                        myStableCount++;
                    else
                        opStableCount++;
                }
        StableEval = 12.5 * (myStableCount - opStableCount);
    }

    //基于行动力的估值
    double MobEval = 0;
    if (MDFACTOR)
    {
        short myValidCount = validCountFor[sideFlag];
        short opValidCount = validCountFor[!sideFlag];
        if (!opValidCount) //如果对方无子可下(很可能迫使对方跳过回合)
            MobEval = 150; //给予较高的特别估值
        else if (!myValidCount) //如果我方无子可下(很可能被迫跳过回合)
            MobEval = -450; //给予很低的特别估值
        else if (myValidCount > opValidCount)
            MobEval = (100.0 * myValidCount) / (myValidCount + opValidCount);
        else if (myValidCount < opValidCount)
            MobEval = -(100.0 * opValidCount) / (myValidCount + opValidCount);
        else MobEval = 0;
    }

    //加权计算估值
    double Eval =
        (BWFACTOR * BWRateEval) +
        (CNFACTOR * CornerEval) +
        (DCFACTOR * DCornerEval) +
        (SDFACTOR * SideEval) +
        (STFACTOR * StableEval) +
        (MBFACTOR * MobEval) +
        (FRFACTOR * FrontlineRateEval) +
        (CRFACTOR * CharaEval);

    return Eval;
}

其中参数以静态变量的形式存储,可以看到,当某项的参数为0时,其不会被计算,这能在一些特定的时期缩短估值的时间。

接下来就每一个方面分析:

① 基于位置特征的估值(CharaEval)

eval()使用根据经验总结出的一张估值表(最初似乎参考了某国外论坛上网友的发言,后来经过自己的修改早已面目全非233):

const short coordValue[10][10] =  
{
    {-8,-8,-8,-8,-8,-8,-8,-8,-8,-8},
    {-8,20,-3,11, 8, 8,11,-3,20,-8},
    {-8,-3,-7,-4, 1, 1,-4,-7,-3,-8},
    {-8,11,-4, 2, 2, 2, 2,-4,11,-8},
    {-8, 8, 1, 2,-3,-3, 2, 1, 8,-8},
    {-8, 8, 1, 2,-3,-3, 2, 1, 8,-8},
    {-8,11,-4, 2, 2, 2, 2,-4,11,-8},
    {-8,-3,-7,-4, 1, 1,-4,-7,-3,-8},
    {-8,20,-3,11, 8, 8,11,-3,20,-8},
    {-8,-8,-8,-8,-8,-8,-8,-8,-8,-8}
};

可以看到角位被赋予了最高的估值,角邻近位(紧靠每个角的两个边上的位置(例如1B,2A)在本文中被称为+位,紧靠每个角的对角线上的位置(例如2B,2G)在本文中被称为*位)被认为是不好的,因为这些位置较容易让对方占角或者被对方翻转大量棋子2。 边上的其他位置都被赋予了很高的估值,这是基于迅速占边容易获得边角稳定子优势的考虑。 最中心的位置被赋予较低的值,是因为我不记得为什么了,是因为经验。总之这个估值表全靠经♂验,没什么可说的。 翻了很多国外的文献,发现也大多都是和我的估值表类似的模式。 重要程度: ★★

② 基于黑白子比例的估值(BWRateEval)

从一定来说,我方棋子数比对方多能够说明我方占有优势,同时为了提高该项估值的稳定性,该项估值以百分比的形式呈现:

if (myStoneCount > opStoneCount)  
    BWRateEval = 100.0 * myStoneCount / (myStoneCount + opStoneCount);
else if (myStoneCount < opStoneCount)  
    BWRateEval = -100.0 * opStoneCount / (myStoneCount + opStoneCount);
else BWRateEval = 0;  

这样的好处在于能够动态地反映黑白子在场上的状况,比求差或者直接用比例更合理,而且范围可预测,缺点是它好像不连续了Orz。反正它不重要。 实际上该项估值的参考价值在终局之前都不是很大,因为黑白子比例是一项和谁即将着子关系很大的参数,即使白方在着子前棋子数目远少于黑方,着子后也可能会逆转局势。 重要程度: ★

③ 基于角位、近角位棋子的估值(CornerEval, DCornerEval)

根据经验,占领角位的带来的优势是极其明显的,故为角位附加了这一项特别的估值。而在前期,下*位或+位会很容易(一不小心)就丢角,故前期给近角位附加了一项特别的负估值,在中后局这项估值的系数将会被调低,因为此时边上棋子可能已经达到一定数目,下在+位的棋子可能有翻转对方大量棋子的奇效。其实主要还是靠经♂验。 重要程度: ★★★★

④ 基于稳定子的估值(SideEval, StableEval)

稳定子的多少显然应当成为棋盘估值的重要指标。拥有更多的稳定子,一方面能保证我方最少棋子数,另一方面,稳定子可以起到辅助翻转大量对方棋子、形成成片稳定子的作用,而对方却无可奈何。 而稳定子又分为两类,一类是边角稳定子,一类是内部稳定子,其判断方法不一样,重要程度亦不一样。直观上说,边界稳定子应当更为重要,因为边界稳定子往往会成片形成,很容易起到翻转对方大量棋子的作用,而内部稳定子相对显得不那么重要,因为其根本不能起到协助翻转的作用(因为其所有方向均被填满)。 因此边界稳定子权重较大,其计算方法为,从棋盘某一角(包括该角)开始,权重分别为:

static const short sideVal[9] = {0, 1, 1, 1, 2, 3, 4, 6, 7};  

这种权重设定方法将鼓励AI占边,形成稳定的强边效应,达成对我方极为有利的局面。 而内部稳定子是在eval()中调用isStable()函数实现的,其参数实际被设置得较低。

注意到,稳定子计算是eval()函数中最耗时的部分之一,故在对弈中前期,SDFACTORSTFACTOR被设置为0,因为中前期几乎不可能会产生稳定子,将参数设为零能节约时间。 重要程度: ★★★★★

⑤ 基于行动力的估值(MobEval, FrontlineEval)

行动力(Mobility),简单来说,是指棋盘上某一方的可着子位置个数。行动力维持较高水平,几乎就能保证之后若干步内都有较好着法,因此行动力是比较重要的。 行动力估值采用了与黑白子比例估值类似的百分比算法,但有所不同的是,行动力估值时会处理一些特殊局面:

if (!opValidCount) //如果对方无子可下  
    MobEval = 150; //返回较高的估值
else if (!myValidCount) //如果我方无子可下  
    MobEval = -450; //返回很低的估值

我方无处着子显然是一种不利的局面,而且根据经验,无处着子的情况往往会连续出现,形成十分糟糕的局面。在我方无处着子时返回一个较大的负值能很大程度上避免这种劣着,同理,对方无处着子是对我方有利的局面,返回一个较大的正值能使AI倾向于选择这种位置。

仅依靠当前可行位置来确定行动力是有一定局限性的,因此我在AI中引入了边界长的概念,由来定义潜在行动力的大小(这是受到[参考文献][3]中散度这一概念的启发,而未引入凝聚手等概念的原因是它不如边界长更适合AI来处理和思考),显然,白方的边界长越大,黑方的潜在行动力越高,反之亦然。 由于我们使用fastmove方法操作棋盘时,会自动刷新边界图,因此,边界长只需要简单调用bitset类的count()方法即可快速得到:

size_t myFrontlineCount = sideFrontlineb[sideFlag].count();  
size_t opFrontlineCount = sideFrontlineb[!sideFlag].count();  

这里也体现了前面所说的fast系列方法的巨大效率优势(bitset类的所有方法都是安全高效的)。 重要程度: ★★★★★


3. AI主函数(搜索函数)的调用和设计:

①AI的初始化

menu()主菜单中,我们调用了AchillesInit()函数对AI做初始化,该函数根据用户输入,设置搜索深度maxDepth、随机化标志randomFlag、终局搜索标志finalSearch,例如,选择5号难度(报警模式)时,将会按如下方式初始化:

case 5:  
    Game::maxDepth = 8;
    Game::finalSearch = true;
    Game::randomFlag = false;
break;  

这是游戏前AI需要的的准备工作。

之前我们提到了,在主游戏中,程序是通过getCoord这个统一的接口来获取坐标的,其中涉及AI的部分为:

case AI:  
    if (Game::useList) //如果局面库开关打开,则尝试匹配局面库
        Game::inputCoord = savedList(Game::board.chara);
    if(!Game::useList || Game::inputCoord.x == -7) 
    //如果局面库开关关闭,或局面库无匹配(此时savedList返回特征坐标)
        Game::inputCoord = CallAI(Game::board);
    //learn();
    break;

其中learn()学习函数的初步实现想法是,将savedList函数中的局面库内容全部转移入文件中(外置化),每次AI返回坐标时,由learn()将该次搜索返回的最佳坐标、返回值、搜索深度等参数写入文件,以后遇到相同局面时,如搜索深度小于等于记录的结果,即可直接从savedList中读取最佳坐标;否则可以调用savedList中的数据作为validCoord中的主变量做更深的搜索,加速剪枝。这样便可以实现一定程度上的学习效果。此函数Coming Soon。

savedList()局面库目前使用最简单的实现,本质上是一个switch() case结构:

Coord savedList(int chara)  
{
    Coord savedCoord;
    switch (chara)
    {
        case 583350:
            savedCoord = {3,4};
            break;
        case 595238:

            //......

        default:
            savedCoord = {-7, -7};
    }
    return savedCoord;
}

其中的结果大部分是将一方搜索深度调为15,另一方深度10-15随机化,经过一晚上的自动化对战自动输出得到的;还有一些是在本地用更深的深度复盘Botzone上的失败对局得到的。

再看CallAI函数,此函数的主要作用是初始化估值函数Board::eval()系数,并调用AI进行搜索:

Coord CallAI(Board &board)  
{
    startTime = clock(); //记录AI启动时间

    //如果深度被设置为0,或触发随机机制,返回随机位置。
    //其中的Hector是一个纯随机AI
    if (Game::maxDepth == 0 || (Game::randomFlag&&!(rand() % RANDFACTOR)))
        return Hector(board);

    size_t validCount = Game::board.validCount();
    size_t turnID = Game::board.turnCount(); 
    //生成这两个变量是为了和Botzone版本的程序匹配

    if (Game::finalSearch && turnID > 21) 
    {
        if (validCount > 10)
            Game::maxDepth = 11;
        else
            Game::maxDepth = 12;
    }
    //如果打开了终局搜索,且进入终局,则深度加深

    if (turnID > 23) //根据回合数调整参数
    {
        BWFACTOR = 0.20; //终局时调高黑白子比例参数
        DCFACTOR = 0.60; //调低危险角子参数
        CNFACTOR = 8.00;
        SDFACTOR = 6.00;
        STFACTOR = 4.00;
        FRFACTOR = 0.24; //调低边界长参数
        MBFACTOR = 0.24; //调低行动力参数
        CRFACTOR = 0.01; //调低特征估值参数
    }
    else if (turnID > 21)
    {
        BWFACTOR = 0.15;
        DCFACTOR = 1.20;
        CNFACTOR = 8.00;
        SDFACTOR = 6.00;
        STFACTOR = 4.00;
        FRFACTOR = 0.24;
        MBFACTOR = 0.24;
        CRFACTOR = 0.01;
    }
    else if (turnID > 18)
    {
        BWFACTOR = 0.12;
        CNFACTOR = 8.00;
        DCFACTOR = 1.50;
        SDFACTOR = 5.00;
        STFACTOR = 3.00;
        FRFACTOR = 0.66;
        MBFACTOR = 0.45;
        CRFACTOR = 0.04;
    }
    else if (turnID > 14)
    {
        BWFACTOR = 0.08;
        CNFACTOR = 9.50;
        DCFACTOR = 4.80;
        SDFACTOR = 4.00;
        STFACTOR = 1.00;
        FRFACTOR = 0.89;
        MBFACTOR = 0.59;
        CRFACTOR = 0.09;
    }
    else if (turnID > 8)
    {
        BWFACTOR = 0.06;
        CNFACTOR = 9.50;
        DCFACTOR = 4.00;
        SDFACTOR = 4.00;
        STFACTOR = 0.00;
        FRFACTOR = 1.02 - double(turnID) / 50;
        MBFACTOR = 0.71 - double(turnID) / 60;
        CRFACTOR = 0.12;
    }
    else
    {
        BWFACTOR = 0.04; //开局时不重视黑白比例
        CNFACTOR = 7.50;
        DCFACTOR = 3.90;
        SDFACTOR = 0.00;
        STFACTOR = 0.00; //不计算基于稳定子的估值
        FRFACTOR = 1.27 - double(turnID) / 50; //重视行动力估值
        MBFACTOR = 0.82 - double(turnID) / 60;
        CRFACTOR = 0.13; //重视位置特征估值
    }

    Coord tmpCoord;
    Game::AchillesReturn = Achilles(board, tmpCoord); //执行搜索,并记录返回值

    assert(Game::board.isValid(tmpCoord, ~board)); //防bug

    return tmpCoord; //返回搜索得到的最佳坐标
}


②主搜索函数

主搜索函数Achilles()的原型为:

double Achilles(const Board &board, Coord &bestCoord,  
                short depth = Game::maxDepth,
                double alpha = ALPHA, double beta = BETA);

由于要实现递归,而最终Board::eval()的返回值为double类型,故该函数不能直接返回坐标,只能通过引用的方式传出,而传入棋盘board使用const引用是为了提高传递效率的同时保证安全,这是一个利用Alpha-Beta剪枝法进行搜索操作的函数,其中默认传入的alpha和beta宏定义于Achilles.h中:

#define ALPHA INT_MIN
#define BETA INT_MAX //因为没有DOUBLE_MIN这种东西

有关doubleint类型效率的考量,请见脚注3。

下面是`Achilles·搜索主函数的具体实现:

int selectLang()  
{
    CLS;
    fflush(stdin); //清空之前的输入缓冲区
    string in;
    cout << "Please Select Language:" << endll;
    ……
    cout << "Please Select:_\b";
    cin >> in; //输出选单,接受用户输入

    if (isValidInput(in, 1, 5)) //处理输入
    {
        switch (in[0])
        {
            case '1':
                Game::langFlag = en_us;
                break;
                ………
            default:
                fatalError(1);
        }
        Game::mainLang.setLangStrings(Game::langFlag);
        return 0; //跳出菜单
    }
    else //输出错误提示
    {
        cout << Game::mainLang.ivldipt << endl;
        PAUSE;
        return 1; //继续循环
    }
}
可以看到,以上算法是基于Alpha-Beta剪枝法的改进搜索方法,相比一般、最简单的的Alpha-Beta剪枝法,有着以下的优点:

  • 有终局判定功能,在游戏分出胜负时会返回使胜子数最多、负子数最少的位置。
  • 有时间控制功能,可以保证不超时。
  • 可以处理某一方无处着子的状况,在我方/对方行动力较低时也能返回正常深度的结果。
  • 之前setValid_fast中的排序处理使博弈树基本有序,采用了首变量优先搜索和最小窗口搜索的原则,使剪枝尽可能多、尽可能快的发生,提高了搜索效率。
  • 引入了PVS(主变量搜索)方法[^5],未来可扩展用于记忆化(机器学习)及其他方面。

由于Alpha-Beta剪枝法的特点,当博弈树强有序时,剪枝十分迅速,故深层搜索会十分迅速,于是我们可以得到一种叫做迭代加深的方法,这个方法在Botzone这种限时平台上能达到非常好的效果: isValidInput 可以看到,这种方法从给定的初始深度开始展开搜索,若搜索结束后未超时,就这次搜索得到的坐标移到validCoord容器的首位,再展开深一层的搜索,由于有上一次结果的辅助,深一层搜索一般能很快得到结果。这种策略能充分利用时间,得到尽可能多的有用信息。

以上便是AI的主要实现。


五、总结&TO DO

总结:

  • 主程序中,基于简单、易用、安全的原则,大多数对象被自然地包装了成类和结构。
  • 棋盘的估值函数被写在Board类中,其基于黑白棋比例、位置特征、角特征、稳定子、行动力五类共八个参数进行估值,根据经验进行了大量的系数调整,达到了较好的效果。
  • 程序的AI(Achilles)采用了Alpha-Beta剪枝法、PVS、终局搜索、终局判定、动态调整系数、PASS处理、博弈树排序、超时处理、迭代加深等高级搜索方法,其效率较高,在Botzone平台1s的时限内能够达到8~15层的搜索深度。

TO-DO LIST:

  • 利用多核处理器的普及,可以将Alpha-Beta搜索改成并行搜索,加快速度。
  • 基于类和结构的棋盘可能还是会带来整体的效率问题,将来会评估采用位棋盘的可能[^6]。
  • playerType用类来写可以简化主程序结构,开始写时没有想到,之后又一直忙于优化AI没空去改。
  • 浮点数运算的确还是可能对整体的估值效率带来一定的影响,后续版本中将尝试全部采用2的幂次拟合。
  • 学习功能有待完成,savedList函数可以放到Achilles主搜索函数中去匹配,这样每次搜索都可以利用到局面库的内容。
  • 只是用了别人的GUI,没有自己完成这方面的工作,未来可能会移植到C#或其他绘图机制更简单的平台上,用成熟的图形引擎完成GUI界面。
  • 单纯的黑白棋游戏不具有吸引力,可能会设计开发“街机模式”、“禅模式”、“彩色模式”等新型游戏模式,并辅以成就系统,吸引更多的人来黑白棋这一经典的智力游戏。

总之,作为计算概率A的大作业,该程序已经达到了所有的要求。黑白棋作为一个简单而又深刻的智力游戏也已经深深地吸引了我,作业的提交远远不是结束,我之后会不断优化AI,达到更高水平。

  1. 由于没有OpenGL编程经验,程序的GUI部分是经过陈子恒同学的允许后,从他的源代码GUI部分移植过来的,十分感谢他的帮助。

  2. 实际上经验增加后,感觉这些位置其实也没有那么糟糕,这也是基于位置的估值的系数被调得很低的原因。

  3. [3]:http://wenku.baidu.com/link?url=0pqllBcpLzPL4jUurwfsj6dEx6sTUnNeLpq92FKpSwjS2I13j-HNMEhFd0lptZHqmyWSWApAmfGqYYD-Ndxbxnlai_Rk6qNZiCLElTlbP7y
  4. 为了提高运算效率,Botzone版本中不含有任何浮点数类型,所有系数、参数都使用了扩大倍数使用整数(尤其是2的幂次)进行拟合,实际上效率增加效果不明显,因此没有对主版本做这样的优化。

  5. 在主版本中没有使用,在Botzone版本中和迭代加深方法一起得到了运用。

  6. 但有同学使用完全使用位棋盘和位操作等低级方法,搜索深度和准确度仍然远不如Achilles,这让我觉得放弃方便易行的类方法不太有必要。

Jet

继续阅读此作者的更多文章

北京市 海淀区