基于Monte Carlo方法的2048 A.I.

本文发布时间: 2019-Mar-22
2048 A.I. 在 stackoverflow 上有个讨论:http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048得票最高的回答是基于 Min-Max-Tree + alpha beta 剪枝,启发函数的设计很优秀。其实也可以不用设计启发函数就写出 A.I. 的,我用的方法是围棋 A.I. 领域的经典算法——Monte Carlo 局面评估 + UCT 搜索。算法的介绍见我几年前写的一篇博文:http://www.cnblogs.com/qswang/archive/2011/08/28/2360489.html简而言之就两点:通过随机游戏评估给定局面的得分; 从博弈树的父节点往下选择子节点时,综合考虑子节点的历史得分与尝试次数。针对2048游戏,我对算法做了一个改动——把 Minx-Max-Tree 改为 Random-Max-Tree,因为增加数字是随机的,而不是理性的博弈方,所以猜想 Min-Max-Tree 容易倾向过分保守的博弈策略,而不敢追求更大的成果。UCT搜索的代码:Orientation UctPlayer::NextMove(const FullBoard& full_board) const { int mc_count = 0; while (mc_count < kMonteCarloGameCount) { FullBoard current_node; Orientation orientation = MaxUcbMove(full_board); current_node.Copy(full_board); current_node.PlayMovingMove(orientation); NewProfit(&current_node, &mc_count); } return BestChild(full_board);}NewProfit函数用于更新该节点到某叶子节点的记录,是递归实现的:float UctPlayer::NewProfit(board::FullBoard *node, int* mc_count) const { float result; HashKey hash_key = node->ZobristHash(); auto iterator = transposition_table_.find(hash_key); if (iterator == transposition_table_.end()) { FullBoard copied_node; copied_node.Copy(*node); MonteCarloGame game(move(copied_node)); if (!HasGameEnded(*node)) game.Run(); result = GetProfit(game.GetFullBoard()); ++(*mc_count); NodeRecord node_record(1, result); transposition_table_.insert(make_pair(hash_key, node_record)); } else { NodeRecord *node_record = &(iterator->second); int visited_times = node_record->VisitedTimes(); if (HasGameEnded(*node)) { ++(*mc_count); result = node_record->AverageProfit(); } else { AddingNumberRandomlyPlayer player; AddingNumberMove move = player.NextMove(*node); node->PlayAddingNumberMove(move); Orientation max_ucb_move = MaxUcbMove(*node); node->PlayMovingMove(max_ucb_move); result = NewProfit(node, mc_count); float previous_profit = node_record->AverageProfit(); float average_profit = (previous_profit * visited_times + result) / (visited_times + 1); node_record->SetAverageProfit(average_profit); } node_record->SetVisitedTimes(visited_times + 1); } return result;}起初用结局的最大数字作为得分,后来发现当跑到512后,Monte Carlo棋局的结果并不会出现更大的数字,各个节点变得没有区别。于是作了改进,把移动次数作为得分,大为改善。整个程序的设计分为 board、player、game 三大模块,board 负责棋盘逻辑,player 负责移动或增加数字的逻辑,game把board和player连起来。Game类的声明如下:class Game {public: typedef std::unique_ptr<player::AddingNumberPlayer> AddingNumberPlayerUniquePtr; typedef std::unique_ptr<player::MovingPlayer> MovingPlayerUniquePtr; Game(Game &&game) = default; virtual ~Game(); const board::FullBoard& GetFullBoard() const { return full_board_; } void Run();protected: Game(board::FullBoard &&full_board, AddingNumberPlayerUniquePtr &&adding_number_player, MovingPlayerUniquePtr &&moving_player); virtual void BeforeAddNumber() const { } virtual void BeforeMove() const { }private: board::FullBoard full_board_; AddingNumberPlayerUniquePtr adding_number_player_unique_ptr_; MovingPlayerUniquePtr moving_player_unique_ptr_; DISALLOW_COPY_AND_ASSIGN(Game);};Run函数的实现:void Game::Run() { while (!HasGameEnded(full_board_)) { if (full_board_.LastForce() == Force::kMoving) { BeforeAddNumber(); AddingNumberMove move = adding_number_player_unique_ptr_->NextMove(full_board_); full_board_.PlayAddingNumberMove(move); } else { BeforeMove(); Orientation orientation = moving_player_unique_ptr_->NextMove(full_board_); full_board_.PlayMovingMove(orientation); } }}这样就可以通过继承 Game 类,实现不同的构造函数,组合出不同的 Game,比如 MonteCarloGame 的构造函数:MonteCarloGame::MonteCarloGame(FullBoard &&full_board) : Game(move(full_board), std::move(Game::AddingNumberPlayerUniquePtr( new AddingNumberRandomlyPlayer)), std::move(Game::MovingPlayerUniquePtr(new MovingRandomlyPlayer))) {}一个新的2048棋局,会先放上两个数字,新棋局应该能方便地build。默认应该随机地增加两个数字,builder 类可以这么写:template<class G>class NewGameBuilder {public: NewGameBuilder(); ~NewGameBuilder() = default; NewGameBuilder& SetLastForce(board::Force last_force); NewGameBuilder& SetAddingNumberPlayer(game::Game::AddingNumberPlayerUniquePtr &&initialization_player); G Build() const;private: game::Game::AddingNumberPlayerUniquePtr initialization_player_;};template<class G>NewGameBuilder<G>::NewGameBuilder() : initialization_player_(game::Game::AddingNumberPlayerUniquePtr( new player::AddingNumberRandomlyPlayer)) {}template<class G>NewGameBuilder<G>& NewGameBuilder<G>::SetAddingNumberPlayer( game::Game::AddingNumberPlayerUniquePtr &&initialization_player) { initialization_player_ = std::move(initialization_player); return *this;}template<class G>G NewGameBuilder<G>::Build() const { board::FullBoard full_board; for (int i = 0; i < 2; ++i) { board::AddingNumberMove move = initialization_player_->NextMove(full_board); full_board.PlayAddingNumberMove(move); } return G(std::move(full_board));}很久以前,高效的 C++ 代码不提倡在函数中 return 静态分配内存的对象,现在有了右值引用就方便多了。main 函数:int main() { InitLogConfig(); AutoGame game = NewGameBuilder<AutoGame>().Build(); game.Run();}./fool2048:这个A.I.的移动不像基于人为设置启发函数的A.I.那么有规则,不会把最大的数字固定在角落,但最后也能有相对不错的结果,游戏过程更具观赏性~项目地址:https://github.com/chncwang/fool2048


(以上内容不代表本站观点。)
---------------------------------
本网站以及域名有仲裁协议。
本網站以及域名有仲裁協議。

2019-May-25 12:57pm
栏目列表