搜索

弈悟计划——大一C程期末实验之五子棋AI的开发日志


发布时间: 2022-11-25 00:01:01    浏览次数:47 次

写在前面

大一C程的期末作业,因为觉得从头学C太没意思,因此报了学校的什么挑战班(早知道不换了去混绩点了)

由于本人懒得要死,刚开始想手搓GUI,然后看了各种图形界面感觉徒增烦恼,就随便找了个看起来最简单的EasyX使用

不过自己码到一半(其实才写了一百行不到)就破防了,感觉再这样下去一个GUI就够我写到学期结束了

遂在网上找了个五子棋图形界面的GUI模板,简单改了一下就只要写核心算法部分就好了

平时由于时间问题,不太能抽出时间写这个,一般就在课上慢慢写了,不过由于写过类似的棋类的OI题(好像是紫书上的),感觉应该会是一段不错的经历

由于要统一代码风格,因此放上来的代码都是格式化过的

然后由于要求要用多文件,因此我很粗暴地分了三个文件再Dev里开了个工程跑(其实分了和没分一样)

其中有两个不变的先放出来

main.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "YiWu.h"

int main() {
    Menu m;
    m.Display();
    return 0;
}

Yiwu.h

#include <graphics.h>
#include <conio.h>
#include <windows.h>
#define _CRT_SECURE_NO_WARNINGS 1

class Menu {
public:
    void Display();
    void ChessBoard(MOUSEMSG m);
};

class Play {
public:
    void TwoPlayerGame(MOUSEMSG m);
    void ComputerUserGame(MOUSEMSG m);
    void buttonRingth(MOUSEMSG m, MOUSEMSG ms, int win); //判断是否点击右侧工具栏
    void displayWin(int n1, int
                    n2);//显示哪一方赢了,n1为0表示双人为1表示人机,n2为0表示黑、人为1表示白、机
    void PlayGame(MOUSEMSG ms);
    int Win();
};

剩下的就是最关键的Yiwu.cpp了,其实应该再细分一下功能的,但是我太懒了就不管了

最后关于这个名字,我取的中文名叫弈悟(不是15!不是15!),算是致敬一波沉迷云顶的洁宝了


大致思路

  • GUI部分:魔改一下板子,图片找不到来源就用画图搓一下
  • 双人对战部分:这部分其实不要求的,但是那个板子里有就顺带留下来了
  • AI部分:重中之重,目前考虑如下(一些具体的部分下面日志里会写):
    • 启发式搜索(评估函数),预期实现6层的棋力
    • alpha-beta剪枝
    • 蒙特卡洛树(待定)
    • Zobrist优化状态数(待定)
    • 迭代加深与算杀(待定)
  • 希望能达到薄纱我的水平wwwwww

开发日志

2022/11/8

魔改UI没什么好说的,主要是修剪图片大小让棋能刚好落在点上

刚开始搞了半天去不掉水印,索性直接摆烂了

然后由于用画图截的辣鸡图差了几个像素点那个棋下不到格点上,魔改参数又花了好久

折腾了一晚上终于算是能下了,顺带保留了原来的板子的双人对战模式

2022/11/15

写了评估函数以及找合法落点的函数

首先我的评估算法也很simple,就是分别考虑六个方向,然后根据在这个方向上的棋型来评分:

  • 成五,100000000
  • 活四,10000
  • 活三,1000
  • 活二,100
  • 活一,10

而对于有一边被其它棋子堵住(或者被边界堵住)的棋子,则对应的分数降一档:

  • 死四,1000
  • 死三,100
  • 死二,10

但是写完之后发现我的评估函数有点问题,比如”黑白白白空白黑“会被算成死三而不是冲五,下次要记得修改下

最后写了个找合法落点的函数,因为我们要下的点一般都是在现有棋局的附近,不会跑的太远

因此我们规定每次落子的位置在距离它切比雪夫距离\(2\)的范围内要有棋子(不论敌我)

然后我们把这些位置按分数排序后开搜即可


2022/11/22

今天开始把alpha-beta剪枝的初代版本基本完成了,大体上还是能跑一下的

不过由于选点的估价函数我直接用全局的那个了,而那个跑一次复杂度就是\(O(16^3)\)的,还有大常数

所以下次要再写一个针对每次下的单个点的估价函数,不然真吃不消这复杂度

而且经过我的研究那个所谓的切比雪夫距离小于等于\(2\)根本跑不动,遂放弃成小于等于\(1\)的情形

但是即使这样我的初代版本还是薄纱了我两次,让我深刻意识到我五子棋水平的低下

下次应该会得到一个毕竟可观的版本,到时候找别人测试一下大概强度然后决定要再加哪些优化吧

免责声明 弈悟计划——大一C程期末实验之五子棋AI的开发日志,资源类别:文本, 浏览次数:47 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-25 12:01:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/cjjsb/p/16916618.html