我想使用极小化极大搜索（带有alpha-beta剪枝），或者更具体地说是负极大搜索，来开发一个玩纸牌游戏的电脑程序。
这个纸牌游戏实际上有4个玩家。为了能够使用极小化极大搜索等算法，我将游戏简化为“我”对抗“其他人”。每次“移动”后，你可以从游戏本身客观地读取当前状态的评估。当所有4个玩家都放置了卡片后，得分最高的玩家赢得所有卡片——卡片的数值是计分的依据。
由于你不知道其他3个玩家之间的卡片分配情况，我认为你必须模拟所有可能的卡片分配情况（“世界”），这些卡片是你之外的。你的卡片有12张，其他3个玩家总共有36张卡片。
因此，我的算法方法是这样的，其中player是一个介于1到3之间的数字，代表程序可能需要为其寻找移动的三个电脑玩家。而-player代表对手，即所有其他三个玩家一起。
private Card computerPickCard(GameState state, ArrayList<Card> cards) { int bestScore = Integer.MIN_VALUE; Card bestMove = null; int nCards = cards.size(); for (int i = 0; i < nCards; i++) { if (state.moveIsLegal(cards.get(i))) { // 如果允许放置这张卡片 int score; GameState futureState = state.testMove(cards.get(i)); // 移动是放置一张卡片（返回一个新的游戏状态） score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE); if (score > bestScore) { bestScore = score; bestMove = cards.get(i); } } } // 现在bestMove是应该放置的卡片}private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) { ArrayList<Card> cards; if (player >= 1 && player <= 3) { cards = state.getCards(player); } else { if (player == -1) { cards = state.getCards(0); cards.addAll(state.getCards(2)); cards.addAll(state.getCards(3)); } else if (player == -2) { cards = state.getCards(0); cards.addAll(state.getCards(1)); cards.addAll(state.getCards(3)); } else { cards = state.getCards(0); cards.addAll(state.getCards(1)); cards.addAll(state.getCards(2)); } } if (depthLeft <= 0 || state.isEnd()) { // 递归结束，因为游戏结束或达到最大深度 if (player >= 1 && player <= 3) { return state.getCurrentPoints(player); // 玩家的得分为正值（对于自己） } else { return -state.getCurrentPoints(-player); // 玩家的得分为负值（对于其他人） } } else { int score; int nCards = cards.size(); if (player > 0) { // 进行一次移动（轮到玩家） for (int i = 0; i < nCards; i++) { GameState futureState = state.testMove(cards.get(i)); if (futureState != null) { // 如果移动有效 score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha); if (score >= beta) { return score; } if (score > alpha) { alpha = score; // alpha 像 max 一样作用 } } } return alpha; } else { // 进行三次移动（轮到其他人） for (int i = 0; i < nCards; i++) { GameState futureState = state.testMove(cards.get(i)); if (futureState != null) { // 如果移动有效 for (int k = 0; k < nCards; k++) { if (k != i) { GameState futureStateLevel2 = futureState.testMove(cards.get(k)); if (futureStateLevel2 != null) { // 如果移动有效 for (int m = 0; m < nCards; m++) { if (m != i && m != k) { GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m)); if (futureStateLevel3 != null) { // 如果移动有效 score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha); if (score >= beta) { return score; } if (score > alpha) { alpha = score; // alpha 像 max 一样作用 } } } } } } } } } return alpha; } }}这似乎运行良好，但是对于深度为1（depthLeft=1），程序平均需要计算50,000次移动（放置的卡片）。这当然太多了！
所以我的问题是：
- 这个实现是否完全正确？你能模拟这样的游戏吗？特别是关于信息不完全的情况？
- 如何在速度和工作量上改进算法？
- 例如，我可以将可能的移动集合减少到一个随机的50%来提高速度，同时保持良好的结果吗？
- 我发现UCT算法可能是一个好的解决方案。你了解这个算法吗？你能帮助我实现它吗？
回答：
你所实现的极小化极大搜索对于信息不确定性如此大的游戏来说是错误的方法。由于你不知道其他玩家之间的卡片分配，你的搜索将花费指数级的时间来探索给定实际卡片分配情况下不可能发生的游戏。
我认为更好的方法是从当你对其他玩家手牌几乎没有或完全没有信息时开始制定良好的游戏规则。比如：
- 如果你在回合中首先出牌，玩你最低的牌，因为你赢得这一回合的机会很小。
- 如果你在回合中最后出牌，玩你能赢得这一回合的最低牌。如果你不能赢得这一回合，那么玩你最低的牌。
让你的程序最初不进行搜索，只按照这些规则玩游戏，并且假设所有其他玩家也会使用这些启发式方法。随着程序观察到每回合第一个和最后一个玩家出的牌，它可以建立一个关于每个玩家可能持有的牌的表格。例如，一张9点牌本可以赢得这一回合，但玩家3没有出这张牌，所以他一定没有9点或更高的牌。随着关于每个玩家手牌的信息的收集，搜索空间最终将被限制到极小化极大搜索可能的游戏可以提供关于下一步该出哪张牌的有用信息的程度。
