برنامج تك-تاك-تو في ++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 emptyPosition::Position()
{for( int j=0; j<9; j++ )
mcell[j] = hcell[j] = empty;
}
// IsWin()// see if the current position is a win for playerboolean Position::IsWin()
{ cell *ptr; // pointer to cellsif( player==human ) // point to appropriate array
ptr = hcell;
elseptr = mcell;
// check for a 3-in-a-rowif( (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);
elsereturn(false);
}
// IsLegal()// find if move is legal in this positionboolean Position::IsLegal(int move) { if( move>=0 && move<=8 &&mcell[move]==empty && hcell[move]==empty )
return(true);
elsereturn(false);
}
// MakeMove()// make move in current position with current playervoid 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 machinevoid Position::SetPlayer(whoplays p) {player = p;
}
// InitDisplay()// Draws lines, numbers squaresvoid Position::InitDisplay() {const unsigned char block = '\xB2'; // gray block
void Insert(unsigned char, int, int); // prototype
int row, col; clrscr(); // clear screenfor(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 boardvoid 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, rowvoid Insert(unsigned char ch, int col, int row)
{ // start 5 lines down, 50 cols over gotoxy(col+50+1, row+5+1); // insert the characterputch(ch);
}
// Evaluate()// set score to chance of win, return the best moveint 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 positionint 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 levelfor(int move=0; move<9; move++) // for each of 9 moves
{ // 'player' can makeif( IsLegal(move) ) // if no one played there yet
{if( legalmoves==0 ) // set returnmove to first
returnmove = move; // legal move ++legalmoves; // count a legal moveposptr = new Position; // make new position
// for this move*posptr = *this; // transfer this pos to posptr
posptr->MakeMove(move); // make the moveif (deep < 3) // display, if in first two
posptr->Display(); // levels of recursionif( 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/machinewhoplays newp = (player==machine) ? human : machine;
posptr->SetPlayer(newp); // in new position // recursive call posptr->Evaluate(score2); // to new positionif(score2==winscore) // if wining score,
waswin = true; // remember there was a win
elsewasother = true; // remember non-win
totalscore += score2; // add new score to totalif( 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 movesif( legalmoves==0 ) // if there are no legal moves
{ score = drawscore; // it must be a draw --deep; // go up one recursion levelreturn(99); // return nonsense move
}
else // there were some legal moves
{ avgscore = totalscore / legalmoves; // find averageif( 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 levelreturn(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 positionint cursrow = 0; // cursor row for text
Position::InitDisplay(); // display the boardwhile(1) // cycle until game over
{ current.SetPlayer(human); // set player to human current.Display(); // display the positiongotoxy(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 movecurrent.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 movegotoxy(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 movegotoxy(1, ++cursrow);
cout << "I play at " << move; current.MakeMove(move); // make machine movecurrent.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 (صفر لنا) , وهكذا .
تعليقات
إرسال تعليق