# EasyX2048 **Repository Path**: Dooooooo/easyX2048 ## Basic Information - **Project Name**: EasyX2048 - **Description**: 基于EasyX的图形化的2048游戏，图像流操作 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-04-01 - **Last Updated**: 2024-04-01 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 衣陈的Easyx2048 ## 框架 vs2022+EasyX ## 核心算法 ### 1.批量加载图像资源 ~~~C++ //为成员属性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算法 ~~~C++ //用两个一维数组线性记录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算法 ~~~C++ //移动逻辑:遇到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官方文档 > ![image-20220812232437782](C:\Users\衣陈\AppData\Roaming\Typora\typora-user-images\image-20220812232437782.png) ![image-20220812232353876](https://s2.loli.net/2022/08/12/LsG5Qbdm7j18F3h.png) 失败了，原因待究 ## 关于帧率控制 ~~~c++ #include clock_t begintime=clock();//时间变量，右函数返回程序运行指此函数时的时间，单位为毫秒 clock_t fortime=clock()-begintime(); //用Sleep函数补足空白时间，完成帧率控制 ~~~ ## 关于2048AI算法冲浪 > 2048本质上可以抽象成信息对称双人对弈模型（玩家向四个方向中的一个移动，然后计算机在某个空格中填入2或4）。这里“信息对称”是指在任一时刻对弈双方对格局的信息完全一致，移动策略仅依赖对接下来格局的推理。作者使用的核心算法为对弈模型中常用的带Alpha-beta剪枝的Minimax。这个算法也常被用于如国际象棋等信息对称对弈AI中。 * **[Repo已fork](https://github.com/yceachan/2048AI)** * [README](https://github.com/yceachan/2048AI/blob/master/README.md) ### Minimax Search和Alpha Beta Pruning的实现 ~~~C++ 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 candidates = new ArrayList<>(); List cells = this.grid.getAvailableCells(); int[] fill = {2, 4}; List scores_2 = new ArrayList<>(); List 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-beta基于这样一种朴素的思想：时时刻刻记得当前已经知道的最好选择，如果从当前格局搜索下去，不可能找到比已知最优解更好的解，则停止这个格局分支的搜索（剪枝），回溯到父节点继续搜索。 > > 如果发现当前格局再往下不能找到更好的解，我们就停止在这个格局及以下的搜索，也就是剪枝。 在上述的极大极小算法中，MIN和MAX过程将所有的可能性省搜索树，然后再从端点的估计值倒推计算，这样的效率非常低下。而α-β算法的引入可以提高运算效率，对一些非必要的估计值进行舍弃。其策略是进行深度优先搜索，当生成结点到达规定深度时，立即进行静态估计，一旦某一个非端点的节点可以确定倒推值的时候立即赋值，节省下其他分支拓展到节点的开销。 ##### 剪枝规则： （1）α剪枝，任一极小层节点的β值不大于他任一前驱极大值层节点的α值，即α（前驱层）≥β（后继层），则可以终止该极小层中这个MIN节点以下的搜索过程。这个MIN节点的倒推值确定为这个β值。 （2）β剪枝，任一极大层节点的α值不小于它任一前驱极小值层节点的β值，即β（前驱层）≤α（后继层），则可以终止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的倒推值确定为这个α值。 #### 伪代码 ~~~C++ /*在搜索过程中，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