Algorithm to find best strategy for placing blocks
This game has a grid size 8x8. At the beginning of each round the player draws 3 blocks at random he must place on the grid. Placing a block is worth its area in points, and completing a row or column is worth 80 points, and that row or column is cleared from the board. The blocks do not move down after squares are cleared like in tetris.
If no more blocks can be placed, the game is over. The object of the game is to maximize your score.
Example:
Example video
I am looking to create a program that will find the best possible strategy for placing blocks, when provided with the three blocks available to the user.
Currently, I have code to create a grid and a list of blocks.
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"]])
]
The code I used to create the grid is found here https://gist.github.com/Olical/2306105 (not mine)
My current approach would just be to search though the grid 1 place at a time for each piece to find somewhere to place it, although this doesn't seem very efficient.
What algorithm could/should I use in order to find this?
If you want a very simple approximation to the best strategy you can use a greedy strategy of trying to clear as many lines as possible in the current round.
You can also write a simple evaluation function to favor things like tight packing of blocks, leaving holes that future block shapes might fit nicely, etc.
However, I suspect this will be far from optimal because you may clear a line but leave a huge mess behind which will be hard to clear in future rounds.
If you want to find the optimal placement of the three blocks you will have to solve the entire game tree, since the block placements decides not only your score for the current round, but also how well you will do in future rounds.
Since the game tree is far to large to solve completely, you will have to find a good approximate solution. For a number of reasons, I think this problem is a good candidate for Monte Carlo Tree Search, for example:
The game tree will have two kinds of nodes: player nodes and chance nodes. Each player node represents one block placements on the board, and each chance node represents the three blocks you draw at random at the beginning of the round which the player has no control over.
The pseudocode for the MCTS algorithm for this game will be:
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)
You'll want to use total_score/visits in the UCT score (rather than wins/visits for two-player games), and you can propagate the score up the tree by storing total score and visits at each node and adding the score of the current simulation to the total score and by incrementing the visit count.
上一篇: 编译器是否允许像Intel C ++编译器一样去除无限循环
下一篇: 寻找放置块的最佳策略的算法