写个三子棋的强化学习AI玩玩。写这玩意只需要有一点C语言基础就可以了，至于AI部分，也是很好理解的。
三子棋
在3*3的棋盘中，先手方画O，后手方画X，连成3个就赢了。事实上，只需要很简单的试验，你就会明白，如果双方都走最优解，最后一定是和棋。
让电脑随机下棋显然没有什么意思，那能不能让电脑聪明点呢？
强化学习
强化学习的描述如下，看不太明白没关系，我会举例子的。
强化学习是机器学习的一个分支，它着重于如何让智能系统（称为代理）通过与环境的交互来学习做出最优的决策或者行动。在强化学习中，代理试图通过执行行动并接收环境反馈（通常是奖励）来最大化其累计获得的总奖励。这一过程涉及到学习行动的策略，即在给定的状态下应采取什么行动。
强化学习的核心组成部分包括：
- 代理（Agent）：执行行动的实体，其目标是学习最佳行动序列（策略）以最大化奖励。
- 环境（Environment）：代理所处并与之交互的系统或问题域。环境根据代理的当前状态和执行的行动，反馈新的状态和奖励。
- 状态（State）：环境的一个描述，代理根据状态做出决策。
- 行动（Action）：代理可以执行的操作。
- 奖励（Reward）：环境对代理执行行动的即时反馈，指导学习过程。
强化学习的学习过程通常涉及探索（尝试新行动以了解它们的效果）和利用（使用已知的信息来获得最大奖励）之间的平衡。这一平衡的目标是发现最优策略，即一个从状态到行动的映射，使得累积奖励最大化。
强化学习在多个领域有广泛的应用，如自动驾驶汽车、游戏、机器人导航和控制、推荐系统等。与其他类型的机器学习不同，强化学习不是直接从数据集学习，而是通过试错和适应环境的反馈来学习。
下面我来谈谈最简单的强化学习，在三子棋中的应用。虽然有点杀鸡用牛刀的嫌疑，但这是个很好的例子。
电脑是很笨的，它只知道游戏规则：只有空位才能下棋、一人一步、连成3个获胜……如果你不告诉它下棋的思路，它就只会随机下。
状态
棋局在某个时刻，会有一个状态：
我们可以用3*3的二维数组来描述，即：
0 0 1
0 1 0
2 1 2
其中0表示空位，1表示先手方的O，2表示后手方的X。
如果我把这个二维数组从右向左、从下到上排成一排，得到212010100，这是一个只由012组成的数字，可以看作三进制，即，再转换为十进制int即可。如果要从这个整数还原棋局的状态，只需要重新转换成三进制，再填到二维数组中。
这样，我们成功地用int来描述棋局的状态。棋局所有可能的状态，不超过种，实际还要更少，因为有一些情况是达不到的。
int GetState(int board[3][3])
{
int state = 0;
// 转换为3进制数
for (int i = 2; i >= 0; --i)
{
for (int j = 2; j >= 0; --j)
{
state = state * 3 + board[i][j];
}
}
return state;
}
void StateToBoard(int state, int board[3][3])
{
// 还原三进制整数
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
board[i][j] = state % 3;
state /= 3;
}
}
}
行动
在某个状态下，比如：
此时轮到X走，假设棋盘的9个位置分别是：
0 1 2
3 4 5
6 7 8
显然二维数组的第x行第y列（x、y从0开始）表示数字n=x*3+y，而x=n/3，y=n%3。
那么对于上图中的棋局状态，X所有可能的走法就是：0,1,3,5。这样，我们就用一个整数表示了某个状态下的行动。
分数
某个状态下的某个行动都可以赋一个得分，这个分数越高，表示这个行动是越有利的。那么如何准确得到每个状态下的每个行动的分数呢？
我们可以这样初始化分数：
- 如果这步棋走完后能直接获胜，分数为1
- 如果这步棋走完后和棋，或者棋局未结束，分数为0.5
- 如果这步棋不能走（位置已被占用），分数为-1
static void _InitValue(value_t value)
{
for (int state = 0; state < STATES_CNT; ++state)
{
// 把状态转换为棋盘
int board[3][3] = { 0 };
StateToBoard(state, board);
// 根据走棋后的状态，初始化分数
for (int point = 0; point < 9; ++point)
{
int tmpBoard[3][3] = { 0 };
memcpy(tmpBoard, board, 9 * sizeof(int));
if (Move(tmpBoard, point / 3, point % 3))
{
int res = IsWin(tmpBoard);
// 赢 - 1
// 和棋 - 0.5
// 棋局未结束 - 0.5
if (res == 1 || res == 2)
value[state][point] = 1;
else
value[state][point] = 0.5;
}
else
{
// 该位置非法
value[state][point] = -1;
}
}
}
}
你可能会问，那如果这步棋走完后输了呢？emmm，这种可能不存在！注意这里只表示走一步棋的分数。如果这步棋走完后几步真的会输，那么分数应该为0，这点后面会讲。这样，如果这个位置没有违反规则，分数就在[0,1]的范围内。
我们可以用一个二维数组来存储所有状态下的所有行动的得分。二维数组的行标表示棋局状态（前面已经用整数描述状态了，为0-1），列标（0
显然，这个分数是不准确的，有可能这步棋很烂，但分数却是0.5，这就需要让AI强化学习了。
奖励
我们让电脑自己和自己下棋，每一步都选择当前状态下分数最高的位置，如果分数相同（比如一开始的9个位置分数都是0.5），就随机选择一个位置。
int BestMove(int board[3][3], value_t value)
{
// 选择value最大的走法
// 找到最大的value
int state = GetState(board);
double maxVal = -1;
int point = 0;
for (int i = 0; i < 9; ++i)
{
if (value[state][i] > maxVal)
maxVal = value[state][i];
}
// 有可能的最优走法
bool moves[9] = { 0 };
// 找到所有和最大value接近的value
for (int i = 0; i < 9; ++i)
{
if (value[state][i] > maxVal - 0.01)
moves[i] = true;
}
// 在moves里随机选择一个最优走法
while (true)
{
int point = rand() % 9;
if (moves[point])
return point;
}
}
最终，会产生一个结果。有可能是先手方O赢了，也有可能是后手方X赢了，还有可能是和棋。
让电脑吸取经验教训，也就是给奖励，也可以是惩罚。
具体的做法是，从最后一步往前推，更新每一步的分数。我们规定：
- 如果是某一方赢了，那么最后一步棋的得分就是1（这点和前面分数的初始化保持一致），而倒数第二步棋是输的那方下的，这步棋的得分设置成0，因为是这步棋直接导致了输棋。
- 如果是和棋，那么最后一步棋的得分就是0.5（这点和前面分数的初始化保持一致），而倒数第二步棋是另一方下的，这步棋的得分设置成0.5，因为是这步棋直接导致了和棋。
那么倒数第三步和倒数第一步是同一方下的。倒数第三步的新的分数=倒数第三步的旧的分数+0.1*(倒数第一步的新的分数-倒数第三步旧的分数)。
同理，倒数第四步和倒数第二步是同一方下的。倒数第四步的新的分数=倒数第四步的旧的分数+0.1*(倒数第二步的新的分数-倒数第四步旧的分数)。
接下来是倒数第五步、倒数第六步……一直到正数第一步。这样，这盘棋出现的状态中，对于走过的行为，就有了新的分数，这就是强化学习！
根据前面的计算方式，很容易知道，如果这步棋是合法的，那么分数就在[0,1]之间。如果某一方赢了，该方最后一步的得分为1，那么前面的每一步分数都会增加，因为该方后一步的分一定比前一步高，这就是奖励。而如果某一方输了，该方最后一步的得分为0，那么前面的每一步分数都会减少，因为该方后一步的分一定比前一步低，这就是惩罚。
注意到更新的分数乘了0.1，这样越往前的分数，变动的幅度就越小，这也是合理的，因为越接近棋局开始，走棋的影响就越小。
经过大量的对局后，所有状态下的行为的得分就会更加准确，无限趋近于理论值。然而，为了防止出现局部最优，也就是AI自我感觉良好，最好让AI有一定的概率随机走棋，而不是每次都选择最优走法。
以下是一次强化学习：
void QLearning(value_t value)
{
// 棋盘
int board[3][3] = { 0 };
// 下棋的状态数组
int states[9] = { 0 };
// 下棋的位置数组
int points[9] = { 0 };
// states和point数组记录的状态数量
int size = 0;
// 记录state
int state = 0;
// 记录胜负和
// 0 - 未分胜负
// 1 - 先手方获胜
// 2 - 后手方获胜
// 3 - 和棋
int res = 0;
// 下一盘棋
while (true)
{
// 计算并保存新的状态
state = GetState(board);
states[size] = state;
// 一定概率随机走棋
// 否则选择value最大的走法
if (rand() % 10 < 3)
{
while (true)
{
// 随机走棋
int x = rand() % 3;
int y = rand() % 3;
if (Move(board, x, y))
{
// 保存当前point
points[size++] = x * 3 + y;
break;
}
}
}
else
{
// 选择value最大的走法
// 找到最大的value和对应的point
int point = BestMove(board, value);
// 在point位置下棋
Move(board, point / 3, point % 3);
// 保存point
points[size++] = point;
}
// 棋局是否结束
if (res = IsWin(board))
break;
}
// 根据这盘棋的信息，总结经验
// 不考虑最后一步
--size;
// 倒数第二步直接导致输棋或和棋
// 输棋分数设为0
// 和棋分数设为0.5
value[states[size - 1]][points[size - 1]]
= (res == 3 ? 0.5 : 0);
--size;
// 从倒数第三步开始，每一步的分数更新为
// 原来的分数 + 0.1 * (后两步的分数-原来的分数)
while (size > 0)
{
value[states[size - 1]][points[size - 1]]
= value[states[size - 1]][points[size - 1]]
+ 0.1 * (value[states[size + 1]][points[size + 1]]
- value[states[size - 1]][points[size - 1]]);
--size;
}
}
这里举个实际的例子，比如下面的对局（这里是我跟电脑的对局，实际强化学习时可以是电脑自己和自己下，也可以是人类和电脑下）：
这盘棋总共下了7步，就分出了胜负。假设这场对局之前，除了最后一步棋的分数是1之外，其余的走法分数都是0.5。那么，value数组中，这7步的得分一开始是：
0.5 0.5 0.5 0.5 0.5 0.5 1
倒数第二步棋直接导致输棋，分数更新为0。
0.5 0.5 0.5 0.5 0.5 0 1
接着更新倒数第三步棋的分数，要加上倒数第一步棋的分数（1）和自己（0.5）的差的0.1倍，即0.05，更新后的分数为0.55。
0.5 0.5 0.5 0.5 0.55 0 1
接着更新倒数第四步棋的分数，要加上倒数第二步棋的分数（0）和自己（0.5）的差的0.1倍，即-0.05，更新后的分数为0.45。
0.5 0.5 0.5 0.45 0.55 0 1
接着更新倒数第五步棋的分数，要加上倒数第三步棋的分数（0.55）和自己（0.5）的差的0.1倍，即0.005，更新后的分数为0.505。
0.5 0.5 0.505 0.45 0.55 0 1
同理更新前2步的分数：
0.5005 0.495 0.505 0.45 0.55 0 1
这就是一次强化学习。最终训练的结果，也就是value数组只需要保存到文件中，需要对局时再从文件中读取数据，这样就不用每次都重新训练了。
void SaveValue(value_t value)
{
FILE* fin = fopen("value.dat", "wb");
if (fin == NULL)
{
perror("fopen");
exit(2);
}
// 保存value
fwrite(value, sizeof(double), 177147, fin);
fclose(fin);
fin = NULL;
}
bool LoadValue(value_t value)
{
FILE* fout = fopen("value.dat", "rb");
// 没有这个文件
if (fout == NULL)
return false;
// 加载value
fread(value, sizeof(double), 177147, fout);
fclose(fout);
fout = NULL;
return true;
}
完整代码
已上传至gitee链接
版权归原作者 努力学习游泳的鱼 所有， 如有侵权，请联系我们删除。