人工智能四子棋AI

#include <iostream> #include "Point.h" #include "Strategy.h" using namespace std; /* 策略函数接口,该函数被对抗平台调用,每次传入当前状态,要求输出你的落子点,该落子点必须是一个符合游戏规则的落子点,不然对抗平台会直接认为你的程序有误 input: 为了防止对对抗平台维护的数据造成更改，所有传入的参数均为const属性 M, N : 棋盘大小 M - 行数 N - 列数 均从0开始计， 左上角为坐标原点，行用x标记，列用y标记 _top : 当前棋盘每一列列顶的实际位置. e.g. 第i列为空,则_top[i] == M, 第i列已满,则_top[i] == 0 _board : 棋盘的一维数组表示, 为了方便使用，在该函数刚开始处，我们已经将其转化为了二维数组board 你只需直接使用board即可，左上角为坐标原点，数组从[0][0]开始计(不是[1][1]) board[x][y]表示第x行、第y列的点(从0开始计) board[x][y] == 0/1/2 分别对应(x,y)处 无落子/有用户的子/有程序的子,不可落子点处的值也为0 lastX, lastY : 对方上一次落子的位置, 你可能不需要该参数，也可能需要的不仅仅是对方一步的 落子位置，这时你可以在自己的程序中记录对方连续多步的落子位置，这完全取决于你自己的策略 noX, noY : 棋盘上的不可落子点(注:其实这里给出的top已经替你处理了不可落子点，也就是说如果某一步 所落的子的上面恰是不可落子点，那么UI工程中的代码就已经将该列的top值又进行了一次减一操作， 所以在你的代码中也可以根本不使用noX和noY这两个参数，完全认为top数组就是当前每列的顶部即可, 当然如果你想使用lastX,lastY参数，有可能就要同时考虑noX和noY了) 以上参数实际上包含了当前状态(M N _top _board)以及历史信息(lastX lastY),你要做的就是在这些信息下给出尽可能明智的落子点 output: 你的落子点Point */ int step = 0; int Mark[3][12][12];//记录 extern "C" __declspec(dllexport) Point* getPoint(const int M, const int N, const int* top, const int* _board, const int lastX, const int lastY, const int noX, const int noY){ /* 不要更改这段代码 */ int x = -1, y = -1;//最终将你的落子点存到x,y中 int** board = new int*[M]; for(int i = 0; i < M; i++){ board[i] = new int[N]; for(int j = 0; j < N; j++){ board[i][j] = _board[i * N + j]; } } /* 根据你自己的策略来返回落子点,也就是根据你的策略完成对x,y的赋值 该部分对参数使用没有限制，为了方便实现，你可以定义自己新的类、.h文件、.cpp文件 */ //Add your own code below int* _top = new int[N]; for(int i = 0; i < N; i++){ _top[i] =top[i]; } int sdepth = 5; step++; //第一步 if(lastX < 0 || lastX >= M || lastY <0 || lastY >= N){//若先落子,下中间位置 int firsty = N/2;; int firstx = top[firsty]-1; if(firstx == noX && firsty == noY){ firsty--; } return new Point(firstx, firsty); } else if(step == 1){//后手,下在贴近先手第一步 if(lastX != noX && lastY-1 >= 0){ return new Point(M-1, lastY-1); } else if(lastX != noX && lastY+1 < N){ return new Point(M-1, lastY+1); } else if(lastX == noX){ if(lastY-1 == noY && lastY+1 < N) return new Point(M-1, lastY+1); else if(lastY+1 == noY && lastY-1 >= 0) return new Point(M-1, lastY-1); else return new Point(top[lastY]-1, lastY); } } //先判断棋盘是否有能够直接胜利或者对手3连的，直接落子在指定地方 int c = 0, r = 0; //列,行 bool winstep = false; for(c = 0; c < N; c++){ r = _top[c] - 1; if(r >= 0){ winstep = laststep(board, M, N, r, c, 1); if(winstep){ x = r; y = c; clearArray(M, N, _top, board); return new Point(x, y); } } } //基本一样 bool losestep = false; for(c = 0; c < N; c++){ r = _top[c] - 1; if(r >= 0){ losestep = laststep(board, M, N, r, c, 2); if(losestep){ x = r; y = c; clearArray(M, N, _top, board); return new Point(x, y); } } } //建树 Tree* root = new Tree( M, N, 0, 0, _top, board, sdepth, 0, true, false, false, Tree::minval, -1, NULL, NULL, NULL, noX, noY); search(root, f);//搜索 Tree* tmp = root->Child; while(tmp != NULL){ if(root->val == tmp->val){//选定落点 x = tmp->x; y = tmp->y; break; } tmp = tmp->Sibling; } clearTree(root);//清除树 delete root; /* 不要更改这段代码 */ clearArray(M, N, _top, board); return new Point(x, y); } bool laststep(int** board, int M, int N, int r, int c, int sign){//判断是否可直接落子 //横向 int heng = 0; for(int i = c-1; i >= 0; i--){ if(board[r][i] == sign) heng++; else break; } for(int i = c+1; i < N; i++){ if(board[r][i] == sign) heng++; else break; } if(heng >= 3) return true; //纵向(同上) int zong = 0; for(int i = r+1; i < M; i++){ if(board[i][c] == sign) zong++; else break; } if(zong >= 3) return true; //斜向 int xie1 = 0; int i, j; i = r-1; j = c+1; while(i>=0 && j<N){ if(board[i][j] == sign) xie1++; else break; i--; j++; } i = r+1; j = c-1; while(j>=0 && i<M){ if(board[i][j] == sign) xie1++; else break; i++; j--; } if(xie1 >= 3) return true; //斜向(同上) int xie2 = 0; i = r+1; j = c+1; while(i<M && j<N){ if(board[i][j] == sign) xie2++; else break; i++; j++; } i = r-1; j = c-1; while(j>=0 && i>=0){ if(board[i][j] == sign) xie2++; else break; i--; j--; } if(xie2 >= 3) return true; //双三 // + // * * // * * return false; } void search(Tree* tree, int(*f)(Tree*)){//α-β搜索过程 if(tree->ifsure){ //倒推值已经确定 tree->ifcheck = true; if(tree->father != NULL){ if((tree->max && tree->val < tree->father->val) || (!tree->max && tree->val > tree->father->val)){//更新 tree->father->val = tree->val; tree->father->ifcheck = true; tree->clearChild(); } } return; } else{ //倒推值尚未确定 while(!tree->ifsure){ Tree* child = tree->extend(f);//扩展点 if(child == NULL){ if(tree->father != NULL){ if((tree->max && tree->val < tree->father->val) || (!tree->max && tree->val > tree->father->val)){ tree->father->val = tree->val; tree->father->ifcheck = true; } tree->clearChild(); } return; } else{ search(child, f);//递归 if( (tree ->max && child->val > tree->val) || (!tree->max && child->val < tree->val) ){ tree->val = child->val; tree->ifcheck = true; }//if bool g = false; Tree* father = tree->father; //更新所有祖先的val while(father != NULL){ if(father->ifcheck){ if(tree->max && !father->max && father->val <= tree->val){ tree->ifsure = true; if(tree->val < tree->father->val){ tree->father->val = tree->val; tree->father->ifcheck = true; } tree->clearChild(); g = true; break; } if(!tree->max && father->max && father->val >= tree->val){ tree->ifsure = true; if(tree->val > tree->father->val){ tree->father->val = tree->val; tree->father->ifcheck = true; } tree->clearChild(); g = true; break; } } father = father->father; } if(g) break; } } } } extern "C" __declspec(dllexport) void clearPoint(Point* p){ delete p; return; } /* 清除top和board数组 */ void clearArray(int M, int N, int* top, int** board){ delete[] top; for(int i = 0; i < M; i++){ delete[] board[i]; } delete[] board; } /* 添加你自己的辅助函数，你可以声明自己的类、函数，添加新的.h .cpp文件来辅助实现你的想法 */ void clearTree(Tree* root){//清楚树 if(root == NULL){ return; } clearTree(root->Child);//递归清楚 clearTree(root->Sibling); if(root->ndepth != 0){ delete root; } } //策略 int Level[5] = {0, 1, 7, 49,343};//斜线 int henglevel[5] = {0,1,6,36,216};//横向次之 int verlevel[5] = {0, 1, 5, 25, 125};//垂直稍弱 int dflevel[4] = {1, 6, 36, 216};//防守棋 //type 1：程序 2：用户 int cal_two_three(int m, int n, int* top){//2连3 int twothreeval = 1200; double res = 0; for(int c = 0; c < n; c++){ double t = 1.0