UVa 10838 The Pawn Chess

题目翻译

考虑以下简化版国际象棋：我们有一个4×44 \times 44×4的棋盘，第一行（输入中的最下方）有四个白兵，最后一行（输入中的最上方）有四个黑兵。游戏的目标是让自己的一个兵走到对方底线（白方走到最后一行，黑方走到第一行），或者逼对手无棋可走（即“困毙”）。当轮到某玩家走棋时，若他没有合法走法（包括所有兵已被吃光），则他被困毙。

兵的走法与普通国际象棋相同，但不能一次走两步。即：

• 兵可以向前（朝向对方底线）走一步，前提是目标格为空。
• 兵也可以吃掉对方兵，如果对方兵位于其左前方或右前方（斜前方一格）。被吃的兵从棋盘移除。

给定棋盘上兵的位置，假设双方都采取最优策略，判断谁会获胜。同时需要计算游戏结束前会进行的步数（假设获胜方会尽快获胜，输的一方会尽可能拖延）。输入局面总是轮到白方走子。

输入格式

第一行输入测试用例数（最多505050个）。每个用例包含四行描述棋盘，前面有一个空行。四行中的第一行表示棋盘的最后一行（黑兵的起始位置）。黑兵用p表示，白兵用P表示，空位用.表示。每方有111到444个兵。初始局面不会是终局局面，且白方至少有一个合法走子。注意：输入局面不一定是从初始局面合法走出来的。

输出格式

对于每个测试用例，输出一行：

• 如果白方赢，输出white (xx)
• 如果黑方赢，输出black (xx)

其中xx是步数（白方赢时步数为奇数，黑方赢时为偶数）。

题目分析与解题思路

本题是一个双方零和博弈问题，棋盘大小固定为4×44 \times 44×4，每方最多444个兵，状态空间有限，适合用极小化极大算法（Minimax\texttt{Minimax}Minimax）配合记忆化搜索解决。

核心思路

1. 状态表示
   棋盘共有161616格，每格有三种状态：空、白兵、黑兵。可以用222位二进制表示一格（000000空，010101白兵，101010黑兵），整个棋盘用一个646464位整数（unsigned long long）表示。另外还需要记录当前轮到谁走（000白方，111黑方）。

2. 胜负判定

   • 白方赢：任意白兵到达第000行（黑方底线）。
   • 黑方赢：任意黑兵到达第333行（白方底线）。
   • 若当前玩家无合法走法（包括无兵可走），则对方赢。

3. 走法生成
   根据当前玩家（白方或黑方）遍历所有兵：

   • 向前走：检查目标格是否在棋盘内且为空。
   • 吃子：检查左前、右前（对白方是行减111，对黑方是行加111）是否有对方兵。

4. 搜索策略（Minimax\texttt{Minimax}Minimax）
   设solve(state,turn)solve(state, turn)solve(state,turn)返回（赢家，从当前状态到游戏结束的步数），其中turn=0turn = 0turn=0表示白方走，turn=1turn = 1turn=1表示黑方走。

   • 终止条件：出现胜负局面或无棋可走。
   • 递归过程：
     • 生成所有合法走法。
     • 对每个走法递归调用solve(nextState,turn⊕1)solve(nextState, turn \oplus 1)solve(nextState,turn⊕1)。
     • 如果当前玩家能赢，则选择步数最少的走法（尽快赢）。
     • 如果当前玩家会输，则选择步数最多的走法（拖延）。

5. 记忆化
   用哈希表缓存(state,turn)(state, turn)(state,turn)的结果，避免重复计算。

算法流程

1. 读入棋盘，转换为646464位状态码。
2. 调用solve(state,0)solve(state, 0)solve(state,0)（白方先走）。
3. 根据返回的赢家和步数输出结果。

复杂度分析

• 状态数：每格333种状态，最多316≈4.3×1073^{16} \approx 4.3 \times 10^7316≈4.3×107，但实际可达状态远少于这个数（每方最多444个兵）。
• 每个状态生成走法最多4×3=124 \times 3 = 124×3=12种（444个兵，每个兵最多333种走法：向前、左吃、右吃）。
• 记忆化后，每个状态只计算一次，整体在时间和空间上均可接受。

代码实现

// The Pawn Chess// UVa ID: 10838// Verdict: Accepted// Submission Date: 2025-12-14// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 棋盘编码：每格 2 位，共 16 格，64 位整数存储// 00: 空, 01: 白兵(P), 10: 黑兵(p)constintWHITE=1,BLACK=2;constintINF=1e9;// 方向：白兵向上(row-1)，黑兵向下(row+1)constintWHITE_DIR=-1,BLACK_DIR=1;constintCAPTURE_DIRS[2][2]={{-1,-1},{-1,1}};// 白兵吃子方向（左上、右上）constintBLACK_CAPTURE_DIRS[2][2]={{1,-1},{1,1}};// 黑兵吃子方向（左下、右下）// 记忆化缓存：map<状态, pair<结果, 步数>>unordered_map<unsignedlonglong,pair<int,int>>memo[2];// 0:白方走, 1:黑方走// 从状态中获取某格的值intgetCell(unsignedlonglongstate,intr,intc){intpos=(r*4+c)*2;return(state>>pos)&3;}// 设置某格的值voidsetCell(unsignedlonglong&state,intr,intc,intval){intpos=(r*4+c)*2;state&=~(3ULL<<pos);state|=((unsignedlonglong)val<<pos);}// 判断是否到达底线boolisWhiteWin(unsignedlonglongstate){for(intc=0;c<4;++c)if(getCell(state,0,c)==WHITE)returntrue;// 白兵到达第0行（黑方底线）returnfalse;}boolisBlackWin(unsignedlonglongstate){for(intc=0;c<4;++c)if(getCell(state,3,c)==BLACK)returntrue;// 黑兵到达第3行（白方底线）returnfalse;}// 生成所有合法走法vector<pair<unsignedlonglong,int>>generateMoves(unsignedlonglongstate,intturn){vector<pair<unsignedlonglong,int>>moves;intplayer=(turn==0)?WHITE:BLACK;intdir=(turn==0)?WHITE_DIR:BLACK_DIR;for(intr=0;r<4;++r){for(intc=0;c<4;++c){if(getCell(state,r,c)!=player)continue;// 向前走一步intnr=r+dir;if(nr>=0&&nr<4&&getCell(state,nr,c)==0){unsignedlonglongnext=state;setCell(next,r,c,0);setCell(next,nr,c,player);moves.push_back({next,1});}// 吃子auto&capDirs=(turn==0)?CAPTURE_DIRS:BLACK_CAPTURE_DIRS;for(auto&d:capDirs){intnr=r+d[0];intnc=c+d[1];if(nr>=0&&nr<4&&nc>=0&&nc<4){inttarget=getCell(state,nr,nc);if(target!=0&&target!=player){unsignedlonglongnext=state;setCell(next,r,c,0);setCell(next,nr,nc,player);moves.push_back({next,1});}}}}}returnmoves;}// Minimax 搜索，返回 (胜负, 步数)pair<int,int>solve(unsignedlonglongstate,intturn){// 检查缓存if(memo[turn].count(state))returnmemo[turn][state];// 终局判断if(isWhiteWin(state))return{0,0};// 白方赢，步数为0（当前还未走）if(isBlackWin(state))return{1,0};// 黑方赢automoves=generateMoves(state,turn);if(moves.empty()){// 当前玩家无棋可走，对方赢if(turn==0)return{1,0};// 白方无棋，黑方赢elsereturn{0,0};// 黑方无棋，白方赢}intbestWinner=-1;intbestSteps=INF;intworstSteps=-1;for(auto&mv:moves){autores=solve(mv.first,turn^1);intwinner=res.first;intsteps=res.second+mv.second;// 加上这一步if(bestWinner==-1){bestWinner=winner;bestSteps=steps;worstSteps=steps;}else{if(winner==turn){// 当前玩家能赢，取最短步数if(winner==bestWinner)bestSteps=min(bestSteps,steps);else{bestWinner=winner;bestSteps=steps;}}else{// 当前玩家会输，取最长步数（拖延）if(bestWinner==winner)worstSteps=max(worstSteps,steps);else{// 如果之前有赢的可能，保留赢法if(bestWinner!=turn){bestWinner=winner;worstSteps=steps;}}}}}intfinalSteps=(bestWinner==turn)?bestSteps:worstSteps;memo[turn][state]={bestWinner,finalSteps};return{bestWinner,finalSteps};}intmain(){intT;cin>>T;while(T--){vector<string>board(4);for(inti=0;i<4;++i){cin>>board[i];// 处理可能的空格（样例中有空格，但实际输入可能没有）if(board[i].size()<4)board[i]="....";}// 构建状态unsignedlonglongstate=0;for(intr=0;r<4;++r){for(intc=0;c<4;++c){intval=0;if(board[r][c]=='P')val=WHITE;elseif(board[r][c]=='p')val=BLACK;setCell(state,r,c,val);}}// 初始化缓存memo[0].clear();memo[1].clear();autores=solve(state,0);intwinner=res.first;intsteps=res.second;if(winner==0)cout<<"white ("<<steps<<")\n";elsecout<<"black ("<<steps<<")\n";}return0;}

总结

本题是一道典型的博弈搜索题，通过状态压缩和记忆化搜索可以在有限时间内求解。关键在于理解Minimax\texttt{Minimax}Minimax搜索中“赢方尽快、输方拖延”的策略，并正确实现走法生成与胜负判断。代码中使用了646464位整数表示棋盘状态，提高了存储和计算效率，适合题目给定的数据范围。