java - 递归运行速度非常慢 - AsyncTask

Question

我正在尝试制作一款 TicTacToe 游戏，其中计算机试图获胜而不是失败 - 它部分有效，但代码在 Android 上运行速度非常慢，但在计算机上运行良好。

计算机的决定是在 AsynTask 中做出的，并且 doInBackground 调用 UI 方法。

我不断得到:

D/dalvikvm(14142): GC_CONCURRENT 释放了 1924K，释放了 15% 26534K/30996K，暂停了 2ms+11ms，总计 136ms

和

D/dalvikvm(14142): GC_FOR_ALLOC 释放了 1711K，释放了 12% 24208K/27304K，暂停了 106ms，总计 106ms

这是代码或这里:https://www.dropbox.com/s/xf6dd2mlkqw2rmr/OnePlayer.java

    public class ComputerTurn extends AsyncTask<Void, Integer, Void> {
    ProgressDialog progressDialog;

    public Context activity;

    public ComputerTurn(Context a)
    {
        this.activity = a;
    }

    @Override
    protected void onPreExecute(){
        //progressDialog = ProgressDialog.show(OnePlayer.this, "Progress Dialog Title Text","Process Description Text", true);
    };      
    long interval =0;
    @Override
    protected Void doInBackground(Void... params){
        Date interestingDate = new Date();
        ((OnePlayer) activity).ComputerPromptInputandSet(current_player);
        interval = (new Date()).getTime() - interestingDate.getTime();
        System.out.println("Time: " +interval);
        return null;
    }       

    @Override
    protected void onPostExecute(Void result){
        super.onPostExecute(result);
        AlertDialog.Builder builder = new AlertDialog.Builder(OnePlayer.this);
        builder.setMessage("Time: " +interval)
            .setCancelable(false)
            .setPositiveButton("OK", new DialogInterface.OnClickListener() {
                public void onClick(DialogInterface dialog, int id) {
                    //  do things

                }
            });
        AlertDialog alert = builder.create();
        alert.show();
        //progressDialog.dismiss();
    }
 }

计算机提示输入和设置:

void ComputerPromptInputandSet(int current_player) {
    //task.doProgress(1);
    depth = 0;
    System.out.println("Computer turn");
    bestMoves = new ArrayList<String>();
    drawMoves = new ArrayList<String>();

    for(int i=0; i <3; i++){
        for(int j =0; j <3; j++){
                if(board[i][j].equalsIgnoreCase("-") 
                  && !board[i][j].equalsIgnoreCase("O") 
                  && !board[i][j].equalsIgnoreCase("X")){
                    CompNode currentNode = null;
                    String [][] temp = board;
                    depth = 0;
                    System.out.println("Calling AI");
                    AI(i, j, currentNode, temp, 0);
                    board[i][j]="-";
                    //print(board);
                    //System.exit(0);
             }
        }
    }
    System.out.println("depth of win: " + bestwin_depth);
    System.out.println("depth of draw: " + bestdraw_depth);
    System.out.println("depth of lose: " + bestlose_depth);

    System.out.println("bestwin: " + bestwin);
    System.out.println("bestdraw: " + bestdraw);
    System.out.println("bestlose: " + bestlose);
    WINNER_FOUND = false;
    game_winner = false;
    is_draw = false;

}

人工智能:

void AI(int i, int j, CompNode cNode, String [][] fake, int depth){
    //task.doProgress(1);
    depth++;
    //System.out.println("In AI");
    //System.out.println("Depth: "+ depth);
    fake[i][j] =  getLetter(current_player); 
    //print(fake);
    boolean winner = CheckWinner(1, fake);
    if(winner){
        //System.out.println("Winner move found");
        //print(fake);
        //cNode.value= 1000;
        if(bestwin_depth >= depth){
            bestwin_depth = depth;
            bestwin = i+"/"+j;
        }
        bestMoves.add(i+"/"+j);
        WINNER_FOUND = false;
        game_winner = false;
        is_draw = false;
        return;
    }
    if(is_draw == true){
        //System.out.println("Draw found or no more space");
        drawMoves.add(i+"/"+j);
        WINNER_FOUND = false;
        game_winner = false;
        is_draw = false;
        return;
    }

    /*  check if game over on move
        if over 
            return
        if not over for comp

    */ 
    ArrayList<String> indexes = getLegalMoves(fake);
    //System.out.println("Legal Moves: "+ indexes.size());
    if(indexes.size() ==0){
        //System.out.println("Draw found or no more space");
        if(bestdraw_depth >= depth){
            bestdraw_depth = depth;
            bestdraw = i+"/"+j;
        }   
        drawMoves.add(i+"/"+j);
        return;
    }
    //permute (indexes, 0, i, j, cNode, fake);
    cNode = new CompNode(indexes.size(), i , j);

    Iterator sets = indexes.iterator();
    PlayerNode [] possibleMove = cNode.children;
    int k =0;


    while (sets.hasNext() ) {
        String index = (String) sets.next();

        String [] index_ =  index.split("/");
        int x = Integer.parseInt(index_[0]);
        int y = Integer.parseInt(index_[1]);

        //System.out.println("( "+x + ", " +y + " )");
        possibleMove[k] = new PlayerNode(indexes.size()-1, x, y);
        String [][]temp = fake;
        playerMove(x, y , possibleMove[k], temp, depth);
        //depth--;

        fake[x][y] = "-";
        k++;
    }
    //System.exit(0);
}

玩家移动:

void playerMove(int i, int j, PlayerNode pNode, String [][]fake, int depth){
    //task.doProgress(1);
    depth++;
    //System.out.println("In playMove");
    //System.out.println("Player move: ");
    //System.out.println("Depth: "+ depth);
    fake[i][j] =  getOtherLetter(current_player); 
    //print(fake);

    boolean winner = CheckWinner(0, fake);
    pNode = new PlayerNode(0, 0, 0);
    if(winner){
        //System.out.println("Player winning move");
        if(bestlose_depth >= depth){
            bestlose_depth = depth;
            bestlose = i+"/"+j;
        } 
       // pNode.value= -1000;
        WINNER_FOUND = false;
        game_winner = false;
        is_draw = false;
        return;
    }
    if(is_draw == true){
        //System.out.println("Draw found or no more space");
        drawMoves.add(i+"/"+j);
        WINNER_FOUND = false;
        game_winner = false;
        is_draw = false;
        return;
    }

    ArrayList<String> indexes = getLegalMoves(fake);
    //System.out.println("Legal Moves: "+ indexes.size());
    if(indexes.size() ==0){
        //System.out.println("Draw found or no more space");
        if(bestdraw_depth >= depth){
            bestdraw_depth = depth;
            bestdraw = i+"/"+j;
        } 

        drawMoves.add(i+"/"+j);
        return;
    }
    //permutePlayer (indexes, 0, i, j, pNode, fake);
    pNode = new PlayerNode(indexes.size(), i , j);

    Iterator sets = indexes.iterator();
    CompNode [] possibleMove = pNode.children;
    int k =0;


    while (sets.hasNext() ) {
        String index = (String) sets.next();

        String [] index_ =  index.split("/");
        int x = Integer.parseInt(index_[0]);
        int y = Integer.parseInt(index_[1]);

        //System.out.println("( "+x + ", " +y + " )");
        possibleMove[k] = new CompNode(indexes.size()-1, x, y);
        String [][] temp = fake;
        AI(x, y , possibleMove[k], temp, depth);
        //depth--;
        fake[x][y] = "-";
        k++;
    }
    //System.exit(0);
}

PlayerNode类

class PlayerNode {
    CompNode [] children;

    PlayerNode(int num, int i , int j){
    this.children = new CompNode[num];
    }
}

CompNode 类:

class CompNode {
    PlayerNode [] children;

    CompNode(int num, int i, int j){
        this.children = new PlayerNode[num];
    }
}

ComputerPromptInputandSet 在我的手机上运行需要 52 秒，在模拟器上运行需要 2 分钟，在另一部手机上运行需要 34 秒。

这是统计屏幕截图:

我该如何解决这个问题？

Answer 1

你的电脑比你的手机快大约 500 倍，我对吗？这很可能是正常的，可能是由于移动内存有限，这会更频繁地调用垃圾收集器。

一般优化应该可以解决问题。

代码非常复杂，我不太理解它，但如果 getLegalMoves 方法做了我认为你应该能够通过消除玩家已经在同一位置交叉的 Action 来返回较少可能的 Action 来极大地优化它x 轴和 y 轴以及对角线。