Minimax的實現不適用於遞歸和C++

我基本上有一個遊戲板，玩家不能一次移動到同一個地方，否則你會失敗。玩家只能移動-1，+1，-16或+16。我想用minimax解決這個問題，並接收minimax使用的輸入，以便我可以看到它是如何完成的。Minimax的實現不適用於遞歸和C++

這是我目前做的如何

#pragma optimize("", off) 

#include <stdio.h> 
#include <Windows.h> 

#define hitcount 4 

#define POINT 1 
#define MINE 2 
#define END 3 

//4 targets: hit all 1's 
//player/mine is 2 
//game ender is 3 
int Board[] = { 
    0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 1, 0, 
    2, 0, 0, 1, 0, 0, 1, 
    0, 0, 0, 0, 0, 0, 0, 
    3, 0, 0, 0, 0, 0, 0 
}; 

static const int choices[] = { 
    -1, 1, -16, 16 
}; 

struct mb { 
    int end; 
    int score; 
    int* moveset; 
}; 

mb solve(int Position, int *Board, int BoardSize, int *MoveSet = NULL, int Offset = 0, int Choice = 0, int Score = 0, bool tree = true) { 
    if(tree) { //tree 
     int *BoardCopy = new int[BoardSize];   

     for(int i = 0; i < sizeof(choices); i++) { 
      MoveSet = new int[256]; 
      for(int i = 0; i < 256; i++) 
       MoveSet[i] = 0xFF; 

      memcpy(BoardCopy, Board, BoardSize); 
      mb m = solve(Position, BoardCopy, BoardSize, MoveSet, Offset, i, Score, false); 

      if(m.moveset != NULL) {    
       if(m.end == 1 && m.score == hitcount) { 
        delete[] BoardCopy; 
        return m; 
       }    

      } 

      delete[] MoveSet; //this is apparently causing problems?? 
     } 

     delete[] BoardCopy; 

    } 
    else { //branch 
     mb m = {0, 0, MoveSet}; 

     Position += choices[Choice]; 
     m.moveset[Offset] = choices[Choice]; 
     if(Position < 0 || Position >= BoardSize || Board[Position] == MINE || (Board[Position] == END && Score != hitcount)) { 
      m.moveset = NULL; 
      return m; 
     } 
     else if(Board[Position] == POINT) { 
      m.score++; 
     } 
     else if(Board[Position] == END) { 
      m.end = 1; 
      return m; 
     } 

     Board[Position] = MINE; 

     return solve(Position, Board, BoardSize, m.moveset, Offset + 1, Choice + 1, m.score); 

    } 

    mb m = {0, 0, NULL}; 
    return m; 
} 


int main() { 

    int Position = 0; 
    for(int i = 0; i < sizeof(Board); i++) { 
     if(Board[i] == MINE) Position = i; 
    } 

    mb m = solve(Position, Board, sizeof(Board)); 
    if(m.end == 1 && m.moveset != NULL && m.score == hitcount) { 
     printf("SUCCESS!\n"); 
    } 

    getchar(); 
    return 0; 
}

但是，這是行不通的。我無法弄清楚爲什麼。該算法看起來應該可以工作，而我的問題看起來與內存清理有關。我的VC++工作室斷點在_CrtIsValidHeapPtr調用幾次解決後

來源

2013-09-28 Jason

我無法證實算法的正確性。但是，編碼錯誤會導致您應該解決的未定義行爲。

主要問題是您將數組大小與數組中的元素數混淆。在您的main()中，您應該使用sizeof(Board)/sizeof(*Board)來確定Board的數組元素的數量，否則您將讀取Board的數組邊界之外。然後，您通過sizeof(Board)作爲BoardSize到solve，但是當您檢查Position是否在範圍內時，這不是正確的值。您的外部for循環也錯誤地計算了choices的數組元素的數量。

作爲一個次要的問題，你是掩蓋在solve()在內for循環命名i另一個變量的i循環變量名。爲了避免混淆，可能應該重新命名。

因此，這些想法，我會在main()改變：

for(int i = 0; i < sizeof(Board)/sizeof(*Board); i++) { 
     if(Board[i] == MINE) Position = i; 
    } 

    mb m = solve(Position, Board, sizeof(Board)/sizeof(*Board));

然後，我會在solve()改變：

 for(int i = 0; i < sizeof(choices)/sizeof(*choices); i++) { 
      MoveSet = new int[256]; 
      for(int j = 0; j < 256; j++) 
       MoveSet[j] = 0xFF; 

      memcpy(BoardCopy, Board, BoardSize*sizeof(int));

而且，你能避免在代碼中new/delete業務對於BoardCopy和MoveSet使用std::vector<int>相當容易。例如：

 std::vector<int> BoardCopy(BoardSize); 

     //... 
      std::copy(Board, Board+BoardSize, BoardCopy.begin());

要傳遞的，你有你的代碼int *參數，你會通過在&BoardCopy[0]，但你應該考慮修改代碼以採取std::vector<int> &。當你這樣做時，你可以刪除所有呼叫到delete BoardCopy。

來源

2013-09-28 03:04:52 jxh

Minimax的實現不適用於遞歸和C++

回答

相關問題