Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Xin Phân Tích Giúp Code Của Project Này.

  1. #1
    Ngày gia nhập
    02 2009
    Bài viết
    0

    Mặc định Xin Phân Tích Giúp Code Của Project Này.

    Chào các bạn!

    Dưới dây là bài tập lớn đàu tiền mà mình nhận từ thầy giáo của mình. Chỉ yêu cầu ngồi phân tích thuật toán. Thầy nói là dùng thuật toán Depth search nhưng sao mình đọc hoài vẫn không nắm bắt được dù có chú thích tiếng anh. Xin các bạn phân tích và chỉ cho mình con đường sáng.

    Chân thành cám ơn.

    Code:
    /* NOTE:  There is NO randomization here.  When the computer
    	makes a move once.  If the board is the same, it will
       make the same move in every case (or it should at least)
    */
    
    #include <iostream.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #define NUMROWS 4
    
    class Move
    {
    public:
    	int from;
       int to;
    
       Move(int a, int b)
       { from = a; to = b;}
    };
    
    static void display(int*); //Shows the board
    static int Sum(int*);  //Returns total number of pieces left
    void play();  //Begins the game
    void initialize(int*, Move&);   //First step into search
    int recur(int*, int);  //Recursive search method
    int evaluate(int*);  //Evaluates board position at specified depth
    int skill = 7;  //SET SKILL LEVEL BY CHANGING THIS NUMBER
    //NOTE:  Skill level MUST be an odd number for algorithm to work
    
    int main()
    {
    int skill_choice;
    
    cout << "This is the original version of the classic game of Nim.\n";
    cout << "...at least as far as I know.  The object is to force your\n";
    cout << "opponent to take the last piece.  You can take any number\n";
    cout << "of pieces from ONE AND ONLY ONE row per turn.  The \n";
    cout << "computer will then think and take its turn.  Who ever\n";
    cout << "is next when only one piece remains loses.\n\n\n";
    
    do{
    cout << "Choose skill level:\n";
    cout << "(0) Beginner\n";
    cout << "(1-3) Intermediate to advanced\n";
    cout << "(4) Computer is very good (but takes awhile to think)\n";
    cin >> skill_choice;
    } while(skill_choice >4 || skill_choice < 0);
    skill = skill_choice*2 +1;
    
    while(1){
    int again;
    play();
    cout << "\n\n\nPlay again:\n";
    cout << "(1) Yes\n(2) No\n";
    cin >> again;
    if(again != 1) break;
    }
    }
    
    
    void play()
    {
    int sum;
    
    /*  This initializes the number of pieces in each row
        (row 0 is ignored).  Change these numbers to make
        variations of the game.
    */
    int row[4] = {0, 3, 5, 7};
    int whichrow, howmany;
    
    display(row);
    
    /*Start game and repeat until it's over*/
    while(1)
    {
    
    /*GET INPUT FROM PLAYER AND ENSURE VALIDITY*/
    cout << "Which row will you take pieces from (1-3): ";
    cin >> whichrow;
    while(whichrow < 1 || whichrow > 3 || row[whichrow] <=0)
     {
     cout << "Not a valid row, please try again (1-3): ";
     cin >> whichrow;
     }
    sum = Sum(row);
    cout << "How many will you take from row " << whichrow;
    cout << "? ";
    cin >> howmany;
    while(sum - howmany < 1 || row[whichrow] - howmany < 0 ||
          howmany < 1)
    {
    cout << "You tried to take too many or too few!\n";
    cout << "Pick again: ";
    cin >> howmany;
    }
    
    row[whichrow] = row[whichrow] - howmany;
    display(row);
    
    /* CHECK FOR PLAYER WIN */
    if(Sum(row) == 1)
    	{
       	cout << "YOU WIN!!!";
          return;
       }
    
    //Initialize the move CPU will make
    Move move(0, 0);
    
    //Select and make move
    initialize(row, move);
    //Move is chosen
    
    cout << "For my turn I will take " << move.to << " from row ";
    cout << move.from << "." << endl;
    row[move.from] = row[move.from] - move.to;
    display(row);
    
    //Test for game over, computer wins
    if(Sum(row) == 1)
    {
    	cout << "I win!!!  Nya Nya Nya!\n";
       return;
    }
    
    } /* this is the end of the loop where player and computer
         alternate turns.
      */
    
      //THIS CODE SHOULD NEVER BE REACHED
      return;
    }
    
    /* This function provides the "graphical" display of
       the remaining pieces...  it doesn't actually DO
       anything though.
    */
    
    static void display(int* rows)
     {
     rows++;
     cout << "|--------------------------------------------------------|\n\n";
     for(int i = 1; i < NUMROWS; i++)
      {
       if(i==1) cout << "        ";
       if(i==2) cout << "    ";
      for(int j = 1; j <= *rows; j++)
        cout << "   |";
      rows++;
      cout << "\n\n";
      }
      cout << "|--------------------------------------------------------|\n\n";
     }
    
    //This function returns the # of pieces left total
    static int Sum(int* row )
    {
    	int total = 0;
    	row++;
    	for(int i = 1; i < NUMROWS; i++)
    	 {
         total+=*row;
         row++;
    	 }
        return total;
    }
    
    /* Here is where the computer starts its search*/
    void initialize(int* array, Move& move)
    {
       Move& m = move;
    
    	//It's best move so far and the depth at which it starts
       int best = -1, depth = 1;
    
    /* COPY ARRAY*/
       int row[4];
       for(int i = 0; i < 4; i++)
       {
       	row[i] = *array;
          array++;
       }
       //Reset "array" to be row[1]
       array= array-3;
    
    
    /* BEGIN SEARCH
    	This for loop goes through each row and checks the board
       position at EVERY conceivable next move.  The search code
       is very similar here to how it appears in the recur function
       and probably could have been put into one function, but it's
       done now.
    */
    	for(int j = 1; j <= 3; j++)
       {
       	int thisrow = row[j];  //Placeholder type variable
       	for(int i = 1; i <= thisrow; i++)
          {
          	int value;
             row[j]--;  //Take one piece...
             value = recur(row, depth);   //...And see how it looks
             if(value > best)  //If it's better than anything so far...
             {
             	best = value;  //Then this is our move!!!!
                m.from = j;
                m.to = i;
             }
          }
          row[j] = *array;  //Reset the row
          array++;
       }
    }
    
    int recur(int* array, int depth)
    {
    
     int best = -1;
     int worst = 101;
    
    /* COPY ARRAY*/
       int row[4];
       for(int i = 0; i < 4; i++)
       {
       	row[i] = *array;
          array++;
       }
    
       if(Sum(row) == 0)
       {
       	//Hopefully, this code should be unreachable
          cout << "Illegal move\n";
       	return 50;
       }
    
    /* If we have reached the end of the game, if it's the human's
    	turn, computer win, if it's the computer's turn, human wins.
    */
       if(Sum(row) == 1)
       {
    	 if(depth%2 == 1)
         return 100;
        else return 0;
       }
    
    //Reset "array" to point to row[1]
       array= array-3;
    
    /* If the search has reached the specified depth, look at
    	the board and return its value.
    */
       if(depth == skill)
       {
    	   int val = evaluate(row);
    
          if(depth%2 == 1)
          	return 100-val;
          else
          	return val;
    	}
    
       /**************RECURSIVE SEARCH SECTION********/
    
       /* BEGIN SEARCH*/
    	for(int j = 1; j <= 3; j++)
       {
       	int thisrow = row[j];
       	for(int i = 1; i <= thisrow; i++)
          {
          	int value;
             row[j]--;
    
             //IF THE CPU tries to take one too many, exit loop
             if(Sum(row)== 0) break;
    
             //Search again with new board at one more level
             value = recur(row, depth+1);
    
             if(value > best)
             {
             	best = value;
             }
             if(value < worst)
             {
             	worst = value;
             }
    
    
          }
          row[j] = *array;
          array++;
       }
    
       /**********************************************/
    
    /* If this depth happens to reflect the computer's turn,
    	return the worst since he would be in the worst possible
       position due to the person's turn.  If it's the person's turn
       then the computer will be in the best possible situation
       since it would have just made a move.
    */
       if(depth%2 == 1)
       {
       	return worst;
       }
       else
       {
         	return best;
       }
    
    }
    
    /* This method evaluates the actual board position when
    	the specified search depth is reached.  The values reflect
       how "guaranteed a win" any position is based on perfect
       playing.  These only reflect end-game positions which is
       where the computer shines.  The only reason for including
       this method at all is to allow for a smaller search space
       to speed up the computer's turns.
    */
    int evaluate(int* array)
    {
    	int total, high=0, low=10;
    
    /* COPY ARRAY*/
       int row[4];
       for(int i = 0; i < 4; i++)
       {
       	row[i] = *array;
          array++;
       }
    
       total = Sum(row);
    
       for(int i = 1; i <=3; i++)
       {
       	if(row[i] < low)
          	low = row[i];
          if(row[i] > high)
          	high = row[i];
       }
    
    	if(total == 1)
       	return 100;
    
    	if(high==1 && low ==1)
       	return 2;
    
        if(total == 2)
       	return (99);
    
       if(high==2)
       {
        	if(total==4)
          	return total;
          else return(100-total);
       }
    
       if(low==0)
       {
       	if(total==(2*high))
          	return total;
          else return 100-(total*2);
       }
    
       if(high==3)
       {
       	if (total==6) return 10;
          else return(100-total);
       }
    
    
       return 50;
    
    }

  2. #2
    Ngày gia nhập
    03 2008
    Bài viết
    25

    Bạn coi kĩ hàm initialize, thuật toán deapth search(tìm kiếm theo chiều sâu) nó nằm ở trong này đó. Chúc bạn mò ra .

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    25

    Cơ bản sẽ có 3 row (1,2,3) tương ứng số * trên 1 row là 3,5,7. Trong hàm initialize bạn sẽ thấy nó duyệt lần lượt từng row, với mỗi row tương ứng nó sẽ duyệt và loại bỏ dần từng * của row đó để tìm ra cái value tối ưu nhất. Sau đó nó sẽ xuống row tiếp theo rồi lại duyệt tất cả các row để loại bỏ * và tìm ra phương án loại bỏ nào là tối ưu nhất rồi trả giá trị ra value. Còn giá trị value như thế nào là tối ưu và tại sao như thế lại là tối ưu thì bạn chưa cần quan tâm. Cái nguyên lí duyệt theo chiều sâu (Depth Search) ở đây là duyệt theo 1 nhánh (row) và đi theo nhánh đó xuống mức sâu nhất có thể (duyệt tất cả các phần tử * của nhánh đó) rồi mới thực hiện tiếp trên nhánh tiếp theo. Hi vọng giúp được bạn.
    P/s: trò này cũng dzui dzui hen ^^, tớ chơi thử thì mới thắng được ở mức 0 à, còn mấy mức kia chưa khi nào tớ thắng ~"~. Đang nghiên cứu thuật giải của nó để xem tìm ra cách thắng nó zzz. Cảm ơn bạn về bài này, phần "trí tuệ nhân tạo" của bài này cũng thú vị thật.

Các đề tài tương tự

  1. Project từ điển Anh-Việt bằng C# + giải thích code
    Gửi bởi pololi trong diễn đàn Dự án & Source code C#, ASP.NET
    Trả lời: 27
    Bài viết cuối: 16-03-2015, 10:28 AM
  2. project và source code đề tài Datamining
    Gửi bởi thansautk trong diễn đàn Dự án & Source code VC++
    Trả lời: 6
    Bài viết cuối: 14-01-2014, 10:05 AM
  3. ADO.NET Project C# muốn dùng soucre code C++ 11
    Gửi bởi cuchuoi137 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 11-11-2013, 08:52 AM
  4. Cần người code thuê project C++ trên nền MFC
    Gửi bởi thuha_1201 trong diễn đàn Việc làm IT(tự do)
    Trả lời: 0
    Bài viết cuối: 11-12-2012, 07:20 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn