vs2022+EasyX
//为成员属性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++;
}
}
//用两个一维数组线性记录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;
}
}
//移动逻辑:遇到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官方文档 <img alt="image-20220812232437782">
失败了,原因待究
#include<time.h>
clock_t begintime=clock();//时间变量,右函数返回程序运行指此函数时的时间,单位为毫秒
clock_t fortime=clock()-begintime();
//用Sleep函数补足空白时间,完成帧率控制
2048本质上可以抽象成信息对称双人对弈模型(玩家向四个方向中的一个移动,然后计算机在某个空格中填入2或4)。这里“信息对称”是指在任一时刻对弈双方对格局的信息完全一致,移动策略仅依赖对接下来格局的推理。作者使用的核心算法为对弈模型中常用的带Alpha-beta剪枝的Minimax。这个算法也常被用于如国际象棋等信息对称对弈AI中。
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;
}
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
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。