برنامج تك-تاك-تو في ++C

c

برنامج تك-تاك-تو

هذه لعبة من ألعاب التسلية الكلاسيكية , نختتم بها منهجنا في تدريس لغة السي ++ ونضعك به علي مدخل الذكاء الاصطناعي حيث يقوم البرنامج بتحليل الموقف واختيار أفض حركة . وبلغة البرمجة الكائنية , فهو تطبيق أخر لفكرة المعاودة فكل كائن يحتوي علي دالة تخلق كائنا جديدا من نفس فئته .

وتلعب هذه اللعبة الشهيرة بالورقة والقلم , حيث يتبادل الخصمان وضع حرفي O, X علي تسعة مربعات كما هو مبين في الشكل والفائز هو من يستطيع ترتيب الحرف الخص به في خط مستقيم .

شكل دور تقليدي للعبة

ويدور الدور بين اللاعب والجهاز بطريقة تفاعلية بواسطة رسائل تظهر علي الشاشة تحدد الخطوة التالية لك خصم , كما هو مبين في الشكل

شكل موقف من مواقف اللعبة

ولعلك تظن أن هذه اللعبة أبسط من أن تقدم كبرنامج نحلله , ولكن البرنامج يحوي في الواقع الأفكار الرئيسية للبرامج الأكثر تطورا كبرامج لعبة الشطرنج مثلا , فالبرنامج يفكر مسبقا في كافة الاحتمالات النابعة عن موقف معين وأيها أكثر احتمالا لتحقيق النصر في النهاية .

وإليك صياغة البرنامج

Tictac.cpp

// tictac.cpp


// tic-tac-toe game


// UCS Laboratories


 


#include <iostream.h>   // for cout, etc


#include <conio.h>      // for gotoxy()


#include <process.h>    // for exit()


 


enum whoplays { human, machine };


enum cell { empty, full };


enum boolean { false, true };


 


int deep = 0;           // recursion depth


 


class Position          // represents one board position


   {


   private:


      cell mcell[9];    // cells marked with machine moves


      cell hcell[9];    // cells marked with human moves


      whoplays player;  // human or machine to play next


   public:


      Position();                   // constructor


      boolean IsWin();              // win in this position?


      boolean IsLegal(int);         // move is legal?


      void MakeMove(int);           // make move


      void SetPlayer(whoplays);     // swap player and machine


      static void InitDisplay();    // displays lines & numbers


      void Display();               // display board position


      int Evaluate(int&);           // score this position


   };


 


// Position()


// constructor: reset all cells to empty


Position::Position()


   {


   for( int j=0; j<9; j++ )


      mcell[j] = hcell[j] = empty;


   }


 


// IsWin()


// see if the current position is a win for player


boolean Position::IsWin()


   {


   cell *ptr;          // pointer to cells


   if( player==human ) // point to appropriate array


      ptr = hcell;


   else


      ptr = mcell;


               // check for a 3-in-a-row


   if( (ptr[0] && ptr[1] && ptr[2]) ||  // horizontal


       (ptr[3] && ptr[4] && ptr[5]) ||


       (ptr[6] && ptr[7] && ptr[8]) ||


       (ptr[0] && ptr[3] && ptr[6]) ||  // vertical


       (ptr[1] && ptr[4] && ptr[7]) ||


       (ptr[2] && ptr[5] && ptr[8]) ||


       (ptr[0] && ptr[4] && ptr[8]) ||  // diagonal


       (ptr[2] && ptr[4] && ptr[6]) )


      return(true);


   else


      return(false);


   }


 


// IsLegal()


// find if move is legal in this position


boolean Position::IsLegal(int move)


   {


   if( move>=0 && move<=8 &&


          mcell[move]==empty && hcell[move]==empty )


      return(true);


   else


      return(false);


   }


 


// MakeMove()


// make move in current position with current player


void Position::MakeMove(int move)


   {


   if( player==human )     // player is human


      hcell[move] = full;


   else                    // player is machine


      mcell[move] = full;


   }


 


// SetPlayer()


// set player to human or machine


void Position::SetPlayer(whoplays p)


   {


   player = p;


   }


 


// InitDisplay()


// Draws lines, numbers squares


void Position::InitDisplay()


   {


   const unsigned char block = '\xB2';       // gray block


 


   void Insert(unsigned char, int, int);     // prototype


   int row, col;


 


   clrscr();                            // clear screen


   for(row=0; row<11; row++)            // vertical lines


      {


      Insert( block,  5, row);


      Insert( block, 11, row);


      }


   for(col=0; col<17; col++)            // horizontal lines


      {


      Insert( block, col, 3);


      Insert( block, col, 7);


      }


   for(int j=0; j<9; j++)               // number squares


      Insert( (char)(j+'0'), (j%3)*6+4, (j/3)*4 );


   }  // end InitDisplay()


 


// Display()


// displays board


void Position::Display()


   {


   void Insert(unsigned char, int, int);     // prototype


   int row, col;


 


   for(int j=0; j<9; j++)               // for each square


      {


      if( hcell[j] )                    // human move


     Insert('X', (j%3)*6+2, (j/3)*4+1);


      else if( mcell[j] )               // machine move


     Insert('O', (j%3)*6+2, (j/3)*4+1);


      else                              // no move


     Insert(' ', (j%3)*6+2, (j/3)*4+1);


      }


//   gotoxy(1, 23);                       // restore corsor pos


   }  // end Display()


 


// Insert()


// inserts character ch at col, row


void Insert(unsigned char ch, int col, int row)


   {


   // start 5 lines down, 50 cols over


   gotoxy(col+50+1, row+5+1);       // insert the character


   putch(ch);


   }


 


// Evaluate()


// set score to chance of win, return the best move


int Position::Evaluate( int& score )


   {


   int const winscore = 100;       // score for a win (lose=0)


   int const drawscore = 50;       // score for a draw


   int returnmove;                 // move to be returned


   Position *posptr;               // pointer to new position


   int legalmoves = 0;             // count legal moves


   int totalscore = 0;             // cumulative score


   int highscore = 0;              // highest score to date


   int avgscore;                   // average score


   int score2;                     // score from recursive call


   boolean waswin = false;         // true if at least one win


   boolean wasother = false;       // if at least one non-win


 


   ++deep;                         // down one recursion level


   for(int move=0; move<9; move++) // for each of 9 moves


      {                            // 'player' can make


      if( IsLegal(move) )          // if no one played there yet


     {


     if( legalmoves==0 )       // set returnmove to first


        returnmove = move;     //   legal move


     ++legalmoves;             // count a legal move


     posptr = new Position;    // make new position


                   //    for this move


         *posptr = *this;          // transfer this pos to posptr


     posptr->MakeMove(move);   // make the move


     if (deep < 3)             // display, if in first two


        posptr->Display();     // levels of recursion


     if( posptr->IsWin() )      // check if it's a win


        {


        waswin = true;          // there was a win


        highscore = winscore;   // win is highest score


        totalscore += winscore; // update total


        returnmove = move;      // return this move


        }


     else                         // no win, so check deeper


        {


                      // swap human/machine


        whoplays newp = (player==machine) ? human : machine;


        posptr->SetPlayer(newp);  // in new position


 


                      // recursive call


        posptr->Evaluate(score2); // to new position


 


        if(score2==winscore)      // if wining score,


           waswin = true;         // remember there was a win


        else


           wasother = true;       // remember non-win


        totalscore += score2;     // add new score to total


        if( score2 > highscore )  // remember the move that


           {                      // produced the


           highscore = score2;    // highest score, and


           returnmove = move;     // the score


           }


        }  // end else (no win)


     delete posptr;               // delete the position


     }  // end if IsLegal


      }  // end for


                // summarize results of all moves


   if( legalmoves==0 )      // if there are no legal moves


      {


      score = drawscore;    // it must be a draw


      --deep;               // go up one recursion level


      return(99);           // return nonsense move


      }


   else                // there were some legal moves


      {


      avgscore = totalscore / legalmoves;   // find average


      if( waswin && wasother )           // if wins and non-wins,


     score = winscore - (winscore-avgscore)/5;  // favor wins


      else


     score = avgscore;  // otherwise, use the average score


      score = 100 - score;  // invert: bad for them, good for us


      --deep;               // go up one recursion level


      return(returnmove);   // return best move


      }  // end else (legal moves)


   }  // end Evaluate()


 


// main()


// get human move, get machine move, etc.


void main(void)


//UCS Laboratories


   {


   int move;                         // store moves


   int sc;                           // for Evaluate()


   int movecount = 0;                // number of move-pairs


   Position current;                 // create current position


   int cursrow = 0;                  // cursor row for text


 


   Position::InitDisplay();          // display the board


   while(1)                          // cycle until game over


      {


      current.SetPlayer(human);      // set player to human


      current.Display();             // display the position


      gotoxy(1, ++cursrow);


      cout << "Make your move (0 to 8): ";  // get human move


      cin >> move;


      if( ! current.IsLegal(move) )


     {


     gotoxy(1, ++cursrow);


     cout << "Illegal move.";


     continue;                   // return to top of loop


     }


      current.MakeMove(move);        // make human move


      current.Display();


      if( current.IsWin() )          // check for human win


     {


     gotoxy(1, ++cursrow);


     cout << "You win!";


     exit(0);


     }


      if( ++movecount==5 )           // if human move was


     {                           // the last possible move


     gotoxy(1, ++cursrow);


     cout << "It's a draw";


     exit(0);


     }                           // now machine can play


      current.SetPlayer(machine);    // set player to machine


      move = current.Evaluate(sc);   // get machine move


      gotoxy(1, ++cursrow);


      cout << "I play at " << move;


      current.MakeMove(move);        // make machine move


      current.Display();


      if( current.IsWin() )          // check for machine win


     {


     gotoxy(1, ++cursrow);


     cout << "I win!";


     exit(0);


     }


      }  // end while


   }  // end main()






يستخدم البرنامج فئة Position تعبر عن وضع ما علي الواقعة , أي تشكيلة من حرفي O, X علي شبكة من تسعة مربعات . وتمثل التشكيلة علي مصفوفة أحادية من تسعة عناصر , كل عنصر من النوع enum cell وله حالتان , فارغ empty ومشغول full . وكان بالإمكان استخدام مصفوفة واحدة للكائن يسجل فيها المواضع التي اختارها اللاعب (حروف X) والمواضع التي اختارها جهاز (حروف O ) ولكن اتضح أنه يكون أبسط بكثير لو أستخدمت مصفوفتان واحدة للاعب hcell[9] (اختصار human cell أي اللاعب البشري ) والثانية للألة mcell[9] (اختصار machine cell ) , كما يضم كائن هذه الفئة متغيرا من النوع enum whoplays يشير للاعب الذي عليه الدور التالي , وله حالتان human, machie .



أما الدوال المنتمية للفئة فهي :



البادئة : لاستهلال كافة المواضع (المصفوفتان hcell, mcell بالحالة "فارغ empty" . الدالة IsWin() تعطي دلالة إن كان الوضع الحالي ينبئ عن حالة فوز .



الدالة ISLegal(move) تحدد إذا كانت الحركة صحيحة أم خاطئة , كان تكون في موضع أكبر من 8 أو أقل من صفر (سالب) , أو في موقع مشغول بالفعل .



الدالة MakeMove() تحول حالة خلية ما في أي من المصفوفتين من فارغ لمشغول إذا كانت الحركة صحيحة .



الدالة SetPlayer تعطي دلالة عليه الدور في اللعب .



الدالة InitDisplay() تستدعي هذه الدالة في بداية البرنامج لكي ترسم الشبكة ذات المربعات التسعة , وترقمها .



الدالة Insert() تضع محرفا في موضع ما من الشبكة علي شاشة الجهاز , وتستخدمها دالتي الإظهار .



الدالة Evaluate وتمثل المنطق الذي يحلل به البرنامج مواقف اللعبة , ليختار الحركة الخاصة به , وهو ما سنعرض له بعد قليل .



تشغيل البرنامج



تبدأ الدالة الأصلية main() البرنامج بإنشاء كائن من فئة Position باسم current , ثم تستدعي الدالة InitDisplay في الكائن المنشأ لرسم رقعة اللعب بعد ذلك تدخل في دوارة يسير فيها اللعب بالخطوات التالية :



- تحديد الخصم الذي يبتدئ اللعب علي أنه اللاعب باستخدام الدالة SetPlayer(human); .



- سؤال اللاعب عن حركته



- اختبار صحة الحركة بالدالة IsLegal(move) , وفي حالة صحتها , تسجيل ذلك في مصفوفة hcell من الكائن بواسطة الدالة MakeMove(move)



- إظهار الموقف واختبار حالتي الفور أو التعادل



- تحويل الخصم إلي الجهاز



- استدعاء الدالة Evaluate() لتحديد خطوة الجهاز وتسجيل ذلك وإظهاره



- اختبار حالة الفوز , وإلا تكررت الدوارة .



منطق البرنامج



نأتي الأن للعقل للبرنامج , فالدالة Evaluate() تحلل موقفا معينا (تشكيلة معينة علي الرقعة ) لتقدر نسبة احتمال أن يؤدي للفوز . وفي سبيلها لتقدير ذلك تقوم بإنشاء كائنات بقدر ما يحتمل أن يتفرع عن هذا الموقف من ردود وذلك عن طريق المعاودة بمعني أن الدالة تستدعي نفسها في كل مرة يحتمل أن يؤدي الموقف إلي رد ما . وإنشاء الكائن عن طريق دوال Evaluate() المتكررة يكون باستخدام الكلمة الحاكمة new والتي تحجز أماكن بالذاكرة للكائنات المنشأ ] تلاحظ أننا نتعامل مع هذه الكائنات بعناوينها المبينة في المؤشر posptr دون حاجة لإعطائها أسماء ما [ .



فحين يفتتح اللاعب المباراة باختبار معين , يكون أمام الجهاز ثمانية احتمالات , يتفرع عنها سبعة احتمالات لرد اللاعب فخمسة ردود للجهاز , وهكذا حتي الاختيار الأخير , بمعني أن الجهاز يكون أمامه 8x 7 x 6 x5 x 4 x 3 x 2 x 1 ] مضروب 8= 40320[ , من الاختيارات بعد حركة اللاعب الأولي , وهو ما يفسر بطء رد الجهاز علي هذه الحركة وزيادة زمن الرد مع تقدم اللعب وقلة الخيارات المتاحة . ولو جعلنا الجهاز يفتتح اللعب , لوصل عدد الاحتمالات , فبينا البعض منها . وتسجل الدالة رقما لكل احتمال , بحسب النتيجة التي يؤدي إليها يسمي score فحالة الفوز تعطي الرقم 100 والخسارة صفر والتعادل 50 ويمكن بهذا الرقم مقارنة الأوضاع المختلفة .



ويتعمق الدالة إلي شجرة الإحتمالات , يحدث شئ من التالي : حالة فوز أحد الخصمين , فتنتهي هذا الفرع من شجرة الاحتمالات (ولذا فعدد الاحتمالات أقل في الواقع مما ذكرناه أنفا , ولكن بقدر قليل ).



وتوضح الدالة Evaluate() في دوارة ذات تسعة دورات تقابل الأوضاع التسعة . وهي تفحص أولا قانونية النقلة , فإن تحقق ذلك , تخلق وضعا جديدا ثم تقدر نتيجته , فإن كان فوزا تضع 100 في المتغير highscore وتضيف 100 لمجموع النقاط الجاري كما أنها تذكر الوضع الذي حقق القيمة .



فإذا لم يكن الوضع فوزا , واصلت الدالة بحثها علي مستوي أعمق , فتستدعي الدالة Evaluate() الخاصة بالكائن الجديد الذي أنشأته , ويضاف تقدير الدالة الجديدة لمجموع النقاط , فإذا كان المجموع هو أكبر مجموع تم للأن , يوضع في المتغير highscore, وتتحدد النقلة علي أساس هذا الموضع الجديد .



تقدير الموضع



عندما ينتهي تقدير كافة المواضع المحتملة , تنتهي دوارة الدالة Evaluate() ليبدأ تقدير الموضع المختار , ويمكنك تقريب ذلك بالقول بأنها تقسم مجموع النقاط علي عدد النقلات المتاحة للخصم , ثم تعكس النتيجة لتقدير المتوسط الذي يعبر عن احتمال الفوز . وعملية العكس مطلوبة لأن ما هو حسن للخصم سيئ لنا فلو أن احتمال فوز الخصم هو ثلاثة نقلات من أربعة متاحة , فإن مجموع نقاطه سيكون قريبا من المائة , ولكنه قريب من الصفر بالنسبة لنا , حيث نكون في حالة قريبة من احتمال الخسارة .



والواقع فإن تجميع نتائج عدة خطوات في عدد موحد من النقاط يعتبر أعقد قليلا من مجرد حساب المتوسط فلو أن خصمنا لدية فرصة واحدة للفوز من أربعة فرص , فإن حساب المتوسط يكون 25 , ولكن حساب المتوسط يفترض أن خصمنا يختار النقلة عشوائيا , وهو أمر ليس متحققا بالمرة في الممارسة العملية , وإن الأخذ في الاعتبار أن خصمنا سوف يختار هذه النقلة بالذات , يجعل احتمال مكسبه يقترب من المائة , وعلي ذلك , فالمفروض أن نسجل لهذه النقلة من وجهة نظرنا قيمة قريبة 0 .



وتؤدي بنا هذه الاعتبارات , سياسة التجربة والخطأ , إلي الخوارزم التالي لتقدير النقاط : إذا كان لدي خصمنا بعض حالات فوز وحالات أخري (تعادل , خسارة , أو نقاط أخري ) فإننا نبدأ من 100 (قيمة الثابت winscore) ثم نطرح منه 100 – متوسط النقاط مقسوما علي 5 ولذا ففي مثال حالة فوز وثلاثة حالات خسارة يكون الحساب كالتالي : 100 – (100-25)/5= 85 . ولحالة فوز وثلاثة تعادلات , يكون المتوسط 62 , وحساب النقاط 100-(100-62)/5=92 .



وفي حالة عدم مكسب أو عدم خسارة , فإن المتوسط يؤخذ بلا تعديل . فأربعة تعدلات تعطي 50 , خسارتان وتعادلان 25 (75 لنا) , أربعة تعادلات 100 (صفر لنا) , وهكذا .

التسميات: