本文设计了一种基于落地打分的井字棋下棋算法，能够实现电脑不败，所以如果玩家会玩的话，一般是平局。
算法核心
电脑根据对落子位置的打分，选择分数最高的位置，若不同落点分数相同则随机选择位置（随机选择就不会显得那么呆板）
所以怎么打分是关键！
基本思想是，判断落点附近的位置的棋子类型，进行打分，进一步解释，根据井字棋的规则，横、竖、对角连成三子则判获胜，所以每一个落点和与他同一横、竖、对角的棋子类型有关。所以我们可以指定一个打分表如下：
C代表己方棋子（电脑），P代表对方（玩家）棋子，空代表没有棋子
| 类型 | 得分 |
|---|---|
| C+C | 100 |
| P+P | 50 |
| C+空 | 6 |
| P+空 | 4 |
| 空+空 | 2 |
| P+C | 1 |
简单解释一下，C+C表示己方已经有2个棋子了，下一步马上可以赢，给最高分，且其他分数相加不会超过100分。同理P+P是50分，如果不存在C+C情况，那么50分将是最高分，其他分数相加不会超过。
C+空和P+空的分数高低取决于电脑是进攻型还是防守型，但是他们分数一定不能相差太多。
这里举个例子说明得分怎么计算
我们计算黄色方格的得分为 横(C+空)+竖（C+空）+对角(P+空）=6+6+4=16。橙色方格得分为横(C+空)+竖（P+空）+对角(P+空）=6+4+4=14。所以电脑会选择走黄色方格。
也就是说，最终每个可以下的格子的打分等于横、竖、对角的打分之和，若没有对角线，则对角线为0分。
核心算法介绍如上，接下来是实现。
代码实现
代码大致可分为三个模块，制定井字棋基本操作和规则、电脑下棋、界面打印。
井字棋下棋规则
我们创建一个SZQ_basic.c文件，在头文件SZQ_basic.h进行相关的定义和声明。
//`SZQ_basic.h` #include<stdio.h> #include <string.h> #include<stdlib.h> #define N 3 #define P_pawn 'o' //玩家棋子 o #define C_pawn 'X' //电脑棋子 X char** creatQP(); //创建棋盘 void printQP(char** QP); //打印棋盘 int inputQZ(char** QP, int row, int column); //输入棋子 int isPlayerWin(char** QP); //判断胜负 int isQPFull(char** QP); //判断平局 基本思想是，通过二维数char[3][3]组存储棋子，空位置则用空格符填充，输入棋子时判断是不是空格符，如果是才可以输入（下棋）。
判断胜负的返回值包括 1 ，0 ， -1，分别表示玩家胜，未结束，电脑胜。平局则是通过判断棋盘是否满，遍历二维数组看是否还有空格符就可以了。
-
创建棋盘
/* * @brief creat chequer */ char** creatQP() { char** QP; QP = (char**)malloc(sizeof(char*) * N); if (QP == NULL) return NULL; for (int i = 0; i < N; i++) { QP[i] = (char*)malloc(sizeof(char) *N); if (QP[i] == NULL) return NULL; memset(QP[i], ' ', sizeof(char)*N); } return QP; } -
打印棋盘
/* * @brief printf Chequer * @para 棋盘地址 */ void printQP(char** QP) { if (QP == NULL) { printf("print Chequer failed!"); return; } puts("|_____________________________ 棋盘 ___________________________|"); printf("tt 行号→ 1 2 3tt玩家棋子：“o”ntt 列号↓tttt电脑棋子：“X”n"); printf("tt |---|---|---|n"); for (int i = 0; i < N; i++) { printf("tt %d|", i + 1); for (int j = 0; j < N; j++) { printf(" %c |", QP[i][j]); } printf("n"); printf("tt |"); for (int j = 0; j < N; j++) { printf("---|"); } printf("n"); } puts("|--------------------------------------------------------------------|"); } -
输入棋子
int inputQZ(char** QP, int row, int column) { if (row < 0 || row>2 || column < 0 || column>2) { printf("输入棋子位置不合法！n请重新输入：>>"); return 0; } if (QP[row][column] != ' ') { printf("该位置已有棋子！n请重新输入：>>"); return 0; } QP[row][column] = P_pawn; return 1; } -
判断棋盘满
/* * brief 判断棋盘是否满了，满了即平局 */ int isQPFull(char** QP) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (QP[i][j] ==' ') return 0; } } return 1; } -
判断胜负
/* *@brief 判断游戏是否结束（玩家获胜？） *@ret 1:玩家胜 0：游戏未结束 -1：玩家败 */ int isPlayerWin(char** QP) { int flag = 0; //判断行成线 for (int i = 0; i < N; i++) { if (QP[i][0] == QP[i][1] && QP[i][0] == QP[i][2] && QP[i][0] == C_pawn) flag = -1; else if (QP[i][0] == QP[i][1] && QP[i][0] == QP[i][2] && QP[i][0] == P_pawn) flag = 1; } //判断列成线 for (int j = 0; j < N; j++) { if (QP[0][j] == QP[1][j] && QP[0][j] == QP[2][j] && QP[0][j] == C_pawn) flag = -1; else if (QP[0][j] == QP[1][j] && QP[0][j] == QP[2][j] && QP[0][j] == P_pawn) flag = 1; } //判断正对角成线 if (QP[0][0] == QP[1][1] && QP[0][0] == QP[2][2] && QP[0][0] == C_pawn) flag = -1; else if (QP[0][0] == QP[1][1] && QP[0][0] == QP[2][2] && QP[0][0] == P_pawn) flag = 1; //判断反对角成线 if (QP[0][2] == QP[1][1] && QP[0][2] == QP[2][0] && QP[0][2] == C_pawn) flag = -1; else if (QP[0][2] == QP[1][1] && QP[0][2] == QP[2][0] && QP[0][2] == P_pawn) flag = 1; return flag; }
电脑下棋算法
接下来创建SZQ_engine.c源文件实现电脑下棋，头文件相关的函数声明如下
#include <time.h> #include "SZQ_basic.h" int computerPlay(char** QP); int row_score(char** QP, int row); int column_score(char** QP, int column); int Pdiag_score(char** QP, int postion); int Ndiag_score(char** QP, int postion); 文件一共包含5个函数，含score的函数是计算在行、列、正对角、反对角情况下的得分，因为每一个落点位置最多只有这四种情况叠加（中心点位置特殊，这四种情况都有），所以只要把每种情况的得分相加，computerPlay函数负责汇总和确定落点，以及下棋。
还是以这个图为例，黄色方格由于只有行、列、正对角，没有反对角，所以反对角分数为0，其他大于0。具体是多少分还得参考打分表。
为了方便，我们将打分表以数组形式存储。三个不同字符，任意两个相加，得到的数一定不会出现相同的，可以通过数学证明。
int scoretable[6][2] = { {C_pawn + C_pawn,50}, {P_pawn + P_pawn,30}, {C_pawn + ' ',6}, {P_pawn + ' ',4}, {' ' +' ',2}, {P_pawn + C_pawn,1}, }; -
行得分计算
int row_score(char** QP,int row){ int score=0; int type = 0; for (int i = 0; i < N; i++) { type = QP[row][i] + type; } //将落点对应那一行三个位置的字符相加，减去自身的空字符，得到类型type type = type - ' '; //查询打分表，type类型的对应得分score for (int k = 0; k < 6; k++) { if (scoretable[k][0] == type) { score = scoretable[k][1]; break; } } return score; } -
列得分计算
int column_score(char** QP, int column) { int score = 0; int type = 0; //将落点对应那一列三个位置的字符相加，减去自身的空字符，得到类型type for (int i = 0; i < N; i++) { type = QP[i][column] + type; } type = type - ' '; //查询打分表，type类型的对应得分score for (int k = 0; k < 6; k++) { if (scoretable[k][0] == type) { score = scoretable[k][1]; break; } } return score; } -
正对角得分计算
int Pdiag_score(char** QP, int postion) { int score = 0; int type ; //判断该位置是否存在正对角情况 if (postion/N==postion%N) { //若存在，同样的将落点对应那一正对角三个位置的字符相加，减去自身的空字符，得到类型type type = QP[0][0] + QP[1][1] + QP[2][2]; type = type - ' '; //查询打分表，type类型的对应得分score for (int k = 0; k < 6; k++) { if (scoretable[k][0] == type) { score = scoretable[k][1]; break; } } } return score; } -
反对角计算得分
int Ndiag_score(char** QP, int postion) { int score = 0; int type; //判断该位置是否存在反对角情况，自行证明反对角满足(postion / N+postion % N)==2 if ((postion / N+postion % N)==2) { type = QP[0][2] + QP[1][1] + QP[2][0]; type = type - ' '; for (int k = 0; k < 6; k++) { if (scoretable[k][0] == type) { score = scoretable[k][1]; break; } } } return score; } -
接下来是汇总分数，确定落点
int computerPlay(char** QP) { int index=0; int score = 0; for (int i = 0; i < N*N; i++) { int temp_score = 0; //遍历棋盘，并且找出空格符，即可落子的位置，计算分数 if (QP[i / N][i % N] == ' ') { //把4种情况的分数相加得到总分数 temp_score = row_score(QP, i/N) + column_score(QP, i%N) + Pdiag_score(QP, i) + Ndiag_score(QP, i); if (temp_score > score) //取分数最大值 { score = temp_score; index = i; } else if (temp_score == score) //若分数相同，在两个随机选择一个位置作为落点 { srand((unsigned)time(NULL)); index=(rand() % 2)? i:index; } } } return index; }注意返回值是索引，就是把二维数组当一维数组，方便遍历和返回位置（二维数组行号和列号是两个值，不方便返回）。因此返回后需要根据索引index确定行和列。
行：index / N
列：index % N
打印棋盘界面
最后，我们把棋盘界面打印，就可以大功告成了。
这里我使用延时函数模拟电脑思考过程，不然打印太快了，没意思hhh。然后玩家也可以自行选择先手和后手。
这部分比较简单，C语言基础语法，直接把代码放下面。
#define _CRT_SECURE_NO_WARNINGS #include <windows.h> #include "SZQ_engine.h" #include "SZQ_basic.h" int main() { //printf("%d", C_pawn+C_pawn); int hang, lie; int cmd = 1; int position; char** TicTacToe = creatQP(); puts("______________________________________________________________________"); puts("|*********************** Tic-Tac-Logic (game) ***********************|"); puts("|** author:gofan-SiTu ***********************************************|"); puts("|************************ 请选择以下功能 *************|"); puts("|************************ 0：退出游戏 ***********|"); puts("|************************ 1：作为先手开始与电脑对弈 ***********|"); puts("|************************ 2：作为后手开始与电脑对弈 ***********|"); puts("|********************************************************************|"); puts("|——————————————————————————————————|"); printf(">请输入对应序号：>>"); scanf_s("%d", &cmd); switch (cmd) { case 0: exit(0); case 1: printf(">您选择与电脑对弈，落子时请输入行号和列号确定位置，中间用空格隔开n"); printf(">您的棋子是“o”,电脑的棋子是“X”n"); printQP(TicTacToe); printf(">您先走棋 "); while (1) { printf(">请输入您的下一步落子位置：>>"); do { scanf_s("%d%d", &hang, &lie); } while (!inputQZ(TicTacToe, hang - 1, lie - 1)); printf(">您走棋后，棋盘如下n"); printQP(TicTacToe); if (isPlayerWin(TicTacToe) == 1) { printf("n>！恭喜玩家获胜 ！<n > 您太强了 <n"); break; } else if (isPlayerWin(TicTacToe) == -1) { printf("n > 电脑获胜 < n >！你太菜拉！< n"); break; } else if (isQPFull(TicTacToe)) { printf(" >！平局 ！< n"); break; } position = computerPlay(TicTacToe); printf(" 电脑正在思考......n"); Sleep(1000); printf(">电脑的落子位置：>>%d %dn>电脑落子后，棋盘如下n", position / N + 1, position % N + 1); TicTacToe[position / N][position % N] = C_pawn; Sleep(100); printQP(TicTacToe); if (isPlayerWin(TicTacToe) == 1) { printf("n>！恭喜玩家获胜 ！<n > 您太强了 <n"); break; } else if (isPlayerWin(TicTacToe) == -1) { printf("n > 电脑获胜 < n >！你太菜拉！< n"); break; } else if (isQPFull(TicTacToe)) { printf(" >！平局 ！< n"); break; } } break; case 2: printf(">您选择与电脑对弈，落子时请输入行号和列号确定位置，中间用空格隔开n"); printf(">您的棋子是“o”,电脑的棋子是“X”n"); printf(">电脑先走棋n"); while (1) { position = computerPlay(TicTacToe); printf(" 电脑正在思考......n"); Sleep(1000); printf(">电脑的落子位置：>>%d %dn>电脑落子后，棋盘如下n", position / N + 1, position % N + 1); TicTacToe[position / N][position % N] = C_pawn; Sleep(250); printQP(TicTacToe); if (isPlayerWin(TicTacToe) == 1) { printf("n>！恭喜玩家获胜 ！<n > 您太强了 <n"); break; } else if (isPlayerWin(TicTacToe) == -1) { printf("n > 电脑获胜 < n >！你太菜拉！< n"); break; } else if (isQPFull(TicTacToe)) { printf(" >！平局 ！< n"); break; } printf(">请输入您的下一步落子位置：>>"); do { scanf_s("%d%d", &hang, &lie); } while (!inputQZ(TicTacToe, hang - 1, lie - 1)); printf(">您走棋后，棋盘如下n"); printQP(TicTacToe); if (isPlayerWin(TicTacToe) == 1) { printf("n>！恭喜玩家获胜 ！<n > 您太强了 <n"); break; } else if (isPlayerWin(TicTacToe) == -1) { printf("n > 电脑获胜 < n >！你太菜拉！< n"); break; } else if (isQPFull(TicTacToe)) { printf(" >！平局 ！< n"); break; } } break; default: printf(">输入序号不准确，程序异常退出！n 请重新启动！"); exit(-1); } printf("n 游戏结束！ n"); for (int i = 0; i < N; i++) free(TicTacToe[i]); free(TicTacToe); for (int i = 5; i >= 0; i--) { printf("程序将在%ds后关闭...n", i); Sleep(1000); } return 0; } 结果
目前这个算法可以实现电脑不败，当然，这个打分表也是我经过分析、筛选确定的分数，比较合理。但是如果把这思想拓展到五子棋上，似乎不太行，至少我现在还没想到思路，因为五子棋比井字棋复杂得多了，而且棋盘很大，就不能简单的对落点位置的附近棋子类型打分，就算可以，判断规则也相当复杂。所以结论就算，这个算法只适合井字棋子棋这种简单的类型。
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
