第十三次CCF CSP認證(2018年3月)真題棋局評估 題解

第十三次CCF CSP認證(2018年3月)真題棋局評估  題解

問題描述
  Alice和Bob正在玩井字棋遊戲。
  井字棋遊戲的規則很簡單:兩人輪流往3*3的棋盤中放棋子,Alice放的是“X”,Bob放的是“O”,Alice執先。當同一種棋子佔據一行、一列或一條對角線的三個格子時,遊戲結束,該種棋子的持有者獲勝。當棋盤被填滿的時候,遊戲結束,雙方平手。
  Alice設計了一種對棋局評分的方法:
  - 對於Alice已經獲勝的局面,評估得分為(棋盤上的空格子數 1);
  - 對於Bob已經獲勝的局面,評估得分為 -(棋盤上的空格子數 1);
  - 對於平局的局面,評估得分為0;

  例如上圖中的局面,Alice已經獲勝,同時棋盤上有2個空格,所以局面得分為2 1=3。
  由於Alice並不喜歡計算,所以他請教擅長程式設計的你,如果兩人都以最優策略行棋,那麼當前局面的最終得分會是多少?
輸入格式
  輸入的第一行包含一個正整數T,表示資料的組數。
  每組資料輸入有3行,每行有3個整數,用空格分隔,分別表示棋盤每個格子的狀態。0表示格子為空,1表示格子中為“X”,2表示格子中為“O”。保證不會出現其他狀態。
  保證輸入的局面合法。(即保證輸入的局面可以通過行棋到達,且保證沒有雙方同時獲勝的情況)
  保證輸入的局面輪到Alice行棋。
輸出格式
  對於每組資料,輸出一行一個整數,表示當前局面的得分。
資料規模和約定
  對於所有評測用例,1 ≤ T ≤ 5。

 

個人理解

              很直觀,這個是個博弈論問題,A、B在既定棋盤狀況下以最優策略使自己獲勝。因為是3×3的棋盤,可以用一個9位數的陣列來對映當前狀態,進行記憶化搜尋,因為對於某一個既定狀態,它的答案是唯一的,所以搜過的狀態無須再次搜尋。搜尋決策時注意起初當前狀態無結果,搜尋到一種就重新整理,後續更新使最終答案正確的方法是 輪到A時在所有拓展方向中取結果最大的,B反之。兩個搜尋結束點是所有格子填滿或一個選手贏得比賽。

   幾個小點說一下,一個是判斷某人是否獲勝的方式,三子成一條線那麼,第三個子的座標一定是在第二個的基礎上加上前兩個的差值;另一個是終止狀態中一定不要忘記都填滿卻平局的狀態。

   在考場上因為觀察到棋盤僅是3×3的,第一反應是打表,但在搜尋決策時進入了一個很大誤區,總想模擬作為一個棋手的所有決策方式,進而講題目演化成一個巨大的模擬,耗時耗力最後發現誤入歧途最終只得放棄。考後討論後才明白記憶化搜尋即為正確方法。

程式碼分享

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long sta;
int sve[222222223];
int che[4][4];
int t,mas,ans;
bool check(long long now)
{
int x1[9],x2[9],y1[9],y2[9];
int tot=0,a,b,x,y;
a=b=0;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
if(che[i][j]==0)tot  ;
else if(che[i][j]==1)
{
a  ;
x1[a]=i;y1[a]=j;
}
else
{
b  ;
x2[b]=i;y2[b]=j;
}
}
if(a<3&&b<3)return false;
if(a>=3)
{
for(int i=1;i<a;i  )
for(int j=i 1;j<=a;j  )
{
x=x1[j]*2-x1[i];
y=y1[j]*2-y1[i];
if(x>0&&x<4&&y>0&&y<4)
if(che[x][y]==1)
{
sve[now]=tot 1;
return true;
}
}
}
if(b>=3)
{
for(int i=1;i<b;i  )
for(int j=i 1;j<=b;j  )
{
x=x2[j]*2-x2[i];
y=y2[j]*2-y2[i];
if(x>0&&x<4&&y>0&&y<4)
if(che[x][y]==2)
{
sve[now]=-(tot 1);
return true;
}
}
}
if(tot==0){
sve[now]=0;
return true;
}
return false;
}
long long cla()
{
long long tot=0;;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
tot=che[i][j] tot*10;
}
return tot;
}
void dfs(long long now,int who)
{
long long aft;
if(sve[now]!=mas)return;
if(check(now))return;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
if(che[i][j]==0)
{
che[i][j]=who;
aft=cla();
dfs(aft,3-who);
if(sve[now]==mas)sve[now]=sve[aft];
if(who==1&&sve[aft]>sve[now])sve[now]=sve[aft];
if(who==2&&sve[aft]<sve[now])sve[now]=sve[aft];
che[i][j]=0;
}
}
}
int main()
{
scanf("%d",&t);
memset(sve,127,sizeof(sve));
mas=sve[1];
while(t--)
{
sta=0;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
scanf("%d",&che[i][j]);
sta=che[i][j] sta*10;
}
dfs(sta,1);
ans=sve[sta];
printf("%d\n",ans);
}
return 0;
}

——————————————–更新分割線—————————————————-

  首先要感謝@qq_37482918的提醒,認證後寫完程式碼和帖子就去做別的事情了,後來ccf官網出了題庫就興沖沖交了一發,結果意外的WA了,當然是爆掉了!

    因為在編譯器裡操作肯定不會出這個問題,後來就想到了因為每個點狀態無非是三種,所以很自然想到用三進位制優化一下,將 資料量就極大地降下來了,因為在原來的sve陣列利用率只有3^9/222222223=0.0088%.

    優化後提交就過了。

    

   簡單說下優化方式,原來狀態的表示方法不便,只是每次存狀態、取狀態時將原來的狀態數轉化為三進位制所代表的十進位制,即turn方法。進位制轉化詳見點選開啟連結

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long sta;
int sva[20000];
int che[4][4];
int t,mas,ans;
int turn(long long x)
{
int re=0;
int t[9];
for(int i=0;i<9;i  )
{
t[i]=x%10;
x=x/10;
}
for(int i=8;i>=0;i--)
{
re=re*3 t[i];
}
return re;
}
bool check(long long now)
{
int x1[9],x2[9],y1[9],y2[9];
int tot=0,a,b,x,y;
a=b=0;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
if(che[i][j]==0)tot  ;
else if(che[i][j]==1)
{
a  ;
x1[a]=i;y1[a]=j;
}
else
{
b  ;
x2[b]=i;y2[b]=j;
}
}
if(a<3&&b<3)return false;
if(a>=3)
{
for(int i=1;i<a;i  )
for(int j=i 1;j<=a;j  )
{
x=x1[j]*2-x1[i];
y=y1[j]*2-y1[i];
if(x>0&&x<4&&y>0&&y<4)
if(che[x][y]==1)
{
sva[turn(now)]=tot 1;
return true;
}
}
}
if(b>=3)
{
for(int i=1;i<b;i  )
for(int j=i 1;j<=b;j  )
{
x=x2[j]*2-x2[i];
y=y2[j]*2-y2[i];
if(x>0&&x<4&&y>0&&y<4)
if(che[x][y]==2)
{
sva[turn(now)]=-(tot 1);
return true;
}
}
}
if(tot==0){
sva[turn(now)]=0;
return true;
}
return false;
}
long long cla()
{
long long tot=0;;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
tot=che[i][j] tot*10;
}
return tot;
}
void dfs(long long now,int who)
{
long long aft;
int x,y;
x=turn(now);
if(sva[x]!=mas)return;
if(check(now))return;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
if(che[i][j]==0)
{
che[i][j]=who;
aft=cla();
y=turn(aft);
dfs(aft,3-who);
if(sva[x]==mas)sva[x]=sva[y];
if(who==1&&sva[y]>sva[x])sva[x]=sva[y];
if(who==2&&sva[y]<sva[x])sva[x]=sva[y];
che[i][j]=0;
}
}
}
int main()
{
scanf("%d",&t);
memset(sva,127,sizeof(sva));
mas=sva[1];
while(t--)
{
sta=0;
for(int i=1;i<4;i  )
for(int j=1;j<4;j  )
{
scanf("%d",&che[i][j]);
sta=che[i][j] sta*10;
}
dfs(sta,1);
ans=sva[turn(sta)];
printf("%d\n",ans);
}
return 0;
}