Code Monkey home page Code Monkey logo

simpletetris's Introduction

  • 学习Android练手作品
  • bingghost

俄罗斯方块AI设计文档

一.概要

使用了2种AI算法:

  • 一种是经典的Pierre Dellacherie算法
  • 一种基于基于深度搜索的算法:

由于时间因素,只测试了一次Pierre Dellacherie算法,消行数13W+ 第2种算法没有花时间去测试,理论上消行数应该比较可观

image

下面简单介绍2种AI算法实现思路

二.Pierre Dellacherie算法:(只考虑当前方块)

Pierre Dellacherie官网: http://imake.ninja/el-tetris-an-improvement-on-pierre-dellacheries-algorithm/

AI算法主要是评分函数: 所以只介绍评分函数 尝试着对当前落子的每一种旋转变换、从左到右地摆放,产生所有摆法。 对每一种摆法进行评价。评价包含如下6项指标

1.下落高度(Landing Height):

当前方块落下去之后,方块中点距底部的方格数 事实上,不求中点也是可以的,详见官网

我实现的方法是分别求出当前方块固定后, 最高点和最低点之和的平均值

2.消行数(Rows eliminated)

消行层数与当前方块贡献出的方格数乘积

3.行变换(Row Transitions):
  • 从左到右(或者反过来)检测一行,当该行中某个方格从有方块到无方块(或无方块到有方块),
  • 视为一次变换。游戏池边界算作有方块。行变换从一定程度上反映出一行的平整程度,越平整值越小
  • 该指标为所有行的变换数之和
  • 如图:■表示有方块,□表示空格(游戏池边界未画出)
  • ■■□□■■□□■■□□ 变换数为6
  • □□□□□■□■□■□■ 变换数为9
  • ■■■■□□□□□□■■ 变换数为2
  • ■■■■■■■■■■■■ 变换数为0
4.列变换(Column Transitions):大意同上

列变换从一定程度上反映出一列中空洞的集中程度,空洞越集中值越小

5.空洞数(Number of Holes)

不解释

6.井的总和(Well Sums):

井指两边皆有方块的空列。该指标为所有井的深度连加到1再求总和 注意一列中可能有多个井,如图:

  •    ■□□ 
    
  •    ■□■ 
    
  •    ■□■ 
    
  •    ■■■ 
    
  •    ■□■ 
    
  •    ■□■ 
    
  •    ■□■ 
    

中间一列为井,深度连加到一的和为 (2+1)+(3+2+1)=9

各项指标权重经验值:
索引 权重
1 -4.500158825082766
2 3.4181268101392694
3 -3.2178882868487753
4 -9.348695305445199
5 -7.899265427351652
6 -3.3855972247263626
最后的评分函数:
    private void PierreDellacherie(int boxIndex,int releaseLines) {
        int highestY = calcApex(mFirstBoxs);
        
        int landingHeight = landingHeight(boxIndex);
        int erodedPieceCellsMetric = erodedPieceCellsMetric(mFirstBoxs,mCurX,mCurY,boxIndex,releaseLines);
        int boardRowTransitions = boardRowTransitions(mFirstBoxs,highestY);
        int boardColTransitions = boardColTransitions(mFirstBoxs,highestY);
        int boardBuriedHoles = boardBuriedHoles(mFirstBoxs,highestY);
        int boardWells = boardWells(mFirstBoxs,highestY);
        
        int score = -45*landingHeight + 34*erodedPieceCellsMetric -
        32*boardRowTransitions -
        93*boardColTransitions -
        79*boardBuriedHoles -
        34*boardWells;
    
        refreshScore(score);
    }  

##三.基于深度搜索(考虑下一个方块)

1.深度搜索模型

假设游戏宽度为10,只考虑平移下落的可能,在极端的情况下,方块有4种旋转类型 (可以做表优化)

那么对于当前方块则有 410 = 40种下落情况 那么有 下一个方块有 410 = 40种下落情况

深度遍历则有 40 * 40 = 1600种情况 所以Tetris的AI算法是常量阶

    public void seekBestStrategy() {
        // 获取当前游戏模型最高点

        // 深度搜索存在的情况
        for (int rotate = 0;rotate < getRotateCount(mCurType);rotate++) {
            for (int i = 0;i < mTetrisGame.mGameWidth - 2;i++) {
                // 检测当前坐标是否能移动

                // 模拟下落 (类似与人类在大脑思考某种行为的后果如何)

                // 设置当前状态
                
                // 消行
                
                // 遍历下一个方块 (遍历下一个方块函数功能和本函数类似,只是该调用变成了评价函数)
                
                // 恢复背景数组状态(最高点向下copy)
            }
        }
        
        // 找到一个最佳点
        setFind(true);
    }  
2.评价函数
a. 脑残评价策略

只考虑2次消行数, 和2次游戏后最终局面的高度 这样会造成大量空洞,游戏很快死掉

b. 简单评价策略

在脑残策略的基础上增加了每列的空洞数量 实现方法也很简单,从最高点向下找空洞

有所改善,但是还是很快死掉

####c. 高端策略

在简单策略的基础上增加:

  • a. 高度差之和
  • b. 高山数量 (当前列高于临近列)
  • c. 深坑数量 (当前列低于临近列)
  • d. 平均高度 上面的一些权值反映游戏局面地势的平缓程度 然后每种取不同权值,权值不同AI效果不同 (经验主义)

游戏截图

image

image

image

image

image

simpletetris's People

Contributors

bingghost avatar

Stargazers

young avatar

Watchers

James Cloos avatar young avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.