寻找放置块的最佳策略的算法
这款游戏的网格尺寸为8x8。 在每轮开始时，玩家随机抽取3个方块，他必须放在网格上。 放置一个块值得分，并且完成一行或一列的值为80分，并且该行或列从板上清除。 正方形像俄罗斯方块一样清除后，块不会向下移动。
如果没有更多的块可以放置，游戏结束。 游戏的目标是最大化你的分数。
例：
示例视频
我希望创建一个程序，在为用户提供三个块的情况下，可以找到放置块的最佳策略。
目前，我有代码来创建网格和块列表。
class Piece():
def __init__(self, shape):
self.shape = shape
def __str__(self):
return self.render()
def render(self):
res = []
for row in self.shape:
res.append("".join(row)+"n")
return "".join(res)
pieces = [Piece([["x"]]),
Piece([["x", "x"]]),
Piece([["x", "x", "x"]]),
Piece([["x", "x", "x", "x"]]),
Piece([["x"],["x"]]),
Piece([["x"], ["x"], ["x"]]),
Piece([["x"], ["x"], ["x"], ["x"]]),
Piece([["x", "x"], ["x", "x"]]),
Piece([["x", "x"], ["x"]]),
Piece([["x"], ["x", "x"]]),
Piece([[" ", "x"], ["x", "x"]]),
Piece([["x", "x"], [" ", "x"]]),
Piece([["x", "x", "x"], ["x"], ["x"]]),
Piece([["x", "x", "x"], [" ", " ", "x"], [" ", " ", "x"]]),
Piece([[" ", " ", "x"], [" ", " ", "x"], ["x", "x", "x"]]),
Piece([["x"], ["x"], ["x", "x", "x"]])
]
我用来创建网格的代码在这里找到https://gist.github.com/Olical/2306105（不是我的）
我目前的做法只是搜索网格1的位置，以找到放置它的地方，尽管这看起来效率不高。
我可以/应该使用什么算法来找到它？
如果你想要一个非常简单的近似最佳策略，你可以使用一个贪婪的策略来尝试在当前一轮中尽可能多的清除行。
你也可以编写一个简单的评估函数来支持块的紧凑包装，留下未来块形状可能适合的洞等。
不过，我怀疑这样做会远远不够理想，因为你可能会清除一条线，但是会留下一个巨大的混乱，在未来几轮很难清除。
如果你想找到三个块的最佳位置，你必须解决整个游戏树，因为块位置不仅决定你当前回合的得分，而且决定你在未来回合中的得分。
由于游戏树远远大于完全解决，你将不得不寻找一个好的近似解决方案。 出于多种原因，我认为这个问题是蒙特卡罗树搜索的一个很好的候选者，例如：
游戏树将有两种节点：玩家节点和机会节点。 每个玩家节点代表棋盘上的一个块放置，每个机会节点代表在玩家无法控制的回合开始时随机抽取的三个块。
该游戏的MCTS算法的伪代码将是：
def MCTS(root, board, n_sims):
for 1...n_sims:
b = board.copy()
cur_node = root
while cur_node.vists >= expand_threshold:
if cur_node is expanded:
if cur_node is chance node:
cur_node = sample child uniformly at random
else:
cur_node = child that maximizes UCT score
b.update(cur_node) # update the board position with the block placement or the new three block draw
else if b.game_over():
break
else:
expand(cur_node, b) # add all child nodes to tree
score = b.roll_out() # play random moves to the end of the game and return final score
cur_node.backprop(score) # propagate score and visit back up tree
return most visited child of root
root = new Node(parent=null, total_score=0, visits=0)
board = new Board(current position)
best_move = MCTS(root, board, 10000)
print(best_move)
您需要在UCT得分中使用total_score/visits （而不是双人游戏的胜利/访问），并且可以通过在每个节点上存储总得分和访问并将分数目前的模拟总分和增加访问计数。
上一篇: Algorithm to find best strategy for placing blocks
下一篇: Count number of ways player 1 can win in a 2 player game