投稿
  1. 高性能架构探索首页
  2. C/C++

电脑如何自动玩popstar（BFS，估价函数）

admin • • C/C++ • 阅读 140

非正经向更博~~~

只是一个无聊的想法，然而百度以后发现解决这个问题的方案很少，也少有实现。于是又来瞎写一篇文章。

游戏规则简单介绍

电脑如何自动玩popstar（BFS，估价函数）

开局是一个10×10的方格，有5种颜色的星星

每次你可以选择一个大小为 (x(xge 2)) 的同色星星连通块并消除它，获得(5x^2)的分数

消除后，空位上方的星星会下落，空列右侧的星星会整列整列地左移

如此循环，直到所有星星都是单个的，无法消除，此时如果剩余星星数(x)不到(10)个，还能获得奖励分(2000-20x^2)

以上为一局，每局得分累加，同时每局累计得分过关目标也会增加（最多加4000），达不到目标则游戏失败。

步骤

自动截屏并识别方块颜色

不会，等上大学再学图像处理

不对呀，蒟蒻没有大学上呀嘤嘤嘤

计算最优解

过程中最核心的部分。

其实算出最优解是几乎不可能做到的，因为只能暴搜，而状态数太大，交给家用电脑绝对TLE（如果需要记忆化去重还MLE）

交给超算还是有希望很快出解

那只好用一些剪枝算法，能在可接受的时间内算出可接受的高分解了

popstar游戏每过一关需要的累计分数比上一关增加最多4000

所以如果能稳定算出4000以上的解就可以无限过关啦

然而这又是不可能的，因为随机一个初始状态甚至都有可能一步也动不了=直接爆0

。。。。。。

想得高分，就要防止有机会得高分的状态被剪掉。

目前看来，积累高分的途径主要有2个

一个是通过聚聚聚聚聚起一个很大的同色块消除得高分，每个小方块的得分与消除时的同色块大小成正比

网上有一个想法，以当前得分+当前所有未被消除色块的分值作为估价函数进行搜索

比起单纯以当前得分为依据进行剪枝，这种方法对于这种情况的处理要好很多。

毕竟在聚起大块爆分之前，总要消掉一些别的颜色的小块，经历一段时间的得分低谷写出了一些哲理的味道

另一个是通过最后剩的单块少于10得分，这个没有规律可循，只能在接近终盘的时候少剪枝吧

已实现，目前对于随机的开局，在(1s)内完成搜索，平均分可达(5500)，分数不到(4000)的概率小于(5%)，无限过关很稳了。

开(100)个数组，下标为(i)的数组存所有剩余块数为(i)的状态。

对于每个数组，去重，按上述估价函数排序，只对前LIM个状态进行bfs扩展。

附带结果展示功能，#define SHOW即可

#include<bits/stdc++.h>
#include<windef.h>
#include<winbase.h>
#include<wincon.h>
#include<conio.h>
#define LL long long
#define R register int
#define Handle GetStdHandle(STD_OUTPUT_HANDLE)
#define SetPos(Y,X) SetConsoleCursorPosition(Handle,(COORD){(short)(X),(short)(Y)})
#define cprintf(c,a...) SetConsoleTextAttribute(Handle,c),printf(a)
//#define SHOW
using namespace std;
const int N=10,LIM=1e3,ColorID[]={0,11,12,10,14,13};
struct Data{//状态，一列方块用二进制压进一个int里
    int a[N],sc,ex;Data*pre;
    inline bool operator<(const Data&x)const{
        if(ex!=x.ex)return ex>x.ex;
        for(R i=0;i<N;++i)
            if(a[i]!=x.a[i])return a[i]<x.a[i];
        return 0;
    }
    inline bool operator==(const Data&x)const{
        for(R i=0;i<N;++i)
            if(a[i]!=x.a[i])return 0;
        return 1;
    }
    inline int operator()(R x,R y)const{
        return a[y]>>3*x&7;
    }
    inline void operator()(R x,R y,R z){
        a[y]^=((a[y]>>3*x&7)^z)<<3*x;
    }
    inline void pop(R x,R y){//x行y列消除
        a[y]=(a[y]>>3*(x+1)<<3*x)|(a[y]&((1<<3*x)-1));
        if(a[y])return;
        for(++y;y<N;++y)a[y-1]=a[y];
        a[N-1]=0;
    }
};
vector<Data>v[N*N+1];
Data mp,*ansp,a[N*N];
bool fl,vis[N][N];
int x,y,c,ans,ps,pt,px[N*N],py[N*N];
inline void swap(R&x,R&y){
    R z=x;x=y;y=z;
}
void Print(Data mp){//展示局面
    SetPos(0,0);
    for(R i=N-1;~i;--i){
        printf(" ");
        for(R j=0;j<N;++j)
            cprintf(ColorID[mp(i,j)],"┌───┐");
        cprintf(15,"n%d",i);
        for(R j=0;j<N;++j)
            cprintf(ColorID[mp(i,j)],"│ ★│");
        printf("n ");
        for(R j=0;j<N;++j)
            cprintf(ColorID[mp(i,j)],"└───┘");
        printf("n");
    }
    cprintf(15," ");
    for(R j=0;j<N;++j)
        printf("  %d  ",j);
    printf("nscore=%dn",mp.sc);
}
void Flash(Data mp){//展示用，使下一步消除块闪烁
    for(R i=0;i<=pt;++i)
        px[i]=N-1-px[i];
    do{
        Print(mp);
        Sleep(200);
        for(R i=0;i<=pt;++i){
            SetPos(3*px[i]  ,1+5*py[i]),printf("     ");
            SetPos(3*px[i]+1,1+5*py[i]),printf("     ");
            SetPos(3*px[i]+2,1+5*py[i]),printf("     ");
        }
        SetPos(3*N+2,0);
        Sleep(300);
    }while(!kbhit());
    getch();
}
int main(){
    freopen("save.dat","r",stdin);
    scanf("%d,%d,%d",&x,&x,&x);
    for(R i=N-1;~i;--i)//开局读入
        for(R j=0;j<N;++j){
            x=rand()%6;
            scanf("%d",&x);
            if(x<0||x>5)return 0;
            if(x)++c;
            mp(i,j,x);
        }
    v[c].push_back(mp);
    for(R l=N*N;~l;--l){//搜索
        sort(v[l].begin(),v[l].end());//状态去重
        v[l].resize(unique(v[l].begin(),v[l].end())-v[l].begin());
        for(Data&now:v[l]){//计算估价函数
            fl=0;memset(vis,0,sizeof(vis));
            for(R i=N-1;~i;--i)
                for(R j=N-1;~j;--j){
                    if(vis[i][j]||(c=now(i,j))==0)continue;
                    px[0]=i;py[0]=j;vis[i][j]=1;
                    for(ps=pt=0;ps<=pt;++ps){
                        x=px[ps];y=py[ps];
#define GO(X,Y,A) if(A&&!vis[X][Y]&&c==now(X,Y))px[++pt]=X,py[pt]=Y,vis[X][Y]=1
                        GO(x-1,y,x);
                        GO(x,y-1,y);
                        GO(x+1,y,x+1<N);
                        GO(x,y+1,y+1<N);
                    }
                    if(pt)now.ex+=(pt+1)*(pt+1)*5;
                }
        }
        sort(v[l].begin(),v[l].end());
        if(v[l].size()>LIM)v[l].resize(LIM);
        for(Data&now:v[l]){//状态扩展
            fl=0;memset(vis,0,sizeof(vis));
            for(R i=N-1;~i;--i)
                for(R j=N-1;~j;--j){
                    if(vis[i][j]||(c=now(i,j))==0)continue;
                    px[0]=i;py[0]=j;vis[i][j]=1;
                    for(ps=pt=0;ps<=pt;++ps){
                        x=px[ps];y=py[ps];
                        GO(x-1,y,x);
                        GO(x,y-1,y);
                        GO(x+1,y,x+1<N);
                        GO(x,y+1,y+1<N);
                    }
                    if(!pt)continue;
                    fl=1;
                    for(ps=0;ps<pt;++ps)
                        for(R k=pt;k>ps;--k)
                            if(px[k-1]<px[k]||(px[k-1]==px[k]&&py[k-1]<py[k]))
                                swap(px[k-1],px[k]),swap(py[k-1],py[k]);
                    mp=now;mp.pre=&now;mp.ex=mp.sc=mp.sc+(pt+1)*(pt+1)*5;
                    for(ps=0;ps<=pt;++ps)
                        mp.pop(px[ps],py[ps]);
                    v[l-pt-1].push_back(mp);
                }
            if(!fl){//算分
                if(l<10)now.sc+=2000-20*l*l;
                if(ans<now.sc)ans=now.sc,ansp=&now;
            }
        }
    }
    for(pt=0;ansp;ansp=ansp->pre)
        a[pt++]=*ansp;
    for(R l=N*N;~l;--l)v[l].resize(0);
#ifdef SHOW//结果展示
    for(R i=pt-1;i;--i){
        memset(vis,0,sizeof(vis));
        Data now=a[i];
        for(y=0;now.a[y]==a[i-1].a[y];++y);
        for(x=0;(now.a[y]<<(29-3*x))==(a[i-1].a[y]<<(29-3*x));++x);
        c=now(x,y);px[0]=x;py[0]=y;vis[x][y]=1;
        for(ps=pt=0;ps<=pt;++ps){
            x=px[ps];y=py[ps];
            GO(x-1,y,x);
            GO(x,y-1,y);
            GO(x+1,y,x+1<N);
            GO(x,y+1,y+1<N);
        }
        Flash(a[i]);
    }
    Print(a[0]);
#endif
    return a[0].sc;
}

save.dat示例

0,0,0
4 5 4 3 1 3 1 1 1 3 
4 1 3 2 3 2 1 1 3 1 
2 2 1 2 3 4 2 1 1 4 
2 1 1 3 3 3 2 3 2 3 
4 4 4 3 3 5 3 2 4 2 
5 5 5 1 4 5 5 2 2 5 
5 2 4 3 3 5 3 2 4 3 
3 4 4 4 1 3 3 1 2 5 
4 3 5 5 5 2 5 3 4 1 
4 4 1 5 4 2 5 1 5 1

展示效果

电脑如何自动玩popstar（BFS，估价函数）

模拟鼠标点击

百度发现好像C++有函数兹瓷

待更

原文链接: https://www.cnblogs.com/flashhu/p/13341142.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    电脑如何自动玩popstar（BFS，估价函数）

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368523

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午6:28
下一篇 2023年3月2日 下午6:28

相关推荐