2048 A.I. 在 * 上有个讨论：http://*.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 = ;
while (mc_count < kMonteCarloGameCount) {
FullBoard current_node;
Orientation orientation = MaxUcbMove(full_board);
current_node.Copy(full_board);
current_node.PlayMovingMove(orientation);
NewProfit(¤t_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(, 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 + );
node_record->SetAverageProfit(average_profit);
} node_record->SetVisitedTimes(visited_times + );
} 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 = ; i < ; ++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
最后发个招聘链接：http://www.kujiale.com/about/join
我这块的工作主要是站内搜索、推荐算法等，欢迎牛人投简历到hr邮箱~