كمبيوتر أوتيللو

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة
كمبيوتر أوتيللو
NTest - برنامج أوتيللو قوي

يشير مصطلح Computer Othello إلى بنية الكمبيوتر التي تشمل الأجهزة والبرامج الحاسوبية القادرة على لعب لعبة Othello . وقد تم تضمينها بشكل خاص في Microsoft Windows من الإصدار 1.0 إلى XP ، حيث تُعرف ببساطة باسم Reversi. [ بحاجة لمصدر ]

التوفر

هناك العديد من برامج أوتيللو مثل NTest و Saio و Edax و Cassio و Pointy Stone و Herakles و WZebra و Logistello والتي يمكن تنزيلها من الإنترنت مجانًا. هذه البرامج، عند تشغيلها على أي جهاز كمبيوتر حديث ، يمكنها تشغيل ألعاب يتم فيها هزيمة أفضل اللاعبين البشريين بسهولة. هذا لأنه على الرغم من أن عواقب الحركات يمكن التنبؤ بها لكل من أجهزة الكمبيوتر والبشر، إلا أن أجهزة الكمبيوتر أفضل في استكشافها. [1]

تقنيات البحث

تبحث برامج أوتيلو الحاسوبية عن أي تحركات قانونية محتملة باستخدام شجرة اللعبة . من الناحية النظرية، تقوم هذه البرامج بفحص جميع المواضع/العقد، حيث تسمى كل حركة يقوم بها لاعب واحد "ply" . يستمر هذا البحث حتى يصل إلى عمق بحث أقصى معين أو يحدد البرنامج أنه تم الوصول إلى موضع "ورقة" نهائي.

يمكن للتنفيذ الساذج لهذا النهج، المعروف باسم Minimax أو Negamax ، البحث فقط على عمق صغير في فترة زمنية عملية، لذلك تم ابتكار طرق مختلفة لزيادة سرعة البحث عن التحركات الجيدة بشكل كبير. تعتمد هذه الطرق على تقليم Alpha-beta و Negascout و MTD(f) و NegaC*. [2] خوارزمية alphabeta هي طريقة لتسريع روتين البحث Minimax عن طريق تقليم الحالات التي لن تُستخدم على أي حال. تستفيد هذه الطريقة من حقيقة أن كل مستوى آخر في الشجرة سيصل إلى الحد الأقصى وكل مستوى آخر سيصل إلى الحد الأدنى. [3]

تُستخدم أيضًا العديد من الأساليب التجريبية لتقليل حجم شجرة البحث: ترتيب التحركات الجيد، وجدول النقل ، والبحث الانتقائي. [4]

لتسريع عملية البحث على الأجهزة ذات المعالجات أو النوى المتعددة، يمكن تنفيذ "بحث موازٍ" . تم إجراء العديد من التجارب باستخدام لعبة Othello، مثل ABDADA [5] أو APHID [6]. في البرامج الحديثة ، يبدو أن YBWC [7] هو النهج المفضل.

قطع متعدد المهام

Multi-ProbCut هو أسلوب استدلالي يستخدم في تقليم شجرة البحث ألفا-بيتا . [8] يقدر أسلوب ProbCut الاستدلالي درجات التقييم على مستويات أعمق من شجرة البحث باستخدام انحدار خطي بين الدرجات الأعمق والأسطح. يوسع أسلوب Multi-ProbCut هذا النهج إلى مستويات متعددة من شجرة البحث. يتم تعلم الانحدار الخطي نفسه من خلال عمليات البحث السابقة في الشجرة، مما يجعل الأسلوب الاستدلالي نوعًا من التحكم الديناميكي في البحث. [9] إنه مفيد بشكل خاص في الألعاب مثل Othello حيث يوجد ارتباط قوي بين درجات التقييم على مستويات أعمق وأسطح. [10] [11]

تقنيات التقييم

هناك ثلاثة نماذج مختلفة لإنشاء وظائف التقييم.

طاولات مربعة الشكل

تختلف قيم المربعات المختلفة - الزوايا جيدة والمربعات المجاورة للزوايا سيئة. وبتجاهل التناظرات، هناك 10 مواضع مختلفة على اللوحة، ولكل منها قيمة لكل من الاحتمالات الثلاثة: القرص الأسود والقرص الأبيض والقرص الفارغ. وهناك نهج أكثر تطورًا يتمثل في الحصول على قيم مختلفة لكل موضع أثناء المراحل المختلفة من اللعبة؛ على سبيل المثال، الزوايا أكثر أهمية في بداية اللعبة وفي منتصفها مقارنة بنهاية اللعبة. [12]

يعتمد على التنقل

يسعى معظم اللاعبين البشر إلى زيادة القدرة على الحركة (عدد الحركات المتاحة) وتقليل الأقراص الحدودية (الأقراص المجاورة للمربعات الفارغة). يتم حساب قدرة اللاعب وقدرته على الحركة، كما يتم حساب قدرة اللاعب المحتملة وقدرته على الحركة. [13] يمكن العثور على هذه التدابير بسرعة كبيرة، وهي تزيد بشكل كبير من قوة اللعب. تمتلك معظم البرامج معرفة بتكوينات الحافة والزاوية وتحاول تقليل عدد الأقراص خلال منتصف اللعبة المبكر، وهي استراتيجية أخرى يستخدمها اللاعبون البشر. [12]

المعاملات المستندة إلى النمط / معاملات النمط

يمكن تقسيم تعظيم القدرة على الحركة وتقليل الحدود إلى تكوينات محلية يمكن إضافتها معًا؛ التنفيذ المعتاد هو تقييم كل صف وعمود وقطر وتكوين زاوية على حدة وإضافة القيم معًا، ويجب تقييم العديد من الأنماط المختلفة. [12] تتم عملية تحديد القيم لجميع التكوينات من خلال أخذ قاعدة بيانات كبيرة من الألعاب التي يتم لعبها بين لاعبين أقوياء وحساب الإحصائيات لكل تكوين في كل مرحلة من مراحل اللعبة من جميع الألعاب. [12]

الخيار الأكثر شيوعًا للتنبؤ بفارق القرص النهائي يستخدم مقياس فارق القرص المرجح حيث يحصل الجانب الفائز على مكافأة تتوافق مع عدد الأقراص. [12]

كتاب الافتتاح

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

تحسينات أخرى

يمكن للأجهزة الأسرع والمعالجات الإضافية تحسين قدرات برنامج تشغيل Othello، مثل البحث عن الطبقات العميقة.

حل عطيل

أثناء اللعب، يتبادل اللاعبون الحركات. يستخدم اللاعب البشري العدادات السوداء بينما يستخدم الكمبيوتر العدادات البيضاء. يبدأ اللاعب البشري اللعبة. [1] يتم حل لعبة أوتيلو بقوة على لوحات 4×4 و6×6، مع فوز اللاعب الثاني (الأبيض) في اللعب المثالي . [14] [15]

عطيل 4 × 4

تحتوي لعبة Othello 4x4 على شجرة لعب صغيرة جدًا وتم حلها في أقل من ثانية واحدة بواسطة العديد من برامج Othello البسيطة التي تستخدم طريقة Minimax، والتي تولد جميع المواضع الممكنة (حوالي 10 ملايين). والنتيجة هي فوز الأبيض بهامش +8 (3-11). [14]

عطيل 6 × 6

تم حل Othello 6x6 في أقل من 100 ساعة بواسطة العديد من برامج Othello البسيطة التي تستخدم طريقة Minimax، والتي تولد جميع المواضع الممكنة (حوالي 3.6 تريليون). والنتيجة هي أنيفوز هيت بهامش +4 (16-20). [16]

عطيل 8 × 8

يُقدر حجم شجرة لعبة أوتيللو 8x8 بحوالي 10 54 عقدة، ويُقدر عدد المواضع القانونية بأقل من 10 28. اعتبارًا من أكتوبر 2023، تدعي إحدى المطبوعات الأولية أن اللعبة قد تم حلها، مع كون النتيجة المثلى هي التعادل. [17] [18] كما تتم مشاركة نتائج الحساب، مما يجعلها واحدة من أكبر الكتب المتاحة للجمهور. [19]

لقد قامت بعض البرامج الرائدة بتوسيع كتبها لسنوات عديدة الآن. ونتيجة لذلك، فإن العديد من الخطوط هي في الممارسة العملية تعادلات أو فوز لأي من الجانبين. فيما يتعلق بالفتحات الرئيسية الثلاثة القطرية والعمودية والمتوازية، يبدو أن الفتحات القطرية والعمودية تؤدي إلى رسم خطوط، في حين أن الفتحة الموازية هي فوز للأسود. تبدو شجرة الرسم أيضًا أكبر بعد الفتحة القطرية منها بعد الفتحة العمودية. [20] [ فشل التحقق ] تتمتع الفتحة الموازية بمزايا قوية للاعب الأسود، مما يمكن الأسود من الفوز دائمًا في لعبة مثالية. [21] [ فشل التحقق ]

محطات بارزة في عالم الكمبيوتر

أ ب ج د هـ ف ج ح
1 أ1إكس ب1إكس سي 1 اكس دي1إكس إي1إكس ف1 اكس جي1اكس اتش 1 اكس 1
2 أ2إكس ب2إكس ثاني أكسيد الكربون دي تو اكس إي2إكس ف2 اكس جي2اكس اتش تو اكس 2
3 أ3 إكس ب3كس سي 3 اكس د3أ إي 3 إكس ف3كس جي3أو h3x 3
4 أ4 إكس ب4اكس سي 4 أو دي4اكس إي4إكس ف4و جي4اكس اتش4اكس 4
5 ايه 5 اكس ب5إكس سي 5 اكس دي 5 اكس إي 5 إكس اف 5 اكس جي 5 اكس اتش 5 اكس 5
6 ايه6 اكس ب6كس سي 6 اكس د6أ إي6 إكس ف6 اكس جي 6 اكس اتش 6 اكس 6
7 ايه 7 اكس ب7إكس سي 7 أو د7أ إي7أو ف7 اكس جي7اكس اتش 7 اكس 7
8 ايه8 اكس ب8إكس سي8 اكس دي8إكس إي8 إكس ف8 اكس جي8 اكس اتش 8 اكس 8
أ ب ج د هـ ف ج ح
لوجيستيليو ضد تاكيشي موراكامي (المباراة الرابعة)
  • 1977 : نشرت مجلة ساينتفك أمريكان أقدم مرجع منشور معروف لبرنامج Othello/Reversi، كتبه NJD Jacobs في BCPL . [22] نشرت BYTE "Othello, a New Ancient Game" كبرنامج مكتوب بلغة BASIC في أكتوبر. [23]
  • 1977 : نشرت شركة Creative Computing نسخة من لعبة Othello التي كتبها إد رايت بلغة FORTRAN . [24] [25]
  • 1978 : أطلقت شركة نينتندو لعبة الفيديو Computer Othello في صالات الألعاب . [26]
  • 1980 : فاز برنامج أوتيلو ذا مور (الذي كتبه مايك ريف وديفيد ليفي ) بمباراة واحدة في مباراة مكونة من ست مباريات ضد بطل العالم هيروشي إينوي. [27] ناقش بيتر دبليو فراي من جامعة نورث وسترن استراتيجيات أوتيلو الحاسوبية والبشرية في BYTE ، وناقش لعبة أوتيلو TRS-80 الخاصة به والتي ادعى فراي أنها هزمت بسهولة نسخة رايت التي تعمل على CDC 6600. [25] طور بول روزنبلوم من جامعة كارنيجي ميلون IAGO ، والذي احتل المركز الثالث في بطولة كمبيوتر جامعة نورث وسترن. [ 28] عندما لعب IAGO The Moor، كان IAGO أفضل في التقاط القطع بشكل دائم والحد من حركة خصمه. [27]
  • 1981 : احتلت لعبة IAGO التي تعمل على DEC KA10 المركز الأول أمام 19 متسابقًا آخرين في بطولة Santa Cruz Open Othello في جامعة كاليفورنيا، سانتا كروز ، وكانت هي الوحيدة التي لم تهزم. احتلت لعبة تشارلز هيث المستندة إلى TRS 80 المركز الثاني. فازت محركات وحدة المعالجة المركزية للحواسيب الصغيرة بالمراكز من الثاني إلى السابع، متقدمة على العديد من الحواسيب الكبيرة والحواسيب الصغيرة؛ تكهن فراي بأن هذا يرجع إلى أن حاسوب Othello لا يستفيد من العديد من مزايا الحواسيب الأكبر حجمًا، مثل العمليات الحسابية ذات الفاصلة العائمة الأسرع . [28]
  • أواخر الثمانينيات : ابتكر كاي فو لي وسانجوي ماهاجان برنامج أوتيلو BILL ، والذي كان مشابهًا لبرنامج IAGO ولكنه كان يشتمل على التعلم البايزي. وقد تفوق برنامج BILL بشكل موثوق على برنامج IAGO. [27]
  • 1992 : بدأ مايكل بورو العمل على برنامج أوتيللو Logistello . كانت تقنيات البحث ووظيفة التقييم وقاعدة المعرفة للأنماط في Logistello أفضل من تلك الموجودة في البرامج السابقة. أتقن Logistello لعبته من خلال لعب أكثر من 100000 لعبة ضد نفسه. [27]
  • 1997 : فاز لوجيستيلو بكل المباريات في مباراة مكونة من ست مباريات ضد بطل العالم تاكيشي موراكامي. ورغم أنه لم يكن هناك شك كبير في أن برامج أوتيلو أقوى من البشر، فقد مرت 17 عامًا منذ آخر مباراة بين الكمبيوتر وبطل العالم. وبعد مباراة عام 1997، لم يعد هناك أي شك: كان لوجيستيلو أفضل بكثير من أي لاعب بشري. [29] [27]
  • 1998 : تقاعد مايكل بورو من Logistello. تضاءل الاهتمام البحثي بـ Othello إلى حد ما، لكن بعض البرامج، بما في ذلك Ntest ​​وSaio وEdax وCassio وZebra وHerakles، استمرت في التطوير. [27]
  • 2004 : أصبح برنامج Ntest ​​أقوى برنامج، وأقوى بكثير من برنامج Logistello.
  • 2005 : أصبح Ntest ​​وSaio وEdax وCirano وZebra أقوى بكثير من Logistello. تقاعد Ntest ​​و Zebra.
  • 2011 : أصبح Saio و Edax و Cyrano أسرع بكثير من Logistello والبرامج الأخرى.
  • 2022 : يظهر Egaroucid كمحرك قوي مستوحى بشكل كبير من Edax.
  • 2023 : تم حل لعبة Othello باستخدام Edax المعدل قليلاً. أصدرت Egaroucid بيانات اللعب الذاتي. [30]

قائمة بأفضل برامج Othello/Reversi

  1. NTest (Ntest) بواسطة كريس ويلتي
  2. Edax (تم أرشفة Edax في 2013-04-06 على موقع Wayback Machine ) بقلم ريتشارد ديلورم
  3. لوجيستيليو (Logistello) بقلم مايكل بورو

انظر أيضا

ملحوظات

  1. ^ من "Dcs.gla.ac.uk" (PDF) . مؤرشف من الأصل (PDF) في 3 يناير 2011.
  2. ^ جان كريستوف ويل (1992). البحث عن NegaC*. مجلة ICCA، المجلد 15، العدد 1، ص 3-7.
  3. ^ أرمانتو، هندروان؛ سانتوسو، جوان؛ جيوفاني دانيال. كورنياوان، فارس؛ يوديانتو، ريكي؛ جوناوان ، ستيفن (أكتوبر 2012). “الشبكة العصبية التطورية للعبة عطيل”. بروسيديا - العلوم الاجتماعية والسلوكية . 57 : 419-425. دوى : 10.1016/j.sbspro.2012.09.1206 .
  4. ^ Buro, M., "Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello", Games in AI Research , HJ van den Herik, H. Iida (ed.), ISBN 90-621-6416-1 , 2000 
  5. ^ جان كريستوف ويل (1996). خوارزمية البحث الموزعة ميني ماكس ABDADA. وقائع مؤتمر علوم الكمبيوتر لعام 1996، ص 131-138. جمعية الحوسبة الآلية، نيويورك، نيويورك، أعيد طبعها في مجلة ICCA، المجلد 19، العدد 1
  6. ^ مارك بروكنجتون (1997). KEYANO Unplugged - بناء برنامج أوتيللو. التقرير الفني TR-97-05، قسم علوم الكمبيوتر، جامعة ألبرتا.
  7. ^ راينر فيلدمان، بيتر ميسليويتز، بوركهارد مونين (1991). برنامج شطرنج موزع بالكامل. التقدم في الشطرنج الكمبيوتر 6
  8. ^ بورو، مايكل (1997). "التجارب باستخدام Multi-ProbCut ووظيفة تقييم جديدة عالية الجودة لأوتيللو". ألعاب في أبحاث الذكاء الاصطناعي . 34 (4): 77-96.
  9. ^ بوليتكو ​​، فاديم. لوستريك، ميتجا؛ شيفر، جوناثان. بيورنسون، ينجفي؛ سيجموندارسون ، سفيرير (1 يونيو 2008). “التحكم الديناميكي في البحث الإرشادي في الوقت الحقيقي”. مجلة أبحاث الذكاء الاصطناعي . 32 : 419-452. دوى : 10.1613/jair.2497 .
  10. ^ Fürnkranz, Johannes (2001). Machines that learn to play games | Guide books. Nova Science Publishers, Inc. 6080 Jericho Tpke. Suite 207 Commack, NYUnited States: Nova Science Publishers, Inc. pp. 11–59. ISBN 978-1-59033-021-0.{{cite book}}:CS1 maint: الموقع ( الرابط )
  11. ^ هاينز، إرنست أ. (2013). البحث القابل للتطوير في الشطرنج الحاسوبي: التحسينات الخوارزمية والتجارب في أعماق البحث العالية. سبرينغر ساينس آند بيزنس ميديا. ص. 32. ISBN 978-3-322-90178-1.
  12. ^ abcdef Gunnar Andersson (2007). "كتابة برنامج أوتيللو". radagast.se . تم الاسترجاع في 2023-02-12 .
  13. ^ كيف يعمل Ntest ​​محفوظ في 2011-11-09 على موقع Wayback Machine في 2 مارس 2005
  14. ^ ab حل أوتيللو 4 × 4 محفوظ 2011-07-07 على موقع واي باك مشين 02 سبتمبر 2008
  15. ^ لعب مثالي في 6x6 أوتيلو من وضعين بديلين للبدء محفوظ في 1 نوفمبر 2009، على موقع واي باك مشين 17 نوفمبر 2004
  16. ^ F. Pittner (يوليو 2006). "الصفحة الرئيسية لـ Tothello". www.tothello.com . تم الاسترجاع في 2023-02-12 .
  17. ^ "Othello is Solved" (PDF) . تم الاسترجاع في 2023-11-04 .
  18. ^ تاكيزاوا ، هيروكي. "النصوص العكسية". جيثب . تم الاسترجاع في 4 نوفمبر 2023 .
  19. ^ "تحليلات لعبة مواقف أوتيللو" . تم الاسترجاع في 2023-11-04 .
  20. ^ "أقوى برنامج أوتيللو من حيث الذكاء الاصطناعي". مؤرشف من الأصل في 2007-01-09 . تم الاسترجاع 2010-04-05 .
  21. ^ "مشروع SaioApp – أقوى محرك أوتيلو" . تم الاسترجاع في 12 فبراير 2023 .
  22. ^ جاردنر، مارتن. الاستجمام الرياضي. مجلة ساينتفك أمريكان، أبريل 1977.
  23. ^ دودا، ريتشارد أو (أكتوبر 1977). "أوتيللو، لعبة قديمة جديدة". BYTE . ص 60-62.
  24. ^ رايت، إد (نوفمبر-ديسمبر 1977). "عطيل". الحوسبة الإبداعية . ص 140-142 . تم الاسترجاع في 18 أكتوبر 2013 .
  25. ^ ab Frey, Peter W (يوليو 1980). "محاكاة عملية اتخاذ القرار البشري على جهاز كمبيوتر شخصي". BYTE . ص. 56. تم الاسترجاع في 18 أكتوبر 2013 .
  26. ^ "كمبيوتر أوتيللو - لعبة فيديو من نينتندو".
  27. ^ abcdef "تاريخ ألعاب الكمبيوتر" (PDF) . مؤرشف من الأصل (PDF) في 24 يناير 2011.
  28. ^ ab Frey, Peter W (يوليو 1981). "بطولة سانتا كروز المفتوحة / بطولة أوتيللو لأجهزة الكمبيوتر". BYTE . ص. 16. تم الاسترجاع في 18 أكتوبر 2013 .
  29. ^ مايكل بورو (20 أغسطس 1997). "مباراة أوتيلو لهذا العام". skatgame.net . تم الاسترجاع في 2023-02-12 .
  30. ^ يامانا، تاكوتو. “نصوص التشغيل الذاتي لـ Egaroucid”. عطيل ايجاروشيد . تم الاسترجاع في 5 نوفمبر 2023 .
ابحث عن كمبيوتر أوتيللو في ويكاموس، القاموس الحر.
  • 4 × 4 عطيل
  • 6 × 6 عطيل
  • برمجة الشطرنج
  • العب لعبة Othello اون لاين ضد الكمبيوتر
تم الاسترجاع من "https://en.wikipedia.org/w/index.php?title=أوتيللو_الكمبيوتر&oldid=1249726555"
Original text
Rate this translation
Your feedback will be used to help improve Google Translate