改How to win the 2048.docxVIP

How to win the 2048？1.Summary(摘要)对于目前火爆的2048游戏，设计一个简单的程序，可以以较大概率赢得游戏。本文将首先对其中用到的基础算法，即Minimax算法和Alpha-beta剪枝算法做简要介绍，然后说明怎样将其具体运用到本游戏中并取得最大value of a tile。Minimax算法是通过对以当前格局为根的格局树的有哪些信誉好的足球投注网站来确定下一步的选择。Alpha-beta剪枝算法核心思想是时时刻刻记得当前已经知道的最好选择，如果从当前格局有哪些信誉好的足球投注网站下去，不可能找到比已知最优解更好的解，则停止这个格局分支的有哪些信誉好的足球投注网站（剪枝），回溯到父节点继续有哪些信誉好的足球投注网站。题设要求游戏拼出2048这个值，根据游戏规则每一步均有四个可移动的方向可供选择，我们的任务是对移动做出选择。这里首先运用Minimax算法，以求对假设的每一步的选择做出一定的评估，根据评估结果的好坏决定当前行走的策略。游戏进行到某种状态上下左右四种选择对应最大最小树的树干，将每一次移动后的状态作为树枝，假定电脑总是选择对玩家最不利的位置填充数，而玩家是从这样的位置中挑选最好的移动方法。考虑移动D（井深）步以后每一种情况所形成的格局，根据评价函数评价所得格局的好坏，从中选择格局最好的一条路径，选择这一条路径作为我们要走的路径，以此类推。如果想获得理想的结果，则井深不能太小，可是井深较大的话会导致计算量太大，所以我们采用Alpha-beta算法来解决这个问题。这里关键是评估函数的选择，文中考虑了单调性、平滑性和空格数的影响因素，加入影响因子，选取线性函数作为评估函数。根据这种策略，每走一步选择最优走法，对于第一问一旦出现2048即停止运行，统计移动步数，对于第二问则不限制最大值，直到格子填满为止。Key words: 2.Introduction(问题重述)1.1Background(背景介绍)The intelligence game ‘2048’ is sweeping the global. Plenty of players claim that they cannot help beginning another attempt, getting 2048! 2048 is played on a simple gray 4×4 grid with simple principles: all tiles slide to the same direction at each move; if two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided; and a new tile will randomly appear in an empty spot on the outer frame of the board with a value of either 2 or 4 after each turn. The game is won when a tile with a value of 2048 appears on the board. On the contrary, if there are no empty spaces and no adjacent tiles with the same value (i.e. no more moves are allowed), the game ends.1.2Questions(问题提出)Build a mathematical model to deal with the following questions:1. Provide a model in order to win this game. To test the performance of your algorithm, you should consider the number of moves and the probability of winning this game.2. If further moves are allowed when a value of 2048 appears, what will be the maximum value of a tile? If the game’s grip is extended to N×N, what will be the maxi