围棋打谱软件中自动提子功能的实现，C/C++源码

本文首发地址：http://blog.csdn.net/liigo/archive/2009/09/22/4582018.aspx

转载请注明出处：http://blog.csdn.net/liigo

作者：liigo, 2009/09/22

 

　　在下围棋时，当一个棋子落到棋盘上，它会对周围对方棋子的死活产生影响，如果对方棋子没有气了（死了），必须从棋盘上拿掉（提子）。这个过程体现到围棋软件中，就需要通过程序代码判断某一个棋子或某一片棋子的死活状态，进而把死掉的棋子从棋盘上移除。

　　进一步分析的话，刚落下的棋子，只可能威胁到周围与其紧临的上下左右方向的四个对方棋子（也可能是三个或两个，如在边角的话），而这四个方向上的对方棋子，可能是孤立的一个棋子，也可能是多个棋子相连的一片棋子（一块棋）。要判断一块棋是否还活着，需要逐个检查这块棋中的每一个棋子：如果其中某个棋子旁边没有棋子，说明这块棋至少还有一口气，因而确定它还没有死；如果检查完这块棋中的所有棋子，始终不能找到一口气，可以确定这整块棋都死掉了。看上去这是一个需要采用递归处理的情况。递归处理整块棋时，切记需要记录已经处理过的棋子，不能重复处理同一个棋子，否则可能会导致循环递归、死递归的情况发生。一旦确定了棋子的生死，从棋盘上拿掉它是很容易的事情，只是在程序中做一些标记而已。

　　注意，我（liigo）这里说的某块棋“还活着”，并不等同于围棋术语中的“已做活”，而只是表示这块棋“暂时还没有死”，至于将来会不会死，不在现在的处理范围之内。别忘了，我们的目标是“如果棋子死了，把它从棋盘上拿掉”，既然还没死（或没死绝），又何必管它呢（如果非要提前提子，反而违反围棋规则了）。

　　以下C/C++源代码，实现了上面说到的自动提子功能。

 

//处理刚落下的子对周边对方子的死活影响 void processLiving(int row, int col) { StoneColor color = m_board[row-1][col-1]; assert(color != SC_BLANK); StoneColor otherColor = (color == SC_BLACK ? SC_WHITE : SC_BLACK); if(m_killedStones[m_stoneIndex] == NULL) m_killedStones[m_stoneIndex] = new BufferedMem(20); BufferedMem* pKilledStones = m_killedStones[m_stoneIndex]; pKilledStones->Empty(); //如果周边是对方的子, 则检查其死活情况, 死了的拿掉 BufferedMem stoneIndexList; if(row>1 && m_board[row-1-1][col-1]==otherColor && checkLiving(row-1,col,color,&stoneIndexList)==false) processDeadStones(&stoneIndexList); stoneIndexList.Empty(); if(row<19 && m_board[row+1-1][col-1]==otherColor && checkLiving(row+1,col,color,&stoneIndexList)==false) processDeadStones(&stoneIndexList); stoneIndexList.Empty(); if(col>1 && m_board[row-1][col-1-1]==otherColor && checkLiving(row,col-1,color,&stoneIndexList)==false) processDeadStones(&stoneIndexList); stoneIndexList.Empty(); if(col<19 && m_board[row-1][col+1-1]==otherColor && checkLiving(row,col+1,color,&stoneIndexList)==false) processDeadStones(&stoneIndexList); InvalidateRect(m_hWnd, NULL, true); }

 

//检查row/col所在的子的死活, color为另一方子的颜色. //返回 1 表示活着(没死), 返回 0 表示死了, 返回 -1 表示生死未定 int checkLiving(int row, int col, StoneColor color, BufferedMem* pStoneIndexList) { int index = RowColToIndex(row, col); if(m_board[row-1][col-1] == SC_BLANK) //有气, 所以活着 return 1; if(m_board[row-1][col-1] == color) //这是对方的子 return -1; int* pIndex = (int*) pStoneIndexList->GetData(); for(int i = 0, n = pStoneIndexList->GetDataSize()/sizeof(int); i < n; i++) { if(pIndex[i] == index) return -1; //已经处理过该子了 } pStoneIndexList->AppendMem(&index, sizeof(index)); //递归检查周边己方的子, 只要整块有一口气就说明活着 //这里存在重复检查的情况, 需要优化 if(row > 1 && m_board[row-1-1][col-1] != color && checkLiving(row-1, col, color, pStoneIndexList)==1) return 1; if(row < 19 && m_board[row+1-1][col-1] != color && checkLiving(row+1, col, color, pStoneIndexList)==1) return 1; if(col > 1 && m_board[row-1][col-1-1] != color && checkLiving(row, col-1, color, pStoneIndexList)==1) return 1; if(col < 19 && m_board[row-1][col+1-1] != color && checkLiving(row, col+1, color, pStoneIndexList)==1) return 1; return 0; }

 

void processDeadStones(BufferedMem* deathStoneIndexList) { int* pIndex = (int*) deathStoneIndexList->GetData(); StoneColor* pBoard = &m_board[0][0]; for(int i = 0, n = deathStoneIndexList->GetDataSize()/sizeof(int); i < n; i++) pBoard[pIndex[i]] = SC_BLANK; //把死掉的子记录下来, 供向前打谱时使用 if(deathStoneIndexList->GetDataSize() > 0) { BufferedMem* pKilledStones = m_killedStones[m_stoneIndex]; assert(pKilledStones); pKilledStones->AppendMem(deathStoneIndexList->GetData(), deathStoneIndexList->GetDataSize());//此处可能会有重复,但无所谓 } }

 

以上代码来自我（liigo）最近开发的“M8围棋谱”软件，此项目已在 Google Code 上开源：http://code.google.com/p/m8weiqipu/。

如有错漏疏忽之处，诚请批评指正。