男女在床上做暖暖插孔网站,制作简单的网页代码,wordpress静态化缓存,建设网站考虑因素0 引子
常见的五子棋棋盘大小为15x15#xff0c;最直观的表示就是一个二维数据。本文为了易于拓展一开始使用的是QVectorQVector的数据#xff0c;但是在分支因子为10的情况下只能搜索到4层左右#xff0c;后面深度加深#xff0c;搜索时间呈指数倍数增长。这种实…0 引子
常见的五子棋棋盘大小为15x15最直观的表示就是一个二维数据。本文为了易于拓展一开始使用的是QVectorQVector的数据但是在分支因子为10的情况下只能搜索到4层左右后面深度加深搜索时间呈指数倍数增长。这种实现方式下六层搜索深度下搜索时间大于1min。 接着使用二维数组int[][]来表示一个搜索状态,搜索速度略有加快时间大约在2倍左右(记忆模糊了)。 目前实现方式中使用的位棋盘这样可以有效的减少寻址时间取出一行或者一列只需要从内存中取出一个int32考虑到17x17或者19x19。有些读者可能想问一个格子有三种状态黑/白/空bool又能如何表示呢答案就是使用两个int32数组表示一个数组表示是否有子另一个表示黑子还是白子。 1 定义
一般而言一组二维数组就可以充分的表示棋盘信息但是在后续棋盘静态评估的需求中发现本文需要对棋盘的四个方向上评估出基础棋型。因而从不同角度冗余的描述棋盘信息就是必要的。
//棋子值的定义[保证0 1为黑子或者白子]
#define PLAYER_BLACK 0
#define PLAYER_WHITE 1
#define PLAYER_NONE 2//四方向
#define MMainDiagonal 0 //主对角线
#define MSubDiagonal 1 //副对角线
#define MHorizontal 2 //水平
#define MVertical 3 //竖直这里也简单给出棋盘信息完备表示为了简化搜索过程的的边界处理对所有棋盘加墙白棋搜索时墙就是黑子。对角线上只保留了可以构成连五的线。 //定义含有边界所有连线上的棋子,用于更新棋型int searchBoard[boardSize2];int searchBoardMask[boardSize2];int searchBoardVertical[boardSize2];int searchBoardVerticalMask[boardSize2];int searchBoardMainDiag[2*boardSize - 9];int searchBoardMainDiagMask[2*boardSize - 9];int searchBoardSubDiag[2*boardSize - 9];int searchBoardSubDiagMask[2*boardSize - 9];2 实现
有了棋盘信息的表示就需要实现如何更新棋盘信息。这里实现可能略微复杂没有做代码的精简。在象棋百科中有通过棋盘旋转的方式来获取不同方向的信息那里是使用通过和一个魔法数位运算来实现的理论上这里也是可以的。 这里具体实现时需要注意三点一是边界点的判定二是位运算如何某数位置0或者置1,三是位移量的求解。
void GameBoard::setSearchBoardPiece(const MPoint position, MPlayerType player)
{int row position.x();int col position.y();if(!isValidSearchPosition(row,col)) return ;if(player PLAYER_WHITE){//player white(1)searchBoard[row] | (1 col);searchBoardMask[row] | (1 col);searchBoardVertical[col] | (1 row);searchBoardVerticalMask[col] | (1row);//主对角线[右下]if(abs(col-row)boardSize-5){if(rowcol){searchBoardMainDiag[boardSize- 5 - row col] |(1 col);searchBoardMainDiagMask[boardSize- 5 - row col] |(1 col);}else{searchBoardMainDiag[boardSize- 5 col - row] | (1 row);searchBoardMainDiagMask[boardSize- 5 col - row] | (1 row);}}//副对角线[右上]if(rowcol6 rowcol boardSize*2-4){if(col boardSize -row 1){searchBoardSubDiag[row col - 6] | (1 col);searchBoardSubDiagMask[row col - 6] | (1 col);}else{searchBoardSubDiag[rowcol-6] | (1 (boardSize1-row));searchBoardSubDiagMask[rowcol-6] | (1 (boardSize1-row));}}}else if(player PLAYER_BLACK){//player black(0)searchBoard[row] ~(1 col);searchBoardMask[row] | (1 col);searchBoardVertical[col] ~(1 row);searchBoardVerticalMask[col] | (1row);//主对角线if(abs(col-row)boardSize-5){if(rowcol){searchBoardMainDiag[boardSize- 5 - row col] ~(1 col);searchBoardMainDiagMask[boardSize- 5 - row col] |(1 col);}else{searchBoardMainDiag[boardSize- 5 col - row] ~(1 row);searchBoardMainDiagMask[boardSize- 5 col - row] | (1 row);}}//副对角线if(rowcol6){if(col boardSize -row 1){searchBoardSubDiag[row col - 6] ~(1 col);searchBoardSubDiagMask[row col - 6] | (1 col);}else{searchBoardSubDiag[rowcol-6] ~(1 (boardSize1-row));searchBoardSubDiagMask[rowcol-6] | (1 (boardSize1-row));}}}else{//playernone(2)searchBoardMask[row] ~(1 col);searchBoardVerticalMask[col] ~(1 row);searchBoard[row] ~(1 col);searchBoardVertical[col] ~(1 row);//主对角线if(abs(col-row)10){if(rowcol){searchBoardMainDiagMask[boardSize- 5 - row col] ~(1 col);searchBoardMainDiag[boardSize- 5 - row col] ~(1 col);}else{searchBoardMainDiagMask[boardSize- 5 col - row] ~(1 row);searchBoardMainDiag[boardSize- 5 col - row] ~(1 row);}}//副对角线if(rowcol6){if(col boardSize -row 1){searchBoardSubDiagMask[row col - 6] ~(1 col);searchBoardSubDiag[row col - 6] ~(1 col);}else{searchBoardSubDiagMask[rowcol-6] ~(1 (boardSize1-row));searchBoardSubDiag[rowcol-6] ~(1 (boardSize1-row));}}}
}
