دليل خوارزمية المينيماكس: كيف تبني ذكاءً اصطناعياً لا يُقهر؟

لطالما راودني الفضول مؤخرًا حول كيفية برمجة الحاسوب ليصبح لا يُقهر في لعبة “إكس أو” (Tic-Tac-Toe). ظننت أن الإجابة ستكون سهلة المنال، لكن بعد بحث مكثف بين المقالات ومقاطع الفيديو وسلسلة من التأملات البرمجية، وجدت نفسي في حيرة أكبر. ومع ذلك، جاءت لحظة “الاستنارة” عندما خصصت الوقت الكافي لفهم آلية عمل خوارزمية المينيماكس (Minimax Algorithm). إذا كنت تسير في نفس الدرب، فدعني أصحبك في رحلة خطوة بخطوة لبناء ذكاء اصطناعي (AI) لا يُقهر.

فهم أساسيات خوارزمية المينيماكس

خوارزمية المينيماكس (Minimax) هي برنامج تكراري (recursive) مصمم لإيجاد أفضل استراتيجية لعب تقلل من احتمالية الخسارة إلى أدنى حد، بينما تزيد من فرص الفوز إلى أقصى حد ممكن. يمكن تمثيل المينيماكس بيانيًا كاستكشاف لعقد شجرة اللعبة (game tree) لاكتشاف أفضل حركة يمكن القيام بها. في هذه الحالة، يمثل جذر الشجرة (root) الحالة الراهنة للعبة، وهي النقطة التي يتم فيها استدعاء خوارزمية المينيماكس.

الشكل 1: شجرة اللعبة للعبة “إكس أو” في حالة اقتراب من النهاية.

ينصب تركيزنا في هذا الدليل على استخدام المينيماكس لإنشاء ذكاء اصطناعي لا يُقهر للعبة “إكس أو”. ومع ذلك، يمكن تطبيقها أيضًا على ألعاب أكثر تعقيدًا مثل الشطرنج، وفي اتخاذ القرارات العامة لحل حالات عدم اليقين. في معظم الحالات، يُطلق على اللاعب الذي يستدعي خوارزمية المينيماكس في البداية اسم اللاعب المُعظِّم (maximizing player). بعبارة أخرى، هو اللاعب الذي يسعى لتعظيم فرص الفوز. في المقابل، يُطلق على خصم اللاعب المُعظِّم اسم اللاعب المُقلِّل (minimizing player)، وهو اللاعب الذي يجب تقليل فرصه في الفوز.

باختصار، خوارزمية المينيماكس هي دالة تكرارية (recursive function) تُنشأ لمساعدة اللاعب (المُعظِّم) على تحديد استراتيجية اللعب التي تقلل من أقصى احتمالية للخسارة.

التعرف على عقدة الجذر في هذا الدليل

لجعل هذا الدليل دقيقًا وواضحًا، ستكون عقدة الجذر (root node) التي سنستخدمها (أي الحالة الحالية للعبة “إكس أو”) عبارة عن لوحة لعب قريبة من النهاية، كما هو موضح في الشكل 2 أدناه. سيمثل الرمز X علامة الذكاء الاصطناعي، بينما سيمثل الرمز O علامة اللاعب البشري.

الشكل 2: عقدة الجذر المستخدمة في هذا الدليل.

في المرحلة الحالية من لعبة “إكس أو” (كما هو مبين في الشكل 2 أعلاه)، حان دور اللاعب X للعب (أي دور الذكاء الاصطناعي). وبما أن هناك ثلاث خلايا فارغة على اللوحة، فهذا يعني أن اللاعب X لديه ثلاثة خيارات لعب محتملة: الخلية العلوية الوسطى، الخلية المركزية، أو الخلية السفلية اليمنى. ولكن ما هو الخيار الأفضل؟ وما هي الحركة التي ستساعد اللاعب X على تقليل أقصى احتمالية للخسارة؟

الشكل 3: خيارات اللعب الممكنة للاعب الذكاء الاصطناعي.

لاتخاذ القرار الأمثل، يحتاج الذكاء الاصطناعي إلى القيام بما يلي:

• تخزين الحالة الحالية (القيم) للوحة “إكس أو” في مصفوفة (array). (بالنسبة لأي خلية فارغة، سيتم تخزين فهرس الخلية (cell's index) كمحتواها الحالي).
• الحصول على قائمة مصفوفة (array list) تحتوي على فهارس الخلايا الفارغة فقط.
• التحقق والتأكيد مما إذا كان لاعب معين قد فاز باللعبة.
• استدعاء المينيماكس تكراريًا (recursively invoke minimax) على كل خلية فارغة من خلايا اللوحة.
• إرجاع نتيجة (score) لكل حركة محتملة لكل من اللاعب X واللاعب O.
• من بين جميع النتائج المرتجعة، اختيار الأفضل (الأعلى) الذي يضمن تقليل احتمالات فوز اللاعب البشري.

لذلك، في الخطوات التالية، سنقوم بتهيئة الذكاء الاصطناعي لإنجاز القائمة أعلاه. فلنبدأ بتخزين الحالة الحالية للوحة في مصفوفة.

تخزين الحالة الحالية للوحة في مصفوفة

خطوتنا التالية هي تخزين المحتوى الحالي لكل خلية من خلايا اللوحة في مصفوفة (array) على النحو التالي:

 const currentBoardState = [
  "X", 1, "O",
  "X", 4, "X",
  "O", "O", 8
 ];

ملاحظة: الحالة الحالية للوحة “إكس أو” لا تزال كما هو موضح في الشكل 2. القيم 1 و 4 و 8 في مصفوفة currentBoardState هي أرقام فهارس الخلايا الفارغة في اللوحة. بعبارة أخرى، بدلاً من استخدام سلاسل نصية فارغة (empty strings)، اخترنا تخزين المحتوى الحالي للخلايا الفارغة كفهارسها الخاصة. من المهم، قبل الانتقال إلى الخطوة التالية، أن نحدد بشكل صريح علامة من هي "X" ومن يملك "O".

 const aiMark = "X";
 const humanMark = "O";

العبارتان أعلاه تشيران إلى أن علامة الذكاء الاصطناعي هي X بينما علامة اللاعب البشري هي O.

إنشاء دالة للحصول على فهارس جميع الخلايا الفارغة

ستقوم الدالة التالية بتصفية مصفوفة currentBoardState، والتي سيتم تمريرها كمعامل (parameter's argument) للدالة. ثم ستعيد مصفوفة جديدة تحتوي على جميع عناصر مصفوفة currentBoardState التي ليست "X" ولا "O".

 function getAllEmptyCellsIndexes ( currBdSt ) {
  return currBdSt.filter( i => i != "X" && i != "O" );
 }

ملاحظة: تذكر أن مصفوفة currentBoardState التي أنشأناها في الخطوة 3 تحتوي فقط على القيم "X" و "O" وفهارس الخلايا الفارغة في اللوحة. لذلك، تقوم دالة getAllEmptyCellsIndexes() أعلاه بتصفية أي ظهور لفهرس في مصفوفة currentBoardState.

إنشاء دالة تحديد الفائز

الغرض الأساسي من دالة تحديد الفائز (winner determiner function) أدناه هو استقبال مصفوفة currentBoardState وعلامة لاعب محدد (إما علامة "X" أو علامة "O") كمعاملات لها. ثم تتحقق مما إذا كانت العلامة المستلمة تشكل مجموعة فائزة على لوحة “إكس أو”. إذا كان الأمر كذلك، يتم إرجاع القيمة المنطقية true؛ وإلا، يتم إرجاع false.

 function checkIfWinnerFound ( currBdSt, currMark ) {
  if (
  (currBdSt[0] === currMark && currBdSt[1] === currMark && currBdSt[2] === currMark) ||
  (currBdSt[3] === currMark && currBdSt[4] === currMark && currBdSt[5] === currMark) ||
  (currBdSt[6] === currMark && currBdSt[7] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[0] === currMark && currBdSt[3] === currMark && currBdSt[6] === currMark) ||
  (currBdSt[1] === currMark && currBdSt[4] === currMark && currBdSt[7] === currMark) ||
  (currBdSt[2] === currMark && currBdSt[5] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[0] === currMark && currBdSt[4] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[2] === currMark && currBdSt[4] === currMark && currBdSt[6] === currMark)
  ) {
  return true;
  } else {
  return false;
  }
 }

بناء خوارزمية المينيماكس

خوارزمية المينيماكس (Minimax algorithm) هي ببساطة دالة عادية تحتوي على تعليمات يتم تنفيذها بمجرد استدعاء الدالة. لذلك، فإن عملية إنشاء الخوارزمية هي نفسها عملية إنشاء أي دالة أخرى. فلنقم بإنشائها الآن:

 function minimax ( currBdSt, currMark ) {
  // مساحة لتعليمات المينيماكس
 }

هذا كل شيء! لقد أنشأنا دالة minimax، وإن كانت فارغة. خطوتنا التالية هي ملء الدالة بالتعليمات التي سيتم تنفيذها بمجرد استدعائها، وهو ما سنفعله أدناه.

ملاحظة: دالة minimax التي تم إنشاؤها أعلاه مصممة لقبول وسيطتين (two arguments). الأولى هي قائمة مصفوفة (array list) لمحتوى اللوحة الحالي، أي القيمة الحالية لمصفوفة currentBoardState. بينما الوسيطة الثانية هي علامة اللاعب الذي يقوم بتشغيل خوارزمية المينيماكس حاليًا، أي العلامة "X" أو العلامة "O".

الاستدعاء الأول لدالة المينيماكس

لتجنب أي التباس لاحقًا في هذا الدليل، دعنا نستدعي دالة minimax لأول مرة، مع تمرير مصفوفة currentBoardState و aiMark كوسيطات للدالة.

 const bestPlayInfo = minimax(currentBoardState, aiMark);

تخزين فهارس جميع الخلايا الفارغة

في هذه الخطوة، سنستدعي دالة getAllEmptyCellsIndexes التي أنشأناها في الخطوة 4، مع تمرير مصفوفة currentBoardState كوسيطة للدالة. ثم سنقوم بتخزين قائمة المصفوفة المرتجعة من الفهارس داخل متغير يسمى availCellsIndexes.

 const availCellsIndexes = getAllEmptyCellsIndexes(currBdSt);

التحقق من وجود حالة نهائية (Terminal State)

في هذه المرحلة، نحتاج إلى التحقق مما إذا كانت هناك حالة نهائية (terminal state) على لوحة “إكس أو” (أي حالة خسارة، أو حالة فوز، أو حالة تعادل). سننجز هذا التحقق عن طريق استدعاء دالة تحديد الفائز (winner determiner function) التي أنشأناها في الخطوة 5 لكل من اللاعبين.

• إذا وجدت الدالة حالة فوز للاعب البشري (المُقلِّل)، فستُرجع القيمة -1 (مما يعني أن اللاعب البشري قد فاز، وأن الذكاء الاصطناعي قد خسر).
• أما إذا وجدت حالة فوز للاعب الذكاء الاصطناعي (المُعظِّم)، فستُرجع القيمة +1 (مما يشير إلى أن الذكاء الاصطناعي قد فاز، وأن اللاعب البشري قد خسر).
• ولكن، إذا لم تتمكن دالة تحديد الفائز من العثور على أي خلية فارغة على اللوحة أو أي حالة فوز لأي من اللاعبين، فستُرجع القيمة 0 (صفر)، مما يعني أن اللعبة قد انتهت بالتعادل.

ملاحظة: النتائج (-1، +1، و 0) المشار إليها أعلاه هي قيم استدلالية (heuristic values)؛ مما يعني أننا سنحصل على نفس النتيجة إذا فضلنا استخدام -25، +25، و 0. دعنا الآن ننتقل لتنفيذ التحقق من الحالة النهائية باستخدام عبارة if على النحو التالي:

 if (checkIfWinnerFound(currBdSt, humanMark)) {
  return { score : -1 };
 } else if (checkIfWinnerFound(currBdSt, aiMark)) {
  return { score : 1 };
 } else if (availCellsIndexes.length === 0 ) {
  return { score : 0 };
 }

عند وجود حالة نهائية (خسارة، فوز، أو تعادل)، ستقوم دالة minimax النشطة بإرجاع نتيجة الحالة النهائية المناسبة (-1، +1، أو 0) وتنهي استدعاءها. إذا أنهت دالة minimax النشطة استدعاءها هنا، فستنتقل الخوارزمية إلى الخطوة 12. ومع ذلك، عندما لا تكون هناك حالة نهائية، ستقوم دالة minimax النشطة بتنفيذ العبارة التالية (الخطوة 10، أدناه).

الاستعداد لاختبار نتيجة لعب اللاعب الحالي على كل خلية فارغة

نظرًا لأن الخطوة 9 لم تعثر على حالة نهائية، يجب علينا ابتكار طريقة لاختبار ما سيحدث إذا لعب اللاعب الحالي (الذي سيقوم بالحركة التالية في اللعبة) على كل خلية فارغة. بعبارة أخرى، إذا لعب اللاعب الحالي على الخلية المتاحة الأولى، ولعب الخصم على الخلية الفارغة الثانية، فهل سيفوز اللاعب الحالي، يخسر، أم يتعادل في اللعبة؟ أم أنه لن يتم العثور على حالة نهائية بعد؟

بدلاً من ذلك، ماذا سيحدث إذا لعب اللاعب الحالي على الخلية المتاحة الثانية، ولعب الخصم على الخلية الفارغة الأولى؟ أو ربما، هل ستكون الخلية المتاحة الثالثة هي أفضل مكان للاعب الحالي للعب؟ هذا الاختبار التجريبي هو ما نحتاج إلى القيام به الآن. ولكن قبل أن نبدأ، نحتاج إلى مكان لتسجيل نتيجة كل اختبار، لذا دعنا نفعل ذلك أولاً بإنشاء مصفوفة (array) تسمى allTestPlayInfos.

 const allTestPlayInfos = [];

الآن بعد أن أمّنا مكانًا لتخزين نتيجة كل اختبار تجريبي، دعنا نبدأ التجارب بإنشاء عبارة حلقة تكرارية (for-loop statement) ستتكرر عبر كل خلية من الخلايا الفارغة بدءًا من الأولى.

 for ( let i = 0 ; i < availCellsIndexes.length; i++) {
  // مساحة لأكواد حلقة for
 }

في الخطوتين التاليتين، سنملأ حلقة for بالكود الذي يجب أن تشغله لكل خلية فارغة.

اختبار لعب علامة اللاعب الحالي على الخلية الفارغة التي تعالجها حلقة الـ For حاليًا

قبل القيام بأي شيء في هذه الخطوة، دعنا نراجع الحالة الحالية للوحتنا.

الشكل 4: الحالة الحالية للوحة “إكس أو”.

لاحظ أن اللوحة أعلاه لا تزال هي نفسها في الشكل 2، باستثناء أننا قمنا بتمييز الخلية التي تعالجها حلقة for حاليًا باللون الأحمر. بعد ذلك، سيكون من المفيد أن يكون لدينا مكان لتخزين نتيجة هذا الاختبار التجريبي النهائية، لذا دعنا ننشئ كائنًا (object) على النحو التالي:

 const currentTestPlayInfo = {};

أيضًا، قبل اختبار لعب علامة اللاعب الحالي على الخلية الحمراء، دعنا نحفظ رقم فهرس الخلية (cell's index number)؛ بحيث يكون من السهل إعادة تعيين معلومات الخلية بعد هذا الاختبار.

 currentTestPlayInfo.index = currBdSt[availCellsIndexes[i]];

دعنا الآن نضع علامة اللاعب الحالي على الخلية الحمراء (أي الخلية التي تعالجها حلقة for حاليًا).

 currBdSt[availCellsIndexes[i]] = currMark;

بناءً على طريقة لعب اللاعب الحالي، ستتغير حالة اللوحة لتعكس حركته الأخيرة.

الشكل 5: اللوحة الجديدة التي تعكس آخر حركة للاعب الحالي.

لذلك، بما أن حالة اللوحة قد تغيرت، نحتاج إلى تشغيل دالة minimax تكراريًا (recursively) على اللوحة الجديدة، مع تمرير حالة اللوحة الجديدة وعلامة اللاعب التالي.

 if (currMark === aiMark) {
  const result = minimax(currBdSt, humanMark);
  currentTestPlayInfo.score = result.score;
 } else {
  const result = minimax(currBdSt, aiMark);
  currentTestPlayInfo.score = result.score;
 }

ملاحظة: الاستدعاء التكراري لدالة minimax في هذه النقطة بالذات سيكون المرة الثانية التي نستدعي فيها الدالة. حدث الاستدعاء الأول في الخطوة 7. سيتسبب هذا الاستدعاء التكراري في تكرار الخطوات من 8 إلى 11. لنفترض أن هناك حالة نهائية في الخطوة 9. في هذه الحالة، سيتوقف استدعاء minimax الحالي عن العمل، ويخزن الكائن النهائي المرتجع (على سبيل المثال، {score: 1}) في المتغير result. بمجرد وجود حالة نهائية، ستكون الخطوة 12 هي الخطوة التالية. إذا لم تكن هناك حالة نهائية، فستبدأ حلقة for ثانية للوحة الجديدة في الخطوة 10. إذا تكررت الخطوة 10، يرجى استبدال لوحة الشكل 4 باللوحة الجديدة في الشكل 5. ومع ذلك، ستكون الخلية المميزة باللون الأحمر الآن هي الخلية التي تعالجها حلقة for حاليًا. لذا، يرجى عكس التغييرات وفقًا لذلك.

حفظ أحدث نتيجة للحالة النهائية

بعد أن يعيد استدعاء minimax الذي انتهى للتو قيمة حالته النهائية، ستقوم حلقة for النشطة بحفظ نتيجة المتغير result في الكائن currentTestPlayInfo على النحو التالي:

 currentTestPlayInfo.score = result.score;

ثم، بما أن النتيجة المرتجعة تنهي رسميًا الاختبار الحالي، فمن الأفضل إعادة تعيين اللوحة الحالية إلى حالتها قبل أن يقوم اللاعب الحالي بحركته.

 currBdSt[availCellsIndexes[i]] = currentTestPlayInfo.index;

أيضًا، نحتاج إلى حفظ نتيجة اختبار لعب اللاعب الحالي للاستخدام المستقبلي. لذا، دعنا نفعل ذلك عن طريق دفع الكائن currentTestPlayInfo إلى مصفوفة allTestPlayInfos على النحو التالي:

 allTestPlayInfos.push(currentTestPlayInfo);

ملاحظة: إذا وصلت إلى هذه الخطوة من الخطوة 17، يرجى متابعة هذا الدليل من الخطوة 18. وإلا، فكر في النقطة التالية. إذا انتهت حلقة for النشطة من التكرار عبر جميع الخلايا الفارغة في اللوحة الحالية، فستنتهي الحلقة عند هذه النقطة، وستكون الخطوة 14 هي التالية. وإلا، ستستمر الحلقة في معالجة الخلية المتاحة التالية (الخطوة 13).

تشغيل حلقة الـ For النشطة على الخلية الفارغة التالية

تذكر أن حلقة for النشطة حاليًا (التي بدأت في الخطوة 10) قد انتهت للتو من عملها للخلايا الفارغة السابقة. لذلك، ستستمر الحلقة في اختبار لعب علامة اللاعب الحالي على الخلية الفارغة التالية. بعبارة أخرى، ستقوم دالة minimax الجارية حاليًا بتكرار الخطوتين 11 و 12. ولكن، بشكل أساسي، لاحظ ما يلي:

• الخلية الحمراء المميزة في الشكل 4 ستتغير إلى الخلية التي تعالجها حلقة for حاليًا.
• يرجى الانتباه إلى أن الشكل 5 سيتغير أيضًا. بعبارة أخرى، ستكون حركة اللاعب الحالي الآن على الخلية التي تعالجها حلقة for حاليًا.
• بعد أن تنهي حلقة for النشطة عملها، ستحتوي مصفوفة allTestPlayInfos على كائنات محددة لكل خلية فارغة قامت حلقة for بمعالجتها.
• سيحتوي كل كائن من الكائنات في مصفوفة allTestPlayInfos على خاصية index وخاصية score (على سبيل المثال: {index: 8, score: -1}).

إذا وصلت إلى هذه الخطوة من الخطوة 20، فعند إكمال الخطوة 12، يرجى متابعة هذا الدليل من الخطوة 18.

التخطيط للحصول على الكائن ذي أفضل نتيجة اختبار لعب للاعب الحالي

مباشرة بعد أن تنهي حلقة for عملها في التكرار عبر جميع الخلايا الفارغة في اللوحة الحالية، ستقوم دالة minimax بما يلي:

• إنشاء مساحة لتخزين الرقم المرجعي الذي سيساعد لاحقًا في الحصول على أفضل كائن اختبار لعب.
• الحصول على الرقم المرجعي لأفضل اختبار لعب للاعب الحالي.
• استخدام الرقم المرجعي المكتسب للحصول على الكائن ذي أفضل اختبار لعب للاعب الحالي.

دون مزيد من اللغط، دعنا ننفذ هذه الخطة في الخطوات القليلة التالية.

إنشاء مخزن لمرجع أفضل اختبار لعب

المتغير أدناه هو المكان الذي سنخزن فيه لاحقًا مرجع أفضل كائن اختبار لعب. (لاحظ أن القيمة null تشير إلى أننا تركنا المتغير فارغًا عمدًا).

 let bestTestPlay = null ;

الحصول على مرجع أفضل اختبار لعب للاعب الحالي

الآن بعد أن أصبح هناك مخزن bestTestPlay، يمكن لدالة minimax النشطة المضي قدمًا في الحصول على مرجع أفضل اختبار لعب للاعب الحالي على النحو التالي:

 if (currMark === aiMark) {
  let bestScore = - Infinity ;
  for ( let i = 0 ; i < allTestPlayInfos.length; i++) {
  if (allTestPlayInfos[i].score > bestScore) {
  bestScore = allTestPlayInfos[i].score;
  bestTestPlay = i;
  }
  }
 } else {
  let bestScore = Infinity ;
  for ( let i = 0 ; i < allTestPlayInfos.length; i++) {
  if (allTestPlayInfos[i].score < bestScore) {
  bestScore = allTestPlayInfos[i].score;
  bestTestPlay = i;
  }
  }
 }

الكود أعلاه يعني ما يلي:

• إذا كانت العلامة الحالية تساوي علامة لاعب الذكاء الاصطناعي (aiMark):
  • أنشئ متغيرًا bestScore بقيمة -Infinity. (لاحظ أن هذه القيمة هي مجرد قيمة وهمية يجب أن تكون أقل من جميع النتائج في مصفوفة allTestPlayInfos. لذلك، فإن استخدام -700 سيؤدي نفس الغرض).
  • ثم، لكل كائن اختبار لعب في مصفوفة allTestPlayInfos، تحقق مما إذا كان الاختبار الذي تعالجه الحلقة حاليًا لديه نتيجة أعلى من bestScore الحالي. إذا كان الأمر كذلك، سجل تفاصيل هذا الاختبار في كل من المتغير bestScore والمتغير bestTestPlay.
• وإلا، إذا كانت العلامة الحالية هي علامة اللاعب البشري (humanMark):
  • أنشئ متغيرًا bestScore بقيمة +Infinity. (مرة أخرى، لاحظ أننا سنحصل على نفس النتيجة إذا فضلنا استخدام +300. إنها مجرد قيمة وهمية يجب أن تكون أكبر من جميع النتائج في مصفوفة allTestPlayInfos).
  • ثم، لكل كائن اختبار لعب في مصفوفة allTestPlayInfos، تحقق مما إذا كان الاختبار الذي تعالجه الحلقة حاليًا لديه نتيجة أقل من bestScore الحالي. إذا كان الأمر كذلك، سجل تفاصيل هذا الاختبار في كل من المتغير bestScore والمتغير bestTestPlay.

الحصول على الكائن ذي أفضل نتيجة اختبار لعب للاعب الحالي

أخيرًا، يمكن لاستدعاء minimax الجاري حاليًا إنهاء عمله بإرجاع الكائن الذي يحتوي على أفضل اختبار لعب للاعب الحالي على النحو التالي:

 return allTestPlayInfos[bestTestPlay];

لاحظ أن minimax سيخزن الكائن المرتجع داخل المتغير result الخاص بحلقة for الأولى التي بدأت في الخطوة 11. ثم سيكرر الخطوة 12. يرجى إعادة زيارة الخطوة 12 فقط. ثم تابع هذا الدليل أدناه.

مراجعة شاملة

تعد هذه المرحلة وقتًا ممتازًا لمراجعة ما قمنا به حتى الآن بصريًا.

• ملاحظة: إذا كانت هذه هي المرة الأولى التي تصل فيها إلى هذه الخطوة، يرجى استخدام الرسم البياني في الخطوة 19.
• هل هذه هي المرة الثانية لك في هذه الخطوة؟ إذا كان الأمر كذلك، فالرسم البياني في الخطوة 21 هو لك.
• هل أنت هنا للمرة الثالثة؟ أحسنت! تحقق من الرسم البياني في الخطوة 23.

تتبع خطواتنا باستخدام رسم بياني

يوضح الرسم البياني أدناه أول اختبار لعب بين الذكاء الاصطناعي واللاعب البشري للاستدعاء الأول لحلقة for الذي بدأه لاعب الذكاء الاصطناعي.

الشكل 6: أول اختبار لعب يتنبأ بحالة خسارة للذكاء الاصطناعي (المُعظِّم).

حلقة الـ For الأولى تتقدم لمعالجة الخلية الفارغة التالية

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

تتبع خطواتنا باستخدام رسم بياني (الجزء الثاني)

يوضح الرسم البياني أدناه ثاني اختبار لعب بين الذكاء الاصطناعي واللاعب البشري للاستدعاء الأول لحلقة for الذي بدأه لاعب الذكاء الاصطناعي.

الشكل 7: ثاني اختبار لعب يتنبأ بحالة فوز للذكاء الاصطناعي (المُعظِّم).

حلقة الـ For الأولى تتقدم لمعالجة الخلية الفارغة التالية (الجزء الثاني)

الآن بعد أن أكد الذكاء الاصطناعي أن اللعب على الخلية الفارغة الثانية سيؤدي إلى حالة فوز، فإنه يتحقق كذلك من نتيجة اللعب على الخلية الفارغة الثالثة بتكرار الخطوة 13.

تتبع خطواتنا باستخدام رسم بياني (الجزء الثالث)

يوضح الرسم البياني أدناه ثالث اختبار لعب بين الذكاء الاصطناعي واللاعب البشري للاستدعاء الأول لحلقة for الذي بدأه لاعب الذكاء الاصطناعي.

الشكل 8: ثالث اختبار لعب يتنبأ بحالة خسارة للذكاء الاصطناعي (المُعظِّم).

الحصول على الكائن ذي أفضل نتيجة اختبار لعب للاعب الذكاء الاصطناعي

في هذه المرحلة (بعد الاختبار التجريبي الثالث)، تكون حلقة for الأولى قد عالجت جميع الخلايا الفارغة الثلاث للوحة الأولى (التي تم تمريرها إلى minimax في الخطوة 7). لذلك، ستمضي دالة minimax قدمًا للحصول على الكائن الذي يحتوي على أفضل اختبار لعب للاعب الذكاء الاصطناعي، وذلك بتكرار الخطوات من 15 إلى 17. ومع ذلك، عند الوصول إلى الخطوة 17، يرجى ملاحظة ما يلي:

• سيتم الآن تخزين الكائن المرتجع في المتغير bestPlayInfo الذي أنشأناه في الخطوة 7.
• لن تكرر دالة minimax الخطوة 12 لأن عبارة حلقة for لم تعد نشطة.

الشكل 9: نظرة عامة على جميع اختبارات اللعب والنتائج.

استخدام البيانات داخل bestPlayInfo

بالنظر إلى لوحة هذا الدليل (لوحة لعب في حالة قريبة من النهاية، كما هو موضح في الشكل 2 من الخطوة 2)، سيكون الكائن في المتغير bestPlayInfo هو {index: 4, score: 1}. لذلك، يمكن للذكاء الاصطناعي الآن استخدام قيمة فهرسه لاختيار أفضل خلية للعب عليها. مثال:

 // الحصول على جميع خلايا اللوحة:
 const gameCells = document .querySelectorAll( ".cell" );

 // أدناه هو المتغير الذي أنشأناه في الخطوة 3:
 const aiMark = "X" ;

 // هذا هو bestPlayInfo الذي أنشأناه في الخطوة 7 ليحتوي على أفضل كائن اختبار لعب للاعب الذكاء الاصطناعي:
 const bestPlayInfo = minimax(currentBoardState, aiMark);

 // لعب علامة الذكاء الاصطناعي على الخلية الأفضل له:
 gameCells[bestPlayInfo.index].innerText = aiMark;

لذلك، سيفوز لاعب الذكاء الاصطناعي باللعبة، وستبدو اللوحة الجديدة الآن على النحو التالي:

الشكل 10: لوحة اللعبة النهائية تظهر أن الذكاء الاصطناعي (اللاعب X) قد فاز باللعبة.

نظرة عامة على خوارزمية هذا الدليل

فيما يلي خوارزمية المينيماكس الكاملة لهذا الدليل. لا تتردد في إدراجها في محرر الأكواد الخاص بك. جربها مع سيناريوهات لعب مختلفة، واستخدم وحدة التحكم (console) للاختبار مرارًا وتكرارًا حتى تشعر بالراحة في بناء ذكاء اصطناعي لا يُقهر. وتذكر، البرمجة تكون أفضل فقط عندما تكتب الكود بذكاء ومتعة، لذا استمتع بوقتك!

 // الخطوة 3 - تخزين الحالة الحالية للوحة في مصفوفة وتحديد مالك كل علامة:
 const currentBoardState = [
  "X", 1, "O",
  "X", 4, "X",
  "O", "O", 8
 ];
 const aiMark = "X";
 const humanMark = "O";

 // الخطوة 4 - إنشاء دالة للحصول على فهارس جميع الخلايا الفارغة:
 function getAllEmptyCellsIndexes ( currBdSt ) {
  return currBdSt.filter( i => i != "O" && i != "X" );
 }

 // الخطوة 5 - إنشاء دالة تحديد الفائز:
 function checkIfWinnerFound ( currBdSt, currMark ) {
  if (
  (currBdSt[0] === currMark && currBdSt[1] === currMark && currBdSt[2] === currMark) ||
  (currBdSt[3] === currMark && currBdSt[4] === currMark && currBdSt[5] === currMark) ||
  (currBdSt[6] === currMark && currBdSt[7] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[0] === currMark && currBdSt[3] === currMark && currBdSt[6] === currMark) ||
  (currBdSt[1] === currMark && currBdSt[4] === currMark && currBdSt[7] === currMark) ||
  (currBdSt[2] === currMark && currBdSt[5] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[0] === currMark && currBdSt[4] === currMark && currBdSt[8] === currMark) ||
  (currBdSt[2] === currMark && currBdSt[4] === currMark && currBdSt[6] === currMark)
  ) {
  return true;
  } else {
  return false;
  }
 }

 // الخطوة 6 - إنشاء خوارزمية المينيماكس:
 function minimax ( currBdSt, currMark ) {

  // الخطوة 8 - تخزين فهارس جميع الخلايا الفارغة:
  const availCellsIndexes = getAllEmptyCellsIndexes(currBdSt);

  // الخطوة 9 - التحقق مما إذا كانت هناك حالة نهائية:
  if (checkIfWinnerFound(currBdSt, humanMark)) {
  return { score : -1 };
  } else if (checkIfWinnerFound(currBdSt, aiMark)) {
  return { score : 1 };
  } else if (availCellsIndexes.length === 0 ) {
  return { score : 0 };
  }

  // الخطوة 10 - إنشاء مكان لتسجيل نتيجة كل اختبار تجريبي:
  const allTestPlayInfos = [];

  // الخطوة 10 - إنشاء عبارة حلقة for ستتكرر عبر كل خلية من الخلايا الفارغة:
  for ( let i = 0 ; i < availCellsIndexes.length; i++) {

  // الخطوة 11 - إنشاء مكان لتخزين نتيجة هذا الاختبار التجريبي النهائية:
  const currentTestPlayInfo = {};

  // الخطوة 11 - حفظ رقم فهرس الخلية التي تعالجها حلقة for حاليًا:
  currentTestPlayInfo.index = currBdSt[availCellsIndexes[i]];

  // الخطوة 11 - وضع علامة اللاعب الحالي على الخلية التي تعالجها حلقة for حاليًا:
  currBdSt[availCellsIndexes[i]] = currMark;

  if (currMark === aiMark) {
  // الخطوة 11 - تشغيل دالة minimax تكراريًا للوحة الجديدة:
  const result = minimax(currBdSt, humanMark);

  // الخطوة 12 - حفظ نتيجة المتغير result في الكائن currentTestPlayInfo:
  currentTestPlayInfo.score = result.score;
  } else {
  // الخطوة 11 - تشغيل دالة minimax تكراريًا للوحة الجديدة:
  const result = minimax(currBdSt, aiMark);

  // الخطوة 12 - حفظ نتيجة المتغير result في الكائن currentTestPlayInfo:
  currentTestPlayInfo.score = result.score;
  }

  // الخطوة 12 - إعادة تعيين اللوحة الحالية إلى حالتها قبل أن يقوم اللاعب الحالي بحركته:
  currBdSt[availCellsIndexes[i]] = currentTestPlayInfo.index;

  // الخطوة 12 - حفظ نتيجة اختبار لعب اللاعب الحالي للاستخدام المستقبلي:
  allTestPlayInfos.push(currentTestPlayInfo);
  }

  // الخطوة 15 - إنشاء مخزن لمرجع أفضل اختبار لعب:
  let bestTestPlay = null ;

  // الخطوة 16 - الحصول على مرجع أفضل اختبار لعب للاعب الحالي:
  if (currMark === aiMark) {
  let bestScore = - Infinity ;
  for ( let i = 0 ; i < allTestPlayInfos.length; i++) {
  if (allTestPlayInfos[i].score > bestScore) {
  bestScore = allTestPlayInfos[i].score;
  bestTestPlay = i;
  }
  }
  } else {
  let bestScore = Infinity ;
  for ( let i = 0 ; i < allTestPlayInfos.length; i++) {
  if (allTestPlayInfos[i].score < bestScore) {
  bestScore = allTestPlayInfos[i].score;
  bestTestPlay = i;
  }
  }
  }

  // الخطوة 17 - الحصول على الكائن ذي أفضل نتيجة اختبار لعب للاعب الحالي:
  return allTestPlayInfos[bestTestPlay];
 }

 // الخطوة 7 - الاستدعاء الأول لدالة minimax:
 const bestPlayInfo = minimax(currentBoardState, aiMark);

الخلاصة التقنية

تُعد خوارزمية المينيماكس حجر الزاوية في بناء الذكاء الاصطناعي للألعاب ذات المعلومات الكاملة (perfect information games) مثل “إكس أو” والشطرنج. يكمن جوهرها في محاكاة جميع الحركات المحتملة للاعبين (المُعظِّم والمُقلِّل) وصولًا إلى الحالات النهائية للعبة، ثم تقييم هذه الحالات لإيجاد المسار الأمثل الذي يضمن أفضل نتيجة ممكنة للذكاء الاصطناعي، مع الأخذ في الاعتبار أن الخصم سيلعب دائمًا بأفضل طريقة ممكنة لتقليل فرص فوز الذكاء الاصطناعي. إن فهم هذه الخوارزمية وتطبيقها يفتح آفاقًا واسعة لتطوير أنظمة ذكاء اصطناعي قادرة على اتخاذ قرارات استراتيجية معقدة بكفاءة عالية.