1 Star 0 Fork 1

衣陈/EasyX2048

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
Loading...
README

衣陈的Easyx2048

框架

vs2022+EasyX

核心算法

1.批量加载图像资源

//为成员属性IMAGE绑定图片,基于命名规律批量得到文件名string,并转为char[]
void Easyx::loadimg()
{
	int ans = 0;
	for (int i = 1; i <= 2048; i *= 2)
	{
		string s = to_string(i);
		s += ".png";
		char Filename[10];
		for (int i = 0; i < s.size(); i++)
		{
			Filename[i] = s[i];
		}
		Filename[s.size()] = '\0';
		loadimage(img + ans, Filename);
		ans++;

	}
}

2.newelem算法

//用两个一维数组线性记录map空白处坐标,取rand()%ans th坐标置2
void MAP::newelem()
{
	int x[16] = { -1,-1,-1,-1,-1,-1,-1,-1 ,-1,-1,-1,-1 ,-1,-1,-1,-1 }, y[16] = { -1,-1,-1,-1 ,-1,-1,-1,-1 ,-1,-1,-1,-1 ,-1,-1,-1,-1 };
	int ans = 0;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (map[i][j] == 1)
			{
				x[ans] = i; y[ans] = j;
				ans++;
			}
		}
	}
	if (ans)
	{
		int pos = rand() % ans;
		map[x[pos]][y[pos]] = 2;
	}
}

3.move算法

//移动逻辑:遇到1冒泡前进,遇到相同merge
void MAP::move(char ch)
{
	switch (ch) {
	case'w':
		for (int j = 0; j < 4; j++)
		{
			for (int i = 1; i < 4; i++)
			{
				if (map[i][j] == 1) continue;
				int pos = i;
				for (; pos > 0; pos--)
				{
					if (map[pos][j] == map[pos - 1][j])
					{
						map[pos - 1][j] *= 2;
						map[pos][j] = 1;
						break;
					}
					if (map[pos - 1][j] != 1 && map[pos - 1][j] != map[pos][j]) break;

					if (map[pos - 1][j] == 1) swap(map[pos][j], map[pos - 1][j]);
				}

			}
		}
		break;
	case's':
		for (int j = 0; j < 4; j++)
		{
			for (int i = 2; i >= 0; i--)
			{
				if (map[i][j] == 1) continue;
				for (int pos = i; pos < 3; pos++)
				{
					if (map[pos][j] == map[pos + 1][j])
					{
						map[pos + 1][j] *= 2;
						map[pos][j] = 1;
					}

					if (map[pos + 1][j] != 1 && map[pos + 1][j] != map[pos][j]) break;

					if (map[pos + 1][j] == 1) swap(map[pos][j], map[pos + 1][j]);
				}
			}
		}
		break;
	case'a':
		for (int i = 0; i < 4; i++)
		{
			for (int j = 1; j < 4; j++)
			{
				if (map[i][j] == 1) continue;
				for (int pos = j; pos > 0; pos--)
				{
					if (map[i][pos] == map[i][pos - 1])
					{
						map[i][pos - 1] *= 2;
						map[i][pos] = 1;
					}

					if (map[i][pos - 1] != 1 && map[i][pos - 1] != map[i][pos]) break;

					if (map[i][pos - 1] == 1) swap(map[i][pos], map[i][pos - 1]);
				}

			}
		}
		break;
	case'd':
		for (int i = 0; i < 4; i++)
		{
			for (int j = 2; j >= 0; j--)
			{
				if (map[i][j] == 1) continue;
				for (int pos = j; pos < 3; pos++)
				{
					if (map[i][pos] == map[i][pos + 1])
					{
						map[i][pos] = 1;
						map[i][pos + 1] *= 2;
					}

					if (map[i][pos + 1] != 1 && map[i][pos + 1] != map[i][pos]) break;

					if (map[i][pos + 1] == 1) swap(map[i][pos], map[i][pos + 1]);
				}
			}
		}
		break;
	default:
		char reinput = _getch();
		this->move(reinput);
		break;
	}
}

关于EasyX

  • 如何将png嵌入exe,如何将IMAGE绑定资源文件?

冲浪Easyx官方文档 <img alt="image-20220812232437782">

image-20220812232353876

失败了,原因待究

关于帧率控制

#include<time.h>
clock_t begintime=clock();//时间变量,右函数返回程序运行指此函数时的时间,单位为毫秒
clock_t fortime=clock()-begintime();
//用Sleep函数补足空白时间,完成帧率控制

关于2048AI算法冲浪

2048本质上可以抽象成信息对称双人对弈模型(玩家向四个方向中的一个移动,然后计算机在某个空格中填入2或4)。这里“信息对称”是指在任一时刻对弈双方对格局的信息完全一致,移动策略仅依赖对接下来格局的推理。作者使用的核心算法为对弈模型中常用的带Alpha-beta剪枝的Minimax。这个算法也常被用于如国际象棋等信息对称对弈AI中。

Minimax Search和Alpha Beta Pruning的实现

private SearchResult search(int depth, double alpha, double beta, int positions, int cutoffs) {
    double bestScore;
    int bestMove = -1;
    SearchResult result = new SearchResult();
    int[] directions = {0, 1, 2, 3};

    if (this.grid.playerTurn) {  // Max 层
        bestScore = alpha;
        for (int direction : directions) {  // 玩家遍历四个滑动方向,找出一个最好的
            GameState newGrid = new GameState(this.grid.getCellMatrix());
            if (newGrid.move(direction)) {
                positions++;
//                if (newGrid.isWin()) {
//                    return new SearchResult(direction, 10000, positions, cutoffs);
//                }
                AI newAI = new AI(newGrid);
                newAI.grid.playerTurn = false;

                if (depth == 0) { //如果depth=0,搜索到该层后不再向下搜索
                    result.move = direction;
                    result.score = newAI.evaluate();
                } else { //如果depth>0,则继续搜索下一层,下一层为电脑做出决策的层
                    result = newAI.search(depth - 1, bestScore, beta, positions, cutoffs);
                    if (result.score > 9900) { // 如果赢得游戏
                        result.score--; // 轻微地惩罚因为更大的搜索深度
                    }
                    positions = result.positions;
                    cutoffs = result.cutoffs;
                }

                //如果当前搜索分支的格局分数要好于之前得到的分数,则更新决策,同时更新bestScore,也即alpha的值
                if (result.score > bestScore) {
                    bestScore = result.score;
                    bestMove = direction;
                }
                //如果当前bestScore也即alpha>beta时,表明这个节点下不会再有更好解,于是剪枝
                if (bestScore > beta) {
                    cutoffs++;  //剪枝
                    return new SearchResult(bestMove, beta, positions, cutoffs);
                }
            }
        }
    } else {
        // Min 层,该层为电脑层(也即我们的对手),这里我们假设对手(电脑)足够聪明,总是能做出使格局变到最坏的决策
        bestScore = beta;

        // 尝试给每个空闲块填入2或4,然后计算格局的评估值
        List<Candidate> candidates = new ArrayList<>();
        List<int[]> cells = this.grid.getAvailableCells();
        int[] fill = {2, 4};
        List<Double> scores_2 = new ArrayList<>();
        List<Double> scores_4 = new ArrayList<>();
        for (int value : fill) {
            for (int i = 0; i < cells.size(); i++) {
                this.grid.insertTitle(cells.get(i)[0], cells.get(i)[1], value);
                if (value == 2) scores_2.add(i, -this.grid.smoothness() + this.grid.islands());
                if (value == 4) scores_4.add(i, -this.grid.smoothness() + this.grid.islands());
                this.grid.removeTile(cells.get(i)[0], cells.get(i)[1]);
            }
        }

        // 找出使格局变得最坏的所有可能操作
        double maxScore = Math.max(Collections.max(scores_2), Collections.max(scores_4));
         for (int value : fill) {
             if (value == 2) {
                 for (Double fitness : scores_2) {
                    if (fitness == maxScore) {
                        int index = scores_2.indexOf(fitness);
                        candidates.add(new Candidate(cells.get(index)[0], cells.get(index)[1], value));
                    }
                 }
            }
            if (value == 4) {
                for (Double fitness : scores_4) {
                    if (fitness == maxScore) {
                        int index = scores_4.indexOf(fitness);
                        candidates.add(new Candidate(cells.get(index)[0], cells.get(index)[1], value));
                    }
                }
            }
        }

        // 然后遍历这些操作,基于这些操作向下搜索,找到使得格局最坏的分支
        for (int i = 0; i < candidates.size(); i++) {
            int pos_x = candidates.get(i).x;
            int pos_y = candidates.get(i).y;
            int value = candidates.get(i).value;
            GameState newGrid = new GameState(this.grid.getCellMatrix());
            // 电脑即对手做出一个可能的对于电脑来说最好的(对于玩家来说最坏的)决策
            newGrid.insertTitle(pos_x, pos_y, value);
            positions++;
            AI newAI = new AI(newGrid);
            // 向下搜索,下一层为Max层,轮到玩家进行决策
            newAI.grid.playerTurn = true;
            // 这里depth没有减1是为了保证搜索到最深的层为Max层
            result = newAI.search(depth, alpha, bestScore, positions, cutoffs);
            positions = result.positions;
            cutoffs = result.cutoffs;

            // 该层为Min层,哪个分支的局势最不好,就选哪个分支,这里的bestScore代表beta
            if (result.score < bestScore) {
                bestScore = result.score;
            }
            // 如果当前bestScore也即beta<alpha时,表明这个节点下不会再有更好解,于是剪枝
            if (bestScore < alpha) {
                cutoffs++;  //减枝
                return new SearchResult(-1, alpha, positions, cutoffs);
            }
        }
    }

    return new SearchResult(bestMove, bestScore, positions, cutoffs);
}

迭代深搜

// 执行搜索操作,返回最好的移动方向
public int getBestMove() {
    return this.iterativeDeep(100);
}

// 基于alpha-beta的Minimax搜索,进行迭代深搜,搜索时间设定为0.1秒,即决策的思考时间为0.1秒
private int iterativeDeep(long minSearchTime) {
    long start = new Date().getTime();
    int depth = 0;
    int best = -1;
    do {
        SearchResult newBest = this.search(depth, -10000, 10000, 0, 0);
        if (newBest.move == -1) break;
        else best = newBest.move;
        depth++;
    } while (new Date().getTime() - start < minSearchTime);
    return best;
}

Minmax算法

介绍

Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的方法 [1] 。而开始的时候总和为0。很多棋类游戏可以采取此算法,例如井字棋(tic-tac-toe)。

基本算法思想

极小化极大(minimax)算法顾名思义,就是让最大得情况最小,这里的最大一般是指最差的情况,比如游戏中最不利的情况。

该算法需要满足零和博弈,初略的解释就是若有两个玩家进行游戏,如果其中一方得到利益那么另一方就会失去利益,游戏利益的总和为0(某些情况下为常数)。

因此,零和的约束条件也使得该算法在很多游戏中图体现出很好的效果,比如大多数的棋类游戏。

其实说白了,这个算法就是一个树形结构的递归算法,每个节点的孩子和父节点都是对方玩家,所有的节点被分为极大值(我方)节点和极小值(对方)节点。

算法优化

α-β剪枝算法

Alpha-beta基于这样一种朴素的思想:时时刻刻记得当前已经知道的最好选择,如果从当前格局搜索下去,不可能找到比已知最优解更好的解,则停止这个格局分支的搜索(剪枝),回溯到父节点继续搜索。

如果发现当前格局再往下不能找到更好的解,我们就停止在这个格局及以下的搜索,也就是剪枝。

在上述的极大极小算法中,MIN和MAX过程将所有的可能性省搜索树,然后再从端点的估计值倒推计算,这样的效率非常低下。而α-β算法的引入可以提高运算效率,对一些非必要的估计值进行舍弃。其策略是进行深度优先搜索,当生成结点到达规定深度时,立即进行静态估计,一旦某一个非端点的节点可以确定倒推值的时候立即赋值,节省下其他分支拓展到节点的开销。

剪枝规则:

(1)α剪枝,任一极小层节点的β值不大于他任一前驱极大值层节点的α值,即α(前驱层)≥β(后继层),则可以终止该极小层中这个MIN节点以下的搜索过程。这个MIN节点的倒推值确定为这个β值。

(2)β剪枝,任一极大层节点的α值不小于它任一前驱极小值层节点的β值,即β(前驱层)≤α(后继层),则可以终止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的倒推值确定为这个α值。

伪代码

/*在搜索过程中,max 方节点的当前最优值被称为α值,min 方节点的当前最优值被称为β 值。在搜索开始
时,α 值为-∞,β值为+∞,在搜索过程中,max 节点使α 值递增,min 节点则使 β值递减,两者构成一个区
间[ α ,β] ,这个区间被称为窗口。窗口的大小表示当前节点值得搜索的子节点的价值取值范围,向下搜索
的过程就是缩小窗口的过程,最终的最优值将落在这个窗口中。一旦max 节点得到其子节点的返回值大于
β值或min 节点得到其子节点的返回值小于α 值,则发生剪枝*/
function minimax(node, depth)
 
    if node is a terminal node or depth = 0
 
        return the heuristic value of node
 
    if the adversary is to play at node
 
        let α := +∞
 
        foreach child of node
 
            α := min(α, minimax(child, depth-1))
 
    else {we are to play at node}
 
        let α := -∞
 
        foreach child of node
 
            α := max(α, minimax(child, depth-1))
 
    return α

@衣陈,yceachan

空文件

简介

基于EasyX的图形化的2048游戏,图像流操作 展开 收起
C++ 等 2 种语言
取消

发行版

暂无发行版

贡献者

全部

近期动态

不能加载更多了
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/Ea_Chan/easyX2048.git
git@gitee.com:Ea_Chan/easyX2048.git
Ea_Chan
easyX2048
EasyX2048
master

搜索帮助