كيف تجعل الكمبيوتر يفكر"استعمال طريقة الشجرة"

اهم سؤال هو

ربما يستطيع ربما يستطيع الكمبيوتر اختيار هدف من الالعاب المتاحة له

لكن كيف يتمكن الكمبيوتر من محاصرتي حتى يسجل عليا هدف

اي انه يلتقط هدف على بعد عدة العاب مستقبلية و يختار العابه الى ان يصل الى تسجيل هدف علي

قبل البدا نتفق على قانون وهو اللعبة اذا كانت هدف قيمتها 1 بالنسبة لي وللكمبيوتر واذا لم تكن هدف قيمتها 0

من الرسم هناك عدة العاب متاحة للكمبيوتر و الاولى هدف كما هو مبين

الدوائر تمثل العاب "الدوائر الزرقاء للكمبيوتر والحمراء للشخص

الكمبيوتر بصدد اللعب

كما هو ملاحظ للكمبيوتر ثلاث العاب

الاولى هدف والثانية و الثالثة قيمتها 0

طبعا الكمبيوتر يختار اللعبة الاولى

لكن المشكلة هي في الوضعية الاتية

اللعبة الثانية قيمتها 0

لكن اللعبة الاولى قيمتها 0 لكن هناك ملاحظة

اللعبة الاولى في الحقيقة قيمتها 1

رغم انها ليست هدف الا ان الكمبيوتر اذا لعبها

مهما لعب الشخص فان الكمبيوتر يستطيع تسجيل هدف

لهذا كيف اجعل الكمبيوتر يختار اللعبة الاولى ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

هذا هو السؤال الكبير

ماذا لو طبقنا القاعدتيين الاتيتين

1-اذا كان هناك لعبة قيمتها 1 "اي هدف" سوف اجعل قيمة اللعبة الاب قيمتها -1

2-اذا كانت كل الالعاب الاشقاء قيمتها -1 سوف اجعل قيمة اللعبة الاب 1

نطبق القاعدة على الوضعية الاتية

في المستوى الثالث هناك 8 العاب فوق بعضها بعض

لاحظ اللعبة الثانية في الترتيبة, هذه اللعبة هدف قيمتها 1

اذا اللعبة الاب تصبح قيمتها -1

لاحظ اللعبة الثالثة في الترتيب, هذه اللعبة هدف قيمتها 1

اذا اللعبة الاب تصبح قيمتها -1

ننتقل الى المستوى الثاني يحوي اربع العاب فوق بعضها بعض

من خلال الاجراءات السابقة

وصلنا الى نتيجة وهي ان اللعبة الاولى والثانية في المستوى الثاني

اصبح قيمتها -1 وهم اشقاء اي ان اللعبة الاب لهم "وهي اللعبة الاولى في العمود الاول"

كل ابناءها -1 "حسب القاعدة الثانية تتحول قيمة هذه اللعبة الى واحد"

وبهذا نحصل على الرسم التالي بعد تطبيق القاعدتيين الاولى والثانية

اذا اصبح الكمبيوتر يرى اللعبة الاولى كأنها هدف مباشر

لهذا سوف يلعبها

وبهذا نكون جعلنا الكمبيوتر يختار اللعبة الهدف حتى ولو كان الهدف يبعد عدة مستويات

لهذا تلاحظ ان كمبيوتر يقوم بمحاصرتك الى ان يسجل هدف

وهو في الحقيقة لايعرف ما يفعل بل يطبق قاعدتيين اساسيتين فقط

وهذا هو سر الذكاء الذي يبديه الكمبيوتر

الى اللقاء في الدرس القادم اذا كان عندكم اسألة ارجوا ان تطرحوها

ملخص الدرس

1-اريد ان اجعل الكمبيوتر يتفوق على اللاعب الخصم

2-لدي دالة لقياس قيمة وضعية الرقعة هل هي هدف او لا

3-لدي دالة ترسم شجرة لكل الاحتمالات للالعاب المستقبلية

كيف اجعل الكمبيوتر يختار اللعبة الاحسن او على الاقل يتجنب اللعبة الاسوء

كيف يحاصر الكمبيوتر اللاعب و يتجنب ان يحاصره اللاعب

في الصورة الكمبيوتر لديه ثلاث العاب عليه ان يختار بينها

الكمبيوتر يقيس قيمة كل لعبة يجدها كالتالية

"قياس قيمة اللعبة هو هل اللعبة هدف او لا

في اللعبة التي اعطيتها كمثال الهدف هو اصطفاف القطع مرورا بالمنتصف"

ملاحظة : عليك تحميل اللعبة حتى تفهم المغزى من الدرس

الصورة 1 "الالعاب داخل الاطار هي لعبة هدف قيمتها 1 الالعاب الاخرى قيمتها 0 لانها اوضاع عادية"

لدى الكمبيوتر ثلاث العاب ليختار بينها

لوكنت مكان الكمبيوتر هل تختار اللعبة 2

طبعا لا لانك اذا لعبت اللعبة 2

سوف يلعب الخصم اللعبة 1 ثم في كلتا اللعبيين المتاحتين لك يستطيع الخصم تسجيل هدف

سواء لعبت الاولى او الثانية

اي انك في الخيارات الاولى اذا اخترت اللعبة 2 سوف يحاصرك الخصم الى ان تنهزم

ماذا يجب ان تختار لو كنت في مكان الكمبيوتر

طبعا يجب ان تختار اللعبة 3 لماذا ؟

لانك اذا لعبتها مهما اختار الخصم ان يلعب سواء الاولى او الثانية سوف تستطيع تسجيل هدف

لكن الكمبيوتر لا يرى الامور فهو يرى الالعاب المتاحة له كلها العاب عادية قيمتها 0

نقوم بتطبيق القاعدتيين

1-اذا كانت لعبة قيمتها 1"هدف" اجعل قيمة اللعبة الاب -1

2-اذا كانت لعبة كل الالعاب الاولاد لها قيمتهم -1 اجعل قيمتها 1

بعد تطبيق القاعدتيين على الرسم السابق يصبح الكمبيوتر يرى الامور هكذا

ملاحظة هامة : طبق القاعدتيين من الامام الى الخلاف اي ابدأ من افرع الشجرة الى رأسها

اذا اصبح لدى الكمبيوتر ثلاث خيرات 0 -1 1

1 يفهمها انه سوف يجل هدف اذا لعب اللعبة

-1 سوف اتلقى هدف اذا لعبت اللعبة

0 لا توجد ملاحظة حول اللعبة

طبعا الامور واضحة

سوف يبحث الكمبيوتر على اللعبة التي قيمتها 1 ويلعبها

اذا لم يجد يبحث عن لعبة قيمتها 0 ويلعبها

اذا لم يجد يلعب لعبة قيمتها -1 مرغما

لكن اذا جعلت الكمبيوتر يفكر لعشرة مستويات الى الامام

مثل ما هو موجود في اللعبة المطروحة سابقا

فان الشخص لن يستطيع تسجيل هدف لان الكمبيوتر يرى الى 10 العاب مستقبلية

لهذا لا مجال لهزيمته

"اذا توفر الوقت والعزيمة سوف نطبق هذه القواعد على لعبة الشطرنج في القريب العاجل"

شكرا جزيلا لكم

.. لا اخفيك أني لم افهم كثيرا .. اعرف ان مبدأ الشجرة او tree منتشر كثيرا هذه الايام :D .. دائما اراه في الدروس لاني ابحث عنه الان .. حملت اللعبة وسأجربها ولعلي استوعب الدرس ,, شكرا جزيلا لك ,

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

up

هذا الموضوع غني جداً ، ولم أكن أعرف ما قيمته الا الان ، لذلك يستحق الرفع ،

جميل جدا , نفس المفهوم ونفس التطبيق ونفس اللعبة الشطرنج :lol: .. كتبت كود لفئة بهذا الشكل , قبل ست سنوات تقريبا لم أقرأ الدس بشكل كامل , شجرة الإحتمالات تتضاعف بشكل كبير جدا في المستويات التالية للعبة , ولم أستبعد وقتها إحتمالات معينة لكي لايتم بناء شجرة الإحتمالات التالية لها , المهم أن الإحتمالات كانت في المرحلة الرابعة تصل لأكثر من كم مليون , وكان هناك تسريب في الذاكرة مع أن كل مقابض المؤشرات موجودة لكن عدة أيام debugging فشلت في تحرير الذاكرة المحجوزة .. شفرت ملفاتي في ذلك الوقت في الجهاز وضيعت شهادة التشفير وراحت الملفات مع اللعبة :lol:

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

هل تعرف أخ هيثم ما خوارزمية البحث التي استخدمت ؟

لأنه المشكلة أن الخوارزميات مثل BFS و DFS وحتى A* لها درجة تعقيد عالية ، فالـ A* العادية حسب ما أعرف تعقيدها كالتالي :

Space Complexity: b^d

وكذلك Time Complexity،

الـ b هو عدد التفرعات لكل node .. أقصى تفرعات ، أو معدلها .

و d هو عمق - depth- الحل في الشجرة .

يعني بدون أن أتفلسف .. قد نحتاج الى ذاكرة بحجم 1 تيرا بايت على الاقل .. و الى ساعات .. حتى ننتقل الى المرحلة التالية .

المشكلة الاخرى ، أنه لحل لعبة الشطرنج ، ستحتاج لمعرفة Tricks هذه اللعبة ، فضلاً عن القوانين ، أليس كذلك ؟ مشكلة بصراحة ..

لدي سؤال أخ هيثم ، هل اللعبة التي عملتها ، عبارة عن لعبة بين اللاعب والكمبيوتر ، أم بين جهازي حاسب ؟ وهل كانت تأخذ وقت طويل من اجل التفكير والانتقال الى المرحلة التالية next state ، وهل كان هناك مستويات ، وهل كانت GUI أو Console .. أسئلة كثيرة ، أعرف ذلك :-) .

المشكلة أني أدرس هذه المادة .. ولدينا مشروع عمل لعبة Othello اذا تعرفها .. وهي قريبة من الشطرنج .. يعني نفس الفكرة .. شجرة وخوارزميات .. لكن أسهل طبعاُ .

لذلك رفعت هذا الموضوع :D

يمكنك برمجة Othello عن طريق إستخدام minimax algorithm بعد ذلك يمكنك تقليل عدد الإحتمالات بستخدام Alpha-beta pruning

هذه مقاله تتكلم عن برمجة ال Othello

أيضا يمكن إستخدام ال key word

"Adversarial search" في عملية البحث في google حيث إنها تدل على الخوارزمايات البحث المستخدمه في الألعاب اللتي تلعب من قبل شخصين منثل الشطرنج Othello , XO إلخ...

اقتباس

المشكلة أني أدرس هذه المادة .. ولدينا مشروع عمل لعبة Othello اذا تعرفها .. وهي قريبة من الشطرنج .. يعني نفس الفكرة .. شجرة وخوارزميات .. لكن أسهل طبعاُ .

لذلك رفعت هذا الموضوع

بالمناسبه ماهي الماده التي تدرسها؟ وما هو الكتاب المطلوب عليكم؟

مبروك على الترقيه أخوي عبدالله :)

المادة ذكاء اصطناعي ، والكتاب الرئيسي

Artificial Intelligence: A Modern Approach

المعروف ، الطبعة الثانية .

هذا مقررنا :) :

http://faculty.ksu.e...s/AICourse.aspx

وفيه تطبيقات جميلة ولكن من مصادر ثانية ،

واضح أنك مستمع بالذكاء :D .. المادة جميلة لكن معقدة حبتين ..

الله يعين .

اقتباس

عن طريق إستخدام minimax algorithm بعد ذلك يمكنك تقليل عدد الإحتمالات بستخدام Alpha-beta pruning

ماشاء الله عليك ..

فعلا ، درست شيء عن هذا .. ولكن بشكل نظري حتى الان ,, سنكمل بعد اجازة العيد ان شاء الله .

بالنسبة للـ alpha-beta ..لم أفهمها حتى الان , حيث هناك دالة معينة تقلل عدد الاحتمالات .. وهي معقدة قليلا .

لكن لدي سؤال أخي /

في ألعاب مثل Metal Gear وغيرها ( لا أقصد اللعبة - أقصد نمط اللعبة ) ، هل يتم الاستفادة من هذه الخوارزميات أم أنها صالحة فقط للالعاب التي تصنّف على أنها : Board Games ؟

اقتباس

مبروك على الترقيه أخوي عبدالله

الله يبارك فيك أخوي ..

فعلا الموضوع جميل جدا ولكن لماذا لم يتم ؟

الفكرة الأوليه وصلت بصعوبه بالغه بس الخوارزميات وينها ؟ مش منطق أنزل دلفي مشان أشوف الكود :)

اقتباس

بالنسبة للـ alpha-beta ..لم أفهمها حتى الان , حيث هناك دالة معينة تقلل عدد الاحتمالات .. وهي معقدة قليلا .

الموضوع ليس صعب ولكن يحتاج إلى تركيز لأن كثرت المصلحات والحسابات في خوارزمية minimax تدوخ الراس

حتى أنا تتبع الرسم الشجري للخوارزميه صعب جدا .

المهم هذه بعض النقاط يمكن تساعد في موضوع ال minnimax و alpha-beta

1) في كل فرع رأيسي هناك فقط قيمه واحده alpha وقيمه واحده beta إنضر إلى الصوره

2) كما ترى هناك ثلاثه فروع رأيسيه (A,D,E)وهذه الفروع هي في الأصل MAX's nodes ( ماكس نود تعني أن parent ل node هو MAX) إذا هنالك ثلاثه قيم beta وقيمه واحده alpha لأن الأصل هو واحد

3)alpha-beta pruned هي خوارزميه وضيفتها أن تخمن ما إذا كان فرع ما من الشجره يستحق ان يعمل له scan أو لا

يتم ذلك التخمين على أساس أحدى قيمتين (alpha or beta)

هناك بعض النقاط الإضافيه لم أذكرها بعد لكي لا ألخبطك ولكن أتمنى أن تقرأ المقال التالي

فقط إقرأ The Alpha-Beta Procedure

لا حاجه إلى قراءة كل المقال

وإذا كان هناك أي نقطه غير واضحه فأنا في الخدمه :)

اقتباس

في ألعاب مثل Metal Gear وغيرها ( لا أقصد اللعبة - أقصد نمط اللعبة ) ، هل يتم الاستفادة من هذه الخوارزميات أم أنها صالحة فقط للالعاب التي تصنّف على أنها : Board Games ؟

في العاده مثل هذه الألعاب تحاول التخلص من خوارزميات البحث قدر الإمكان بسبب سلبياتها , فهي ذائما تعتمد على بناء smart agents عن طريق behavior tree وغيرها من الطرق

لم أسمع عن أي لعبه من ذلك النوع إستخدمتهم بصراحه

ولكن أعتقد أن مثل هذه الخوارزميات ممتازه لصنع إستراتيجيتا قويه في مثل ألعاب turn Based Strateg وأيضا RTS

أيضا هذا لا يعني أن لا يمكن إستخدامها في مثل ألعاب FPS , تخيل معي أنك تريد التسلل إلى غرفه معينه داخل مبنا ما في هذه الحاله يمكنك تخيل الوضع مثل ألعاب TBS ولكن الفرق أنك لاتحسب الوضع بالضبط مثلا أنت لا تقول إذا وقفت في النقطه (0,0) بل تعممها وتقول إذا وقفت في الغرفه A سيوجد خطر

هنلك مبدأ يسمى smart environment وهو أن البيئه هي الذكيه وليس الشخصيات حيث أنها تحتوي جميع المعلومات التي سيحتاجها الagent

فإذا عملت smart environment(مثل الغرفه A و الخطر) سيسهل عليك عمل إستراتيجيه عن طريق إستخدام ال minimax

شاهد هذا الفيديو وسترى أن لا يوجد مستحيل في ال AI

ماريو يستخدم A*

ملحوضه الفيديو يحتوي على إغنيه لذلك أخفض الصوت إذا كنت تنزعج من الأغاني

ممتع النقاش معك أخ عبدالله :-) .

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

- شدّني كثيراً الديمو ، ذكاء ماريو ، وهناك عدد من الأسئلة :

1- A* : لا أعرف كيف قام به في هذه اللعبة ، أي ماهي States التي تكون هذا الفضاء ،

ثم ان A* لن تدرس حالة الخصم كما هو الحال مع Alpha-Beta على سبيل المثال ، هل ما أقوله صحيح ؟

لذلك هناك بعض الامور المحيرة ،

قد يكون سبب الحيرة ، هو أنني لم أطبق على لعبة كتلك الالعاب ، فقط على خريطة و لعبة X.O ( لم أكملها ) .

هذا تعليق للمبرمج :

أعرف ماهو المقصود بالـ heuristic function ، لكن ماذا يقصد : بالوقت المطلوب للوصول الى حد النافذة الأيمن ؟

الموضوع مثير !

اقتباس

- شدّني كثيراً الديمو ، ذكاء ماريو ، وهناك عدد من الأسئلة :

1- A* : لا أعرف كيف قام به في هذه اللعبة ، أي ماهي States التي تكون هذا الفضاء ،

حسنا في البدايه نريد إجاد ال initial state , goal state, operators

لنفرض أن ال initial state =موقع ماريو الحالي

و ال goal state = آخر نقطه يمكن لماريو رأيتها من جهت اليمين(هذا ماقصده المبرمج )

و ال operators= (القفز للأمام , القفز للخلف ,المشي للأمام , المشي للخلف, القفز للأعلى...) أي جميع العمليات التي يمكن لماريو القيام بها من موقعه

بعد معرفه هذه المعلومات أصبح تطبيق الفكره أسهل

اقتباس

ثم ان A* لن تدرس حالة الخصم كما هو الحال مع Alpha-Beta على سبيل المثال ، هل ما أقوله صحيح ؟

كلامك صحيح ولكن كما ترى الخصوم هنا ليس أذكياء ولذلك كل اللي نريد نعرفه هو موقعهم و نوعهم (لأن بعض بعضهم محصن من الأعلى مثل القنفذ لذلك الموقع لوحده لا يصلح إلا إذا كنا نخطط لتفاديهم جميعا )

اقتباس

قد يكون سبب الحيرة ، هو أنني لم أطبق على لعبة كتلك الالعاب ، فقط على خريطة و لعبة X.O ( لم أكملها ) .

بالنسبه ل X.O إذا طبقت عليها ال minimax ستهل عليك العمل في مشروعك القادم

اقتباس

أعرف ماهو المقصود بالـ heuristic function ، لكن ماذا يقصد : بالوقت المطلوب للوصول الى حد النافذة الأيمن ؟

كما تعلم أن الجوله في ماريو تتحرك عندما يتحرك ماريو لذلك لنفرض أن آخر نقطه تستطيع رأيتها من جهت اليمين هي نقطت الهذف لذلك عنما ماريو يتجه إلى هذه النقطه ستتولد نقطه هذف أخرى لأنا الجوله تحركت والنقطه السابقه لم تعد النقطه القصوه اليمنى

الآن ماهو المقصود بالوقت ؟

الهذف من التطبيق هو المشاركه في مسابقه ماريو لذلك الفائز في المسابقه سيكون الشخص اللي تطبيقه يفوز في الجولات بأقصر زمن ممكن

لذلك إذا فرضنا أن ماريو دائما يجد أقصر طريق إلى نقطت الهذف هذا يعني أنه سينهي الجوله في أقصر وقت ممكن

هذه مقابله مع المبرمج في موقع AIGameDev

سترى أن المبرمج يشرح مشروعه بتفصيل أكثر و أدق من الشرح الموجود هنا (أيضا بالصور :) )

معلومات قيمة أخوي ، ( ماشاء الله ) .

لي عودة ان شاء الله .. بتطبيقات ومحاولات .