تطوير الذكاء الاصطناعي في برامج الشطرنج. ضرب الذكاء الاصطناعي شخصا في الألعاب (GO، الشطرنج وغيرها) مشروع تدريب الشطرنج والذكاء الاصطناعي
قبل عام، فاز برنامج ألفاغو الإثارة على أقوى لاعب في العالم، والآن هزمت المخابرات الاصطناعية الأبجدير الأقوى محرك الشطرنج.
أسقط السمكة، والتي تستخدم في إعداد المنزل معظم اللاعبين، تحول الفائز في بطولة TCEC لعام 2016 وبطولة الشطرنج ببرامج الكمبيوتر 2017، لتكون أضعف بوضوح. في المباراة من 100 حزبا، فاز ألفازيرو ب 28 انتصارات في 72 تعادل ولا تضيع أبدا.
بالمناسبة، أمضى Alphazero أربع ساعات فقط ل "دراسة" الشطرنج. آسف، الناس، لكنك لا تغضب.
جميع المبرمجين الأفائزين الذين طوروا بواسطة Deepmind، Google، خلقوا بناء على آلية "تعلم الجهاز"، بشكل أكثر دقة، "التعلم مع التعزيز". ببساطة، فإن الأبجدية لم يدرس الشطرنج بالمعنى التقليدي. ليس لديه كتاب لاول مرة، ولا طاولات Endgame، ولا توجد خوارزميات معقدة لتقييم قوة البيادق المركزية والمسيرة.
يمكن مقارنة عملها بالروبوت الذي يمكنه استخدام الآلاف من قطع الغيار، لكنه لا يعرف مبدأ تشغيل محرك الاحتراق الداخلي، - إنه يمر عبر مجموعات محتملة، حتى يبني فيراري، ولهذا يحتاج إلى وقت أقل من ثلاثية رب الحلقات. لمدة أربع ساعات، لعب البرنامج الكثير من الأطراف معك، ليصبح معلمك الخاص.
حتى الآن، يواصل فريق المبرمجين الصمت. لم يعطوا تعليقات Chess.com، والرجوع إلى حقيقة أن التقرير "بينما قيد النظر"، ولكن هنا يمكنك قراءة نصها الكامل. يشمل فريق البحث Demis Hassabis، مرشح رئيسي من إنجلترا ومؤسس مشارك في Deepmind (اشترته Google في عام 2014). هاسابس، الذي شارك في بطولات ترادف ترادف في افتتاح شطرنج لندن كلاسيك، حاليا في مؤتمر أنظمة معالجة المعلومات العصبية (أنظمة معالجة المعلومات العصبية) في كاليفورنيا، باعتبارها متعاونا للتقرير عن موضوع آخر.
ولكن مع Chess.com شارك بفارغ الصبر أحكامه لاعب الشطرنج الذي لديه تجربة شخصية رائعة في اللعبة ضد أجهزة الكمبيوتر الشطرنج. لا يفاجأ MG Harry Kasparov أن Deepmind قد انتقل من الذهاب إلى الشطرنج.
وقال شيث: "هذا إنجاز ملحوظ، على الرغم من أنه كان متوقعا بعد ألفاغو". "إنها تقترب من" Type-B "، وهي نهج يشبه الإنسان إلى الشطرنج، الذي حلمت قناة شانون وألان تورينج باستبدال تمثال نصفي صلب".
مثل الشخص، تعتبر الأبجدية مواقف أقل من سابقاتها. وذكر التقرير أنه يقدر "إجمالي" 80 ألف وظيفة في الثانية الواحدة مقارنة ب 70 مليون في الثانية من الأسماك.
افتتحت MG Peter-Heine Nielsen، وهي ثانية طويلة الأجل من بطل العالم MG Magnus Karlsen، شغفه، مما يجعله أقرب مع رئيس Fide: الأجانب. قال شيس.كوم: "بعد قراءة التقرير، وعلى وجه الخصوص، بعد مراجعة الحزب، اعتقدت:" كنت دائما فضوليا أنه إذا تم زراعة مظهر أكثر معقولة على كوكبنا وأظهر لنا فنك لعبة الشطرنج. يبدو الآن أعرف ما هو عليه. "
لقد تعلمنا أيضا أهمية مزايا الجذعية، على الأقل في الذكاء الاصطناعي. 25 من 28 من الانتصارات، فاز Alphazero باللون الأبيض (على الرغم من أن النتيجة + 3 \u003d 47-0 أسود من الأسهم، التي يتجاوز تصنيفها 3400، أيضا ليس سيئا).
يظهر التقرير وكيف وغالبا ما اختار المحرك بعض الولادة كما يعلمون. عذرا، عشاق الحماية الهندية القديمة، لكنك لست مؤيدا. الفائدة في الحماية الفرنسية هي أيضا أحكاس UGAS مع مرور الوقت، ولكن الرغبة في لعب غامبيت Ferzy، وخاصة، بدأت بداية اللغة الإنجليزية للتو.
ماذا ستفعل على موقع التعب الأساسي للمخلوق، فقط من أتقن اللعبة بتاريخ 1400 عام؟ سوف يستغرق الأمر الآخر. بعد المباراة من الأسفنولوجيا، تنفق Alphazero على "التدريب" ساعتين فقط وهزمت إلمو، أقوى محركات الكمبيوتر للعبة في Syogi.
لا يقتصر استخدام برنامج التعلم الذاتي المباطيء هذا، بالطبع على الألعاب.
وقال كازاروف "لقد اعتقدت دائما أن هناك الكثير من المعرفة التجريبية في الشطرنج من الجهاز حتى يتمكنوا من اللعب بقوة" من الصفر "، دون استخدام المعرفة البشرية على الإطلاق". ما يمكننا أن نتعلمه عن الشطرنج. بمساعدة Alphazero، التي تفتح آفاق ضخمة لتعلم الآلة في الجهاز بأكملها، قد تجد منتديات لا يمكن الوصول إليها للناس. من الواضح أن العواقب تمتد بعيدا عن الشطرنج وغيرها من الألعاب. قدرة الجهاز لفتح وتجاوز معرفة أنظمة مغلقة معقدة، المتراكمة من قبل البشرية لعدة قرون، - هذه هي أداة تغيير العالم ".
تمت مقابلة الصحفيين Chess.com من ثمانية من أصل عشرة مشاركين بطولات في لندن حول موقفهم من مباراة البرنامج. سيتم نشر الفيديو مع مقابلة على الموقع لاحقا.
انتقد أكثر حدة شروط المباراة MG Hikar Nakamura. الآن هناك مناقشة ساخنة حول قوة الحوسبة للمعارضين، لكن ناكامورا تعتقد أن آخر كان أكثر أهمية.
دعا Gradmaster الأمريكي المباراة "غير شريفة"، مما يحدد ذلك من أجل العمل الأمثل للمحرك، يجب على Ekokfish استخدام كتاب لاول مرة. لا يعتقد ناكامورا أنه من خلال ساعدها، فستفز المخزون بالمباراة، لكن الفجوة في الحساب ستكون أقل بكثير.
"أنا متأكد من أن الرب نفسه الله لن اكتسب 75 في المئة من النظارات مع أبيض دون أي مدى،"، علق على النتيجة ألفاافيرو وايت: 25 انتصارات و 25 انتصارات.
تتأمل MG Larry Kaufman، محرك Komodo Concodo الرائد، في معرفة مدى نجاح البرنامج الجديد على أجهزة الكمبيوتر الشخصية، دون استخدام البهارات الحاسوبية في Google. كما كرر الاعتراضات التي تعبر عنها ناكاكورا حول حقيقة أن مخزونها لعبت دون معرفة لاول مرة المعتادة.
وقال: "بالطبع، إنه أمر لا يصدق تقريبا"، قال: "نعم، سمعت عن إنجازات ألفاغو صفر في اللعبة وتوقعت شيئا كهذا، بالنظر إلى أن فريق المطور كان لديه لاعب شطرنج Demis Hassabis. ومع ذلك، ليس من الواضح ما إذا كان برنامج Alphazero يمكن أن يلعب الشطرنج على جهاز كمبيوتر منتظم، ومدى نجاحه. ربما يقترب الانتشار الحديث لمحركات الشطرنج باستخدام ميزة MiniMax، ولكن حتى الآن من السابق لأوانه إعلانه. تجدر الإشارة إلى أنه أثناء تدريب Alphazero de Facto أنشأ كتابه الأول الذي لاول مرة، لذلك سيكون من العدل استخدامه ضد المحرك مع كتاب لاول مرة جيد. "
عدم لمس ظروف المباراة، يتم تصور Nielsen، في أي مجالات أخرى يمكن تطبيق هذا النوع من التعلم.
"[هذا] العقل الاصطناعي الحديث". "إنه يأتي من شيء مثل الشطرنج إلى مشاكل جديرة بجوائز نوبل وأكثر من ذلك. أعتقد أننا كنا محظوظين لأنهم قرروا قضاء أربع ساعات على الشطرنج، لكن عواقب هذا الاكتشاف أكثر أهمية للغاية ".
موضوع، عصر الطلاب
المعلوماتية وتكنولوجيا المعلومات والاتصالات، 10-11 فئة
مشروع مختصر موجز
تم تطوير المشروع كجزء من الانضباط "المعلوماتية والاتصالات" للطلاب من 10-11 فئة
أسئلة توجيه المشروع
السؤال الأساسي
هل يمكن الكمبيوتر استبدال الشخص؟
مشاكل المشكلة
1. هل يمكن للكمبيوتر نفسه وضع المهام وحلها؟
2. هل يكون الكمبيوتر قادرا على إعادة إنتاج كل تصرفات وأفكار شخص؟
3. هل الكمبيوتر قادر على إدارة شخص؟
مقرر
1. ما هي المهام التي يحلها الكمبيوتر؟
2. هل تكوين EMM الذاتي؟
3. يمكن أن الآلي استبدال شخص ما؟
4. الذكاء الاصطناعي \u003d الذكاء البشري؟
5. هل أحتاج إلى إدارة عمل الكمبيوتر؟
6. هل من الممكن وضع روبوت "على رأس الجدول"؟
7. هل يمكن للكمبيوتر معرفة كيفية التفكير؟
8. هل من الممكن استبدال الدماغ البشري الاصطناعي؟
9. هل يستعد الشخص لتوجيه كل العمل إلى الروبوتات؟
خطة المشروع
تمثيل المشكلة الوضع:
يحتاج المعلم إلى إلقاء العصف الذهني مع الطلاب من أجل تحديد المعرفة الحالية للطلاب حول المشكلة، دوافعهم، ميولها ومصالحهم. أداة - العصف الذهني باستخدام عرض البدء. بمساعدة العرض التقديمي، يخلق المعلم موقفا مشكلة، وينظم هجوم في الدماغ، ومناقشة القضايا التي نشأت، وترشيح الفرضيات وتوزيع الطلاب على المجموعات المواضيعية، مع مراعاة الاهتمامات.
مشروع العمل:
في المرحلة الأولية للمشروع، يساعد المعلم كل مجموعة مواضيعية لتوزيع الأدوار، ومناقشة استراتيجية البحث، وطرق البحث عن المعلومات، وأساليب البحث وإمكانية تنفيذ نتائج العمل. والنتيجة هي خطة نشاط فردية. علاوة على ذلك، تبدأ البحوث المستقلة، عمل محرك البحث من الطلاب وفقا للخطة. في هذه المرحلة، يقوم الطلاب بجمع معلومات حول موضوع مشكلة إشكالية في الموسوعات والكتب المدرسية وعلى الإنترنت، ومناقشة المعلومات التي تم جمعها في المجموعة، وتطوير أدوات البحث، وإجراء البحوث، ومقارنة نتائجها مع المعلومات التي تم جمعها، ورسم استنتاجات كن استجابة للسؤال الإشكالي. ينبغي منح تركيز المعلم للمناقشات المؤقتة والمناقشات داخل المجموعات والمشاورات لمعلمي الموضوعات. سيساعد صاحب تقدير الذات المشاركين في المشروع لتحقيق مستوى النمو الشخصي.
تسجيل أنشطة المشروع:
تم التخطيط لتصميم النتائج في شكل عرض تقديمي أو كتيب أو ويكي مقالة، لذلك قد تحتاج هنا إلى التشاور مع مدرس علوم الكمبيوتر، على إحدى المشاورات من الضروري مناقشة مع المعايير لتقدير هذه المنتجات وبعد في الوقت نفسه، يستعد أداء المجموعة، لذلك في معايير التقييم من الضروري وضع العناصر لتقدير خطاب الطلاب، والقدرة على طرح الأسئلة والرد عليها.
حماية المشروع والمعارض والمناقشة:
في سياق الحماية، تقدم كل مجموعة عملها (عرض تقديمي أو كتيب أو مقالة Wiki)، إجابات أسئلة. يحدث التقييم من خلال المجموعة التي وضعتها المعايير والمشاركين في مجموعات أخرى والمدرسين. تسمح لك حماية المشاريع بالإجابة على السؤال الأساسي، وصياغة استنتاجات عامة حول النتيجة.
في نهاية العمل:
العنصر الضروري في نشاط المشروع بأكمله هو تحليل العمل المنجز، حيث يناقش المعلم مع الطلاب الذين فعلوا ذلك أنه لم يعمل ولماذا. في هذه المرحلة، يمكنك الاتصال بأوراق احترام الذات مرة أخرى ونرى نمو جودة عالية لكل مشارك. بالإضافة إلى ذلك، هناك انعكاس بلوق ممكن. يصبح من المهم منح المجموعة. ويمكنك التعرف على موقع المشروع. 
مشروع بطاقة العمل
نشر المعلم
1997، نيويورك. يفقد بطل العالم في شطرنج Garry Kasparov الكمبيوتر "الأزرق العميق" للشركة IBM، وتصبح هذه المعركة أكبر حفلة شطرنج في جميع الأوقات والشعوب. ستتحدث هذه اللعبة عن "المعركة الإنسانية الأخيرة"، سيقارن الكثيرون في أول رحلة رايت براذرز وهز رواد الفضاء على سطح القمر.
20 يوليو - في يوم الشطرنج الدولي - أخبرك بما حدث بعد ذلك. وأيضا حول ما هي الذكاء الاصطناعي أقل شأنا من الإنسان، ومن أين تورنج آلان هنا. كلمة هاري كاسباروف، بطل الشطرنج العالمي ومؤلف كتاب.
ومن المفارقات، ولكن خلال لعبة متزامنة من اللعبة المتزامنة مع أفضل لاعبي الشطرنج المحترفين، فإن الروبوت هو الأكثر وسيلة للتنقل بين الطاولات وإعادة ترتيب قطع الشطرنج، وعدم حساب التحركات. على الرغم من أن علوم العلوم العلمية لعدة قرون توصلت إلى أتمتاتا تبدو وتنقل كأشخاص، فإن الروبوتات اليوم تعمل بنجاح في العمل الجسدي، يجب أن تعترف بأن سياراتنا أفضل تنتج تفكر بشري من الحركات البشرية.
في الشطرنج، كما هو الحال في العديد من المجالات الأخرى للنشاط، تكون السيارات قوية فيما يضعف الناس، والعكس صحيح.
هذا المبدأ المعروف جيدا في مجال الذكاء الاصطناعي والروبوتات وضعت مكونات القناة في السنة، والتي لاحظت أن "نسبيا ببساطة لضمان قيام أجهزة الكمبيوتر بإجراء اختبار تنمية عقلية أو لعبت في لعبة الداما على مستوى البالغين، لكنها من الصعب أو المستحيل على مهارات طفل يبلغ من العمر عام واحد في القمة للإدراك أو التنقل ".
في ذلك الوقت لم أكن على علم بهذه النظريات؛ بالإضافة إلى ذلك، تحدث قماش حول الداما، وليس عن الشطرنج، ولكن بعد عشر سنوات أصبح من الواضح أن هذا المبدأ ينطبق على مجال نشاطي. Grandmashters تم التعامل معها تماما مع تقدير الموقف والتخطيط الاستراتيجي - أماكن ضعيفة لأجهزة الكمبيوتر الشطرنج، لكنها يمكن أن تحسب العواقب التكتيكية في ثوان، والتي ستكون أفضل العقول البشرية مطلوبة لعدة أيام.
تقدمت بي فكرة. بعد مطابقاتي مع الأزرق العميق جذبت اهتماما وثيقا جدا، أردت مواصلة تجارب الشطرنج، على الرغم من حقيقة أن IBM رفضتهم.
خطتي، ببساطة التحدث، كان مثل: إذا كنت لا تستطيع الفوز بها، ثم انضم إليهم.
اعتقدت: ماذا لو كان الشخص والسيارة ليس المعارضين، ولكن من قبل الشركاء؟ تم تجسيد الفكرة في السنة في Leone الإسبانية، حيث وقعت أول مباراة في الشطرنج المتقدمة (الشطرنج المتقدمة). كان لدى كلا الشريكين جهاز كمبيوتر شخصي في متناول اليد ويمكنه استخدام أي برنامج في اختيارهم أثناء الحزب. كان الهدف هو دخول الجديد، وهو أعلى مستوى من اللعبة - بسبب توليفة أقوى جوانب الذكاء البشري والذكاء. على الرغم من أننا سنرى أبعد من ذلك، فإن كل شيء مرت بالطريقة، فإن النتائج الواضحة لهذه "معارك مينور" أقنعني أن الشطرنج لا يزال بإمكانه تقديم الكثير في هذه المنطقة باعتباره تفاعل العقل البشري والذكاء الاصطناعي.
لهذا الإدانة، جاءت بعيدا عن البداية. كانت الشيشات مقبرة مقدسة طويلة قبل أن يتعلم الناس خلقهم. والآن اكتسب العلم أخيرا الوصول إلى هذه الكأس - وتبت إلى أن يكون الشخص الذي يبقيه في يديه. أمامي وقف الاختيار: رفض المكالمة أو خذها. كيف يمكنني مقاومة؟ كانت فرصة لمزيد من زيادة شعبية الشطرنج وتوسيع الجمهور غزاها بعد المباراة الشهيرة بين بوبي فيشر وبوريس سبازكي خلال الحرب الباردة وبعد معاربي من أجل تاج العالم مع Anatoly Karpov. هذا من شأنه أن يسمح لجيش الرعاة السخي لعالم الشطرنج، خاصة من عدد شركات التكنولوجيا الفائقة. وهكذا، فإن شركة إنتل في منتصف التسعينيات برعاية سلسلة كاملة من بطولات الشطرنج السريعة والكلاسيكية ودورة كاملة من كأس العالم، بما في ذلك مباراة الملكية مع Vishvanatan Anand، التي عقدت في الطابق العلوي من مركز التجارة العالمي. بالإضافة إلى ذلك، قمت بإدارة فضول غير قابل للتغلب عليه. هل يمكن للسيارات حقا أن تتعلم كيف تلعب الشطرنج جيدة مثل بطل العالم؟ هل هم حقا قادرون على التفكير؟
أتساءل ما
ظهر برنامج الشطرنج الأول في وقت سابق من الكمبيوتر الأول.
قامت بتطوير عالم الرياضيات البريطاني الرائعة آلان تورينج، الذي اخترق مدونة آلة التشفير النازي "Enigma". في عام 1952، كتب خوارزمية على الورق، بمساعدة السيارة التي يمكن أن تلعبها السيارة الشطرنج، وأداء عالم الرياضيات نفسه في دور المعالج المركزي. تحولت "آلة الورق من تورينج" لتكون لاعب مختص تماما. ذهب سبب تصميمه إلى أبعد من إطار المصلحة الشخصية لإثارة الشطرنج. منذ فترة طويلة تعتبر القدرة على لعب الشطرنج جزءا من الذكاء البشري، وإنشاء جهاز قادر على هزيمة شخص في هذه اللعبة يجب أن يمثل مظهر سيارة ذكية حقا.
يرتبط اسم آلان Tyurring أيضا إلى الأبد باسم التجربة العقلية التي اقترحها بها، وأجريت في وقت لاحق في الواقع والاسم "اختبار تورينج". جوهرها هو تحديد ما إذا كان الكمبيوتر سيكون قادرا على خداع شخص بطريقة تعتقد أنه يتعامل مع شخص، وإذا كان يستطيع - يتم النظر في الاختبار. حتى قبل تطابقي الأول مع الأزرق العميق، بدأت أجهزة الكمبيوتر في الذهاب من خلال ما يمكن أن يسمى "الشطرنج Testa Turing". ما زالوا لعبوا بشكل سيء للغاية وغالبا ما فعلوا تحركات غير إنسانية بوضوح، لكن في بعض الأحيان تمكنوا بالفعل من لعب الأطراف التي ستكون مناسبة تماما وفي بطولة إنسانية لائقة. كل عام أصبحت السيارة أقوى وأقوى، ولكن في عملية تطورها، تعلمنا المزيد عن الشطرنج أنفسنا أكثر من الذكاء الاصطناعي (AI).
لا يمكن القول أن ذروة عمليات البحث التي يبلغ عمرها 45 عاما، والتي أصبحت حدثا في جميع أنحاء العالم تحولت بخيبة أمل، لكنها أظهرت بوضوح أنه لم يكن هو نفسه لإنشاء ذكاء اصطناعي كان قادرا على المقارنة مع العقل البشري ، ما كان قادرا على مقارنة تورينج والآخرين.
في جوهرها، لم يختلف "العقل" الأزرق العميق عن "العقل" من الإنذار القابل للبرمجة.
فكرت في الأمر فقط تفاقمت بالنسبة لي مرارة الهزيمة - فقدت عيادة الإنذار القابلة للبرمجة، حتى لو كان 10 ملايين دولار ويستحق 10 ملايين دولار؟
إن مجتمع الاتحاد الأفريقي المزعوم، بالطبع، فرح النتيجة وجذب الانتباه، لكن في الوقت نفسه، كان يحبط العلماء بوضوح من حقيقة أن الأزرق العميق لا يشبه الذكاء الاصطناعي الذي حلم به أسلافهم. بدلا من لعب الشطرنج كشخص - إظهار الحدس البشري والتفكير الإبداعي غير القياسي، فإنه يلعب الشطرنج كسيارة: يقيم ما يصل إلى 200 مليون خطوة ممكنة في الثانية والفوز بسبب قوة الحوسبة الخشنة. بالطبع، هذا لا يقلل من الإنجازات ذاتها. في النهاية، الأزرق العميق هو خلق العقل البشري، وفقدان الشخص الذي أنشأه السيارة في وقت واحد يعني انتصاره.
بعد جهد لا يصدق من تلك المباراة، التي تتفاقم من قبل السلوك المشبوه من IBM واتجاهتي للشك، لم أكن مستعدا للتعرف بسهولة على هزيمتي. بصراحة، لم أكن أعرف أبدا كيف أخسر. أعتقد أن الشخص الذي يتم توسيعه بسهولة مع الهزيمة لن يصبح أبدا بطل حقيقي، وهذا المبدأ، بالطبع، هو أيضا عادل وفي حالتي. لكنني أؤمن بالنضال الصادق. ثم اعتقدت أن IBM خدعني - وكذلك العالم بأسره، الذي كان يتبع مباراتنا بشكل وثيق.
يجب الاعتراف بأن التحليل المتكرر لكل جانب من جوانب هذه المبارزة المغلقة مع الأزرق العميق تحولت إلى أمر صعب.
لسنوات، تجنبت عمدا أي محادثات حول هذا الموضوع، حيث أخذ فقط ما كان معروفا بالفعل لعامة الناس.
منشورات مخصصة للأزرق العميق، مجموعة كبيرة، ولكن هذا الكتاب هو الأول والآخر حيث يتم جمع كل الحقائق والقصة بأكملها كما أراها. على الرغم من وجع الذكريات، فقد كانت تجربة مفيدة ومفيدة. علمني معلمي الكبير ميخائيل بوتفينيك، بطل العالم السادس في الشطرنج، أن نبحث عن الحقيقة في كل موقف. وحاولت أداء العهد والبحث عن الحقيقة في جوهر الأزرق العميق للغاية.
التوضيح: Shutterstock.أرسل عملك الجيد في قاعدة المعارف بسيطة. استخدم النموذج أدناه
سيكون الطلاب الطلاب الدراسات العليا، العلماء الشباب الذين يستخدمون قاعدة المعارف في دراساتهم وعملهم ممتنين لك.
منشور من طرف http://www.allbest.ru/
تطويرالبرمجياتوحدةمصطنعفكرلألعابفيشطرنج
شطرنج الكمبيوتر خوارزمية الفكر
- مقدمة
مفهوم "الشطرنج الحاسوب" هو نظير علوم Cybernetics وقسمها "الفكر الاصطناعي". يعد الشطرنج نموذجا مثاليا لدراسة المهام المعقدة، وخاصة تلك التي تحتاج فيها إلى تمثال نصفي. يشير تطوير برنامج الشطرنج إلى مشكلة تطوير الذكاء الاصطناعي للأسباب التالية:
* هناك ثقة عامة في أن المهمة مرتبطة بمشكلة الذكاء الاصطناعي، كما تعتبر الشطرنج أكثر اللعبة الفكرية
* هناك معيار موضوعي للعمل - قوة برنامج الشطرنج
* يمثل التمايز الكبير لهذا المعيار إمكانية تحسين البرنامج تدريجيا.
واحد من مؤسسي Cybernetics ونظرية المعلومات - كلود شانون - في الخمسينات، قاموا أولا بصياغة القواعد اللازمة للاختيار سكتة دماغية على رقعة الشطرنج. في الموضع الذي تم تحليله من أجل عمق معين، يتم نقل جميع الخيارات الممكنة، ويتم تعيين إجمالي المناصب التي تستخدم الوظائف المستهدفة. ثم يتم تنفيذ إجراء MiniMax لإعادة التراجع إلى الموضع الأولي، ويتم تقييم تقييمه والأفضل، وفقا للسيارة، كما هو محدد.
دور الشخص هو تقدير الموقف، بأكبر قدر ممكن من الدقة لتعيين الوظائف المستهدفة. هذه الوظائف لها عنصرين - المواد والموضعية. من أول شيء كل شيء واضح - ميزة مادية (بالأرقام والبجيل)، كقاعدة عامة، حجة خطيرة للغاية لتقييم الموقف كأفضل. بالإضافة إلى ذلك، أصغر المادة على اللوحة على كلا الجانبين، كلما زاد التقييم أكثر دقة.
ولكن مع العنصر الموضعي، كل شيء أكثر تعقيدا: يتم أخذ العديد من العوامل في الاعتبار، على سبيل المثال، ميزات موقع الأشكال الفردية والبجيلات، والمساحة الموجودة على متن الطائرة، والوقت لإعادة تجميع القوات وغيرها. القدرة على تقديره بشكل صحيح لقد كان دور جميع العوامل في موقف معين يعتبر دائما أحد علامات مفاكئة لاعبي الشطرنج. - من الناس.
كان ضعف لعبة الكمبيوتر بالتحديد في إساءة استخدام المواد واستحالة تنفيذ "القوة الغاشمة المطلقة" للخيارات. في كتب الشطرنج من 70s و 1980s، يمكنك العثور على عدد كبير من الأمثلة المثالية لمباراة الأشخاص المصابين بالآلات عندما فاز السيد أو Grandmaster بالحزب بمساعدة التضحيات الجميلة للأرقام والبجيلات. السر واضح بالفعل: بالنسبة للذكاء البشري، على عكس اصطناعي، فإن هيمنة العوامل الموضحة واضحة في تلك اللحظات عندما تم تنفيذ ضحايا المواد.
مرت السنوات، بزيادة في سرعة الكمبيوتر، زاد عمق الحساب، وفي الوقت نفسه تحسن الخوارزميات، مما يحسن تجميع وظائف تقييم الموقف. وفي النصف الثاني من التسعينيات، أصبحت أجهزة الكمبيوتر بالفعل تنافس بنجاح مع Frasisters of Overly Class. Epochal ل "الشطرنج Cybernetics" حدث الحدث في مايو 1997. التي أنشأتها شركة IBM Corporation الأزرق العميق في المباراة من 6 أطراف فازت هاري كاسباروف نفسه. تم تجهيز الكمبيوتر بشعر شطرنج خاص، وتنظرت السيارة حوالي 200 مليون وظيفة في الثانية الواحدة. اجتذبت شركة IBM لمشروعه العديد من الجدات، وقد تم استخدام أحدث إنجازات نظرية الشطرنج لإنشاء أكبر عدد ممكن من الخوارزميات الكمال. وهكذا، كما لوحظ بالفعل، في 90s، بدأت برامج الشطرنج لأجهزة الكمبيوتر المكتبية بإغلاق أجهزة الكمبيوتر المتخصصة.
كل شهر، تزداد قوة برامج الشطرنج وقوة أجهزة الكمبيوتر بشكل لا لبس فيه، قبل الافتراضات الأكثر جريئة من المتفائلين. منذ 12-15 سنة أخرى حول هذا الموضوع "متى ستكون السيارة قادرة على التغلب على Grandmaster؟" في الأساس، تم تخفيضه إلى السؤال "هل هو قادر على القيام بذلك من حيث المبدأ؟". وإذا كانت الإجابة "يمكن" تمكنت من الحصول عليها، فقد تم تقدير الوقت في الفاصل الزمني 15-25 سنة.
وقد دحض الواقع هذه التوقعات. حدث كل شيء أسرع بكثير! بالفعل في منتصف التسعينيات، وجد أن تخليق "برنامج اللعبة + الكمبيوتر" يمكن أن يتنافس مع Grandmaster.
الغرض من العمل هو تطوير وتنفيذ وحدة البرمجيات الاستخباراتية الاصطناعية لمباراة الشطرنج، والتي تشمل:
1. دراسة خوارزميات اللعبة الحالية المعمول بها الشطرنج
2. تطوير خوارزمية سلوك خصم الكمبيوتر
3. تحديد معلمات خوارزمية سلوك خصم الكمبيوتر
4. تنفيذ البرامج، والتي تشمل تنفيذ خوارزمية اللعبة وتطوير واجهة رسومية
5. مقارنة البرامج المتقدمة مع نظائرها الحالية.
1 . تاريختطويرشطرنجبرنامج
في عام 1951، كتب آلان تورينج خوارزمية، والتي يمكن أن تلعبها السيارة الشطرنج. فقط في ذلك الوقت أداء المخترع نفسه في دور السيارة. في نفس عام 1951، يكتب كلية الرياضيات كلود شانون أول مقالتها حول برمجة الشطرنج. ووصف استراتيجيتين لإيجاد منعطف أفضل، ويستند كلاهما إلى الوظيفة المثيرة لتقدير نقاط النهاية:
* اكتب A - تمثال نصفي جميع التحركات الممكنة إلى عمق ثابت، مع مكالمة في نهاية الدالة المقدرة (لأنه من المستحيل تمديده حتى النهاية)
* النوع B - يؤدي التوسع الانتقائي فقط في صفوف معينة معينة تراكمية إلى تقليم الفروع غير المتاحة
تم تصميم الكمبيوتر الأول من خلال خلفية Neumanna للحفاظ على العمليات الحسابية المعقدة عند إنشاء أسلحة نووية. في عام 1950، ظهرت العينة الأولى، قادرة على إنتاج 10000 عملية في الثانية الواحدة. كانت إحدى التجارب الأولى التي تحتوي على الجهاز عبارة عن كتابة برنامج الشطرنج، ومع ذلك، كانت الشطرنج غير قياسية - على متن طائرة 6 * 6 دون أفيال.
بعد بضع سنوات، لعب هذا الكمبيوتر ("مهووس") مع أشخاص: فاز لاعب شطرنج قوي بفوز واثق، وفقد الوافد الجديد في السكتة الدماغية.
في عام 1957، تم تنفيذ IBM704 (42 كيلو هرتز، 7 كيلوبايت - دائمة) في البرنامج على متن مجموعة كاملة، بمشاركة جميع الأرقام. اعتقدت السيارة 4 أيام في 8 دقائق. مستوى اللعبة هو الهواة.
في عام 1962، تفتح Newel و Simon و Shaw خوارزمية تسمى ألفا بيتا (ألفا بيتا)، أعطى النتيجة أي أسوأ من تمثال نصفي كامل، دون استكشاف جميع الخيارات. لم يتطلب أي معرفة شطرنج خاصة، ويمكن تطبيقها لحل أي مهمة بث. جوهر الخوارزمية هو أنه في كل صف من اللعبة، يتم تعقب نتائجها القصوى والأبيض والأسود، وإذا تلقت بالفعل في مرحلة ما من الأسود النتيجة بالفعل، فقد تم بالفعل بحد أقصى أبيض، من قبل، ثم لا معنى للقضاء. عندما يعود تمثال نصفي إلى النقطة التي تحقق فيها الحد الأقصى الأبيض، فإن النتيجة، ستظل مرفوضة. أساس جميع برامج الشطرنج الحديثة هي واحدة من الإصدارات المتقدمة من هذه الخوارزمية.
حوالي عام 1973، كانت جميع برامج الشطرنج من النوع الخامس. تستند أساسا إلى مولدات النزوح من المعقول، والتي تقطع بتقييم ثابت للتمثيل الصغير. مع ظهور المعالجات الأكثر قوة، بدأ المبرمجون في التبديل إلى الكتابة A. تم تعليمهم الأول و Chess4، وكانت هذه البرامج "القوة الخشنة" بمجرد أن وصلوا إلى عمق 5 العناية في المرحلة المتوسطة، بدأوا في الفوز في المسابقات مع V. اكتب البرامج
في عام 1975، يبدأ روبرت هياط في تطوير CrayBlitz، الذي كان منذ فترة طويلة برنامج سبيس أسرع لفترة طويلة ومن 1983 إلى 1989. - أبطال العالم بين برامج الشطرنج. كان يبحث عن حوالي 40-50 ألف وظيفة في الثانية (في عام 1983) أنه من أجل وقته كان إنجازا كبيرا.
في عام 1977، يخلق طومسون وتكوندون من مختبر الجرس أول مجتمع الشطرنج المتخصص. كانت الفكرة الأساسية في تنفيذ بعض أجزاء برنامج الشطرنج (مولد السكتة الدماغية، وظائف تقدير الموقف، وكاشف شاخوف، وما إلى ذلك) في مستوى الأجهزة، والتي أنقذت تأخير البرنامج في كل موقف دون انتظار زيادة قوة المعالجات. يمكن لأفضل أجهزة الكمبيوتر في ذلك الوقت استكشاف ما يصل إلى 5000 وظيفة في الثانية الواحدة، وآلة Tompson Ken، التي تم تسميتها، معالجتها 180 ألف صف واحد في الثانية. يمكن أن يفكر Belle في مواقع 8-9 فجرا، مما وضعه على مستوى المعالج. فاز بالعديد من بطولات الشطرنج الكمبيوتر. ولكن على الرغم من حقيقة أن الحديد المتخصص هو أمر بحجم أسرع من السيارة المعتادة، فإن برنامج CrayBlitz في المتفوق، ثم لا تزال السيارة أفضل.
في التسعينيات، قام ريتشارد لانج، الكتابة فقط على المجمع، ببرنامج قوي للبحث عن عبقرية للغاية. حتى الآن، تم عقد هذا البرنامج بشكل مطرد بمكان 5-6 على بطولة شطرنج الكمبيوتر العالمية. أيضا، في التسعينيات، بدأت خوارزميات الشطرنج في التطور بقوة، ظهرت اليورانيات من السكتة الدماغية الفارغة (Nullmove)، انتقائي قطع الفروع الحدودية لشجرة خرق.
بشكل منفصل، يستحق النظر في برنامج الشطرنج الأكثر شهرة، جهاز كمبيوتر شطرنج Super - Blue Deep. في عام 1987، بدأ الأزرق العميق كتطوير طالب - كان من المثير للاهتمام أن يكون لديك مجموعة من الطلاب القادرين جرب قوتهم، وموضوع الدبلوم ممتاز. التقدم المحرز في التكنولوجيا يسمح بإصدار أول إصدار من المعالجات (يسمى Chiptest) بسرعة كبيرة. النسخة المتقدمة التالية، المسمى الفكر العميق يتبع. في هذه المرحلة، لاحظت المجموعة إدارة تسويق IBM للشركة ومعالجتها باقتراح، حيث كان من المستحيل رفضه. نتيجة الصلب الأزرق العميق والأزرق العميق الثاني. وبالتالي، فإن العميق الأزرق الثاني هو نتيجة لأكثر من 10 سنوات من تشغيل مجموعة قادرة جدا، حيث كل من المبرمجين / السكك الحديدية والجهات المكتسة الشديدة. تم تمويل جميع الأعمال من قبل IBM، لذلك كان لدى المجموعة موارد لم تحلم بالمنظمات الأكاديمية. يتم إجراء Deep Blue II بناء على خادم IBM RS / 6000 قوي. يحتوي الخادم على 31 معالجات عادية؛ أعلن المرء أن الشيء الرئيسي، يخضع ل 30 آخرين. يتم توصيل معالج الشطرنج التخصصي 16 معالج كل "عامل"، بهذه الطريقة هناك 480 معالجات الشطرنج. المعقدة بأكملها معالجتها أكثر من مليار مواقف في الثانية الواحدة.
في 11 مايو 1997، فاز عميق Blue II بطل العالم في الشطرنج Garry Kasparov في المباراة من 6 أطراف. بعد المباراة مع البطل، تم تفكيك الأزرق العميق.
كما ترون، بدءا من الأول، وتنتهي مع البرامج الأكثر حداثة، تم بناء برامج الشطرنج على أساس سلامة التحركات الممكنة، ولكن كانت هناك محاولات لبناء المزيد من الخوارزميات "الفكرية" غير الساحق. حاول العديد من لاعبي الشطرنج المشهورين تطوير هذه الخوارزميات، لكن النتائج لم تفي بالمتطلبات. على سبيل المثال، كان Botvinnik M.m.، كونه بطل عالمي ومؤلف أعمال عديدة على نظرية الشطرنج، لأكثر من 20 عاما، يشارك في إنشاء برنامج الشطرنج، لكن البرنامج لم يلعب أبدا.
جميع الخوارزميات الزائدة في العثور على أفضل مسار هي بناء شجرة اللعبة وتبحث عن أفضل خطوة.
2. جنرال لواءمفاهيمنظريةألعاب
2.1 خشبممكنالمواقف
دع الشجرة النهائية الموجهة G، التي تتكون المجموعة في رؤوسها تتكون من اثنين من مجموعات فرعية غير مصنوعة من الدورات الفرعية B0 و B1، وأي Vertex P B، وهي ليست بداية أي رابط لهذه الشجرة، ووضعها وفقا للرقم الفعلي OE (ص). هذا يحدد لعبة اثنين من المعارضين مع المعلومات الكاملة. تسمى رؤوس الأشجار الموجهة G، التي تنتمي إلى مجموعة فرعية من B0، مواقف مع أبيض ومجموعة فرعية من B1 - مواقف مع تحركات سوداء؛ تسمى روابط هذه الشجرة السكتات الدماغية البيضاء أو السوداء، اعتمادا على الفرع الفرعي من B0 أو B1 ينتمي إلى البداية. إذا تم وضع موضع P B وفقا للرقم OE (P)، فإنه يطلق عليه النهائي، وتسمى OE (P) تقييم ثابت لهذا المنصب.
الشجرة الموجهة G تسمى شجرة اللعبة.
وفقا للتعريف لأي موقف PB، هناك المسار الوحيد L (P0\u003e P1، P1\u003e P2، ...، PK\u003e P) مع البداية في الشجرة الموجهة نحو الجذر P0 R وتنتهي في الموضع قيد الدراسة ، يسمى هذا المسار حفلة تؤدي إلى وضع P.
الجذر P0 شجرة لعبة G هو موقف مخصص. هذا هو الموقف الذي اقترحه البرنامج، والمهمة هي العثور على أفضل مسار في ذلك. للقيام بذلك، يكفي تحديد OEP0 و OEPI لجميع الوظائف التي يتم الحصول عليها من P0 لكل دورة. يتم تنفيذ تعريفات تقدير الموضع الأولي P0 من خلال مخطط الإطفاء الكامل، وفي نظرية الألعاب، تسمى هذه الخوارزمية خوارزمية Negamax.
يتم احتساب تعقيد شجرة الألعاب من خلال الصيغة: W ^ D، حيث W هو متوسط \u200b\u200bعدد التحركات الممكنة، وعمق الشجرة.
الشكل 1 - شجرة المناصب المحتملة
2.2 مبدأminimax.
يتم تنفيذ هذه الخوارزمية من خلال البحث عن عمق. وهذا هو، بالنسبة لكل فاصلة فشت، فمن الضروري العثور على جميع القمم المجاورة وكرر البحث عنها. نسترجع إلى أعلى العمق الأخير وتتوقع أرباح اللاعب الأول. ثم، من العقدة الأصل، انتقل إلى عقدة الطفل القادمة (إن وجد) ونتوقع أن تكون النظارات المكثفات هناك. إذا انتهى عدد العقد الفرعية، فإننا نبحث عن الحد الأدنى من المكاسب (إذا كان مستوى العقدة الأصل غريبة) أو أقصى حد (حتى الآن). العقدة الوالدية لديها مكاسب مكاسب. نحن نقدم بحث مماثل، ولكن بالنظر بالفعل إلى أن العقدة الأصل هي بالفعل تابعة.
في أوراق الشجرة، يحدث حساب النقاط بالنسبة للاعب الأول، أي ويعتقد أن اللاعب الأول يسعى إلى زيادة مكاسبه، واللاعب الثاني لتقليل أرباح اللاعب الفائز. يفوز اللاعب الأول في حال أن عدد النقاط في الجزء العلوي من شجرة المستوى أكبر من الصفر.
الشكل 2 - البحث في خوارزمية خوارزمية شجرة
نتيجة لذلك، تتوافق العملية المستخدمة من قبل البرنامج حلول بالتناوب (الكمبيوتر / الشخص)، في كل دورة يختار الكمبيوتر الحد الأقصى للتصنيف. إن الحل الذي تم إرجاعه إلى جذر الشجرة تبين بلا شك أنه الخيار الأفضل، بموجب افتراض أن العدو في كل حالة يجعل أقوى التحركات. يتم تنفيذ التقدير الثابت فقط في عقد المستوى الأخير (أوراق الشجرة) لموقف الكمبيوتر.
هذه الخوارزمية تجعل البحث الكامل عن جميع الخيارات. سيتم تقييم عدد المناصب المعينة ك W إلى درجة D، حيث W هو عدد تقريبي من التحركات في موضع واحد، D هو عمق سوء التقدير. بالنسبة لشطرنج W حوالي 40 عاما، وهذا يعني أن العد بالعمق 4، يجب أن نمركز 40 ^ 4 \u003d 2560 ألف وظيفة، وعمق 5 - 10240 ألف وظيفة.
شجرة خرق تنمو أضعفا بشكل كبير. حتى الآن، على أقوى معالجات، مع وجود رمز الأمثل، من الممكن النظر في العمق 6 في الفترة الزمنية المقدرة الحقيقية. هذه هي المشكلة الرئيسية في تطوير خوارزميات لعبة الشطرنج وجميع التطورات تهدف إلى الحد من المجموعات المشتركة.
يوضح الشكل 3 مخطط الكتلة من خوارزمية Minimax لاختيار إحراز تقدم أفضل، فإن الخوارزمية المقدمة من الخوارزمية ترجع أفضل تقدم في التقييم الذي تم الحصول عليه مع تحليل أعمق. يتم تقديم مخطط كتلة خوارزمية لإيجاد تقييم في العمق في الشكل 4.
الشكل 3 - مخطط كتلة لاختيار السكتة الدماغية الأفضل
الشكل 4 - مخطط كتلة للبحث عن تقييم في العمق
عند استدعاء خوارزمية لإيجاد تقييم لعمق مع عمق كبير للغاية، نحصل على تقييم بنزاهة كاملة لجميع التحركات الممكنة.
2.3 طريقةنفيأقصى(Negamax)
في هذه الخوارزمية، فإن التقدير الثابت للموقف لأحد الأطراف يساوي التقييم الثابت للفريق الآخر مع العلامة المعاكسة.
الشكل 5 - طريقة الحد الأقصى السلبي
2.4 ثابتةتقييمموضعوصيانةمتطلباتلمقدرالمهام
التقدير الثابت للموقف هو طريقة موضوعية، التعبير الكمي عن الإحساس الذاتي الذي يحدث في شخص عند النظر في موقف، دون تحليل الطرق الممكنة لتطوير اللعبة. في ألعاب البرمجة، يسمى تقييم موقف ثابت ميزة جودة الموضع.
إذا تم تطبيق إيجاد حركة أفضل بمساعدة شجرة اللعبة بنفس النجاح لجميع الألعاب، فإن تقييم الموقف الثابت هو جزء متخصص للحصول على لعبة معينة. يحدد تخصصها أسلوب لعبة اللاعب الاصطناعي، وتحدد العوامل الموضوعة في الدالة المقدرة الغرض من الصخب.
إن مقارنة الرقم مع الموضع يجعل من الممكن التمييز بين مجموعات السيارات السيئة والجيدة. القدرة على التمييز بين مجموعات جيدة من السيئة، تحدد قوة لاعب افتراضي. في ألعاب شخصين، يتكون التقدير من قبل أحد اللاعبين. إذا ترجع الدالة المقدرة تقدير جيد لاعب واحد، فيجب أن يعود سيئا لخصمه. هذه القاعدة هي معيار قابلية تطبيق أي وظيفة تقييم في الخوارزميات التي تنفذ الذكاء الاصطناعي.
الشرط الأساسي لوظيفة التقييم هو تناظره فيما يتعلق باللاعبين، أي يجب إجراء شرط - ما هو جيد لاعب واحد، سيء للآخر. يجب أن تأخذ ميزة تقديرية جيدة في الاعتبار المبادئ الأساسية لاستراتيجية اللعبة والاستجابة للخصائص التالية:
* المواد - المحسوبة مباشرة كفرق في عدد أشكال اللاعب، من الممكن إضافة معاملات الوزن لكل شخصية محددة
* تحديد المواقع - يوضح جودة أرقام اللاعب
* تطوير الموقف - يوضح أن عدد اللاعب المحتمل يتحرك. كلما تم تطوير الموقف الأفضل، فإن الاستراتيجيات الأكثر إماراتي لها لاعب. لهذا السبب، من الضروري السيطرة على حالتها والحد منها
* تتبع نهاية اللعبة - في حالات الفوز (أخذ ملك الخصم)، يجب أن تعطي أقصى قدر من التصنيف، عادة + إنفينيتي، في حالات فقدان (فقدان الملك)، يجب أن تعيد الحد الأدنى من التصنيف، عادة ما لا نهاية
للعب الشطرنج، من الضروري مراعاة التغيير في تقييم الموقف، اعتمادا على مرحلة الحزب.
الوظيفة المقدرة الكلاسيكية هي وظيفة من بعض الخصائص المذكورة أعلاه من موضع اللعبة، أي الوظيفة المقدرة هي النتيجة الإجمالية لتقدير الموقف من وجهات النظر المختلفة.
الوظيفة المقدرة لجميع الألعاب مختلفة، لأنها تعكس تفاصيل اللعبة. يتم اختيار ميزات التقييم تجريبيا.
أهمية المميزة المختارة أمر ضروري. يتم تحديد الأهمية من خلال ضرب الخصائص المحددة للمعامل المقابل. يجب أن يكون لهذا المعامل مبرر إحصائي.
وبالتالي، يمكن تمثيل الوظيفة المقدرة في النموذج التالي:
f (p) - الوظيفة المقدرة حسب الموقف ص،
عامل أهمية خصائص I-OH،
I-AYA موقف مميزة P.
2.5 تنظيممهام
أثناء تنفيذ الأطروحة، من الضروري التحقيق في الطرق والخوارزميات الحالية لتنفيذ الكمبيوتر من لعبة الشطرنج، وتحديد مزاياها الرئيسية وعيوبها من أجل، بناء على المعرفة المكتسبة، اختر خوارزمية توفر أفضل عملية هذا النظام.
بعد عمل التخرج، فمن الضروري:
أقوم بتطبيق الخوارزميات التي تمت دراستها بلغة البرمجة C #
أقوم بتطبيق تعديلاتها المختلفة باستخدام وحدات إضافية
ب إجراء تجارب رقمية لتقدير جودة النماذج المتقدمة، ومقارنة التعديلات المنفذة، من أجل اختيار الأفضل
لو تطوير واجهة مريحة وبديهية
3. التحقيقالخوارزمياتوالمكملات
3.1 الحروف الأبجديةيكمل
تنظيف Alpha-Beta Cleaning (English Alpha-Beta Pruning) هي خوارزمية بحثية يبدو أنها تقلل من عدد العقد التي تم تقييمها في شجرة البحث في خوارزمية MiniMax. الفكرة الرئيسية هي كما يلي: إذا كان أحد التحركات الخاصة بك، فإن الخصم لديه إجابة غير مواتية لك، فمن غير المعقول تحليل الإجابات الأخرى المحتملة على هذه الخطوات الخاصة بك، لأنه حتى لو كان هناك من بينها، فإن الخصم سوف لا تختارهم. يقع Alpha-Beta Clipping التحسين، حيث لا يتم تغيير نتائج الخوارزمية المحسنة.
الشكل 6 - خوارزمية انقطاع ألفا-بيتا
تكمن ميزة مقطوعة ألفا بيتا في الواقع في حقيقة أن بعض فروع شجرة البحث قد يتم استبعادها بعد النظر في واحدة على الأقل من فروع المستوى بالكامل. نظرا لأن القطع يحدث في كل مستوى من التعشيش (باستثناء الماضي)، يمكن أن يكون التأثير كبيرا تماما. تؤثر فعالية الطريقة بشكل كبير على الفرز الأولية للخيارات (بدون خرق أو بعمق أصغر) - أثناء فرز أفضل الخيارات "الجيدة"، كلما زاد قطع الفروع "السيئة" دون تحليل شامل. يتم إجراء البحث MiniMax في عمق، لذلك في أي وقت يكفي النظر في العقد على طول المسار الوحيد في الشجرة.
الفكرة الرئيسية لقلبة ألفا - بيتا هي العثور على الدورة ليست بالضرورة الأفضل، ولكن "جيد بما فيه الكفاية" من أجل اتخاذ القرار الصحيح.
عند إدخال هذه الخوارزمية، يتم تقديم معلمات ألفا وبيتا، وتسمى نافذة خرق. هذه المعلمات هي المسؤولة عن حدود القطع في المستوى الأول، عند التعمق في شجرة اللعبة، تتغير هذه المعلمات. الخوارزمية ألفا بيتا مع المعلمات ألفا \u003d + إنفينيتي والإرثية \u003d إنفينيتي (القوة الغاشمة مع النافذة الكاملة) تعطي النتيجة نفس خوارزمية negamax، وهذا هو، تمثال نصفي كامل. يوضح الشكل 7 مخطط كتلة خوارزمية ألفا بيتا لحساب تقدير الموقف في العمق.
الشكل 7 - سوق Flowchart ألفا بيتا للبحث عن تقييم في العمق
3.1.1 مثالاساسيقطع
الشكل 8 - مثال لقطة قياسية
النظر في مثال على قطع ألفا بيتا الإصدار بيتا القياسية. في المراكز، نختار هذه الخطوة، لذلك، نختار أعظم قيمة من المراكز الموجودة في و C. القيمة المحسوبة بالفعل - هذا هو 10. عند حساب الموضع الذي اتضح، تتمتع إحدى العقد بقيمة 5 . في موقف مع هذه الخطوة، سوف يقوم خصمنا بذلك، وبالتالي حدد أصغر قيمة. من هذا، يتبع أن قيمة الموضع C ستكون من 5 وما أدناه، لذلك نختار دائما في الخيار. لذلك، حساب بقية العقد معنا لا نسلوك.
3 .1.2 مثالفي الصميمقطع
الشكل 9 - مثال على مقطع متعمق
النظر في مثال لقطة عميقة. في المراكز، سوف نختار بين الرحلات في الموقف في و C. القيمة B \u003d 15. نبدأ بحساب C. في الموضع الإلكتروني، أعطى أحد العقد القيمة 5. في الموضع الإلكتروني، ينتمي اختيار السكتة الدماغية إلى الخصم، مما يعني أن القيمة النهائية ل E ستكون من 5 وانخفاض. إذا كانت القيمة C تساوي ه، فسنختار الخيار في، لأنها أكثر جاذبية. لذلك، نحن لا نعرف بالضرورة القيمة الدقيقة للموضع E، لذلك يتم قطع جميع الفروع الأخرى منه.
3 .2 ترابطيغمر(تكريريتعميق.)
إن معنى هروب العادم أو العطلة التكرار يكمن في مكالمة متكررة إلى إجراء عمق ثابت مع عمق متزايد حتى لا يتم تجاوز الحد الزمني المحدد أو لم يتم تحقيق عمق البحث. ميزة هذه الطريقة هي أنه يجب ألا تختار عمق البحث مقدما؛ بالإضافة إلى ذلك، يمكنك دائما استخدام نتيجة البحث المكتمل الأخير. يمكن استخدام القيم التي تم إرجاعها من كل بحث لضبط نافذة البحث المرغوبة.
بشكل عام، تسبب مقطع ألفا بيتا من أعلى الشجرة على الفاصل الزمني (-؟؛ +؟). ومع ذلك، باستخدام غمر تكراري، يمكننا تغييره.
لنفترض أن X - قيمة الحركة المثلى الموجودة في التكرار السابق، وسوف تشير عدد EPSILON إلى الفرق المقدر في النتائج بين البحث عن العمق D-1 وعمق D. Next، نحن ببساطة استدعاء ألفا -Beta قطع من أعلى الشجرة مع الفاصل الزمني المقدر: Alphabeta (D، X-EPSILON، X + EPSILON).
1. تعد إرجاع القيمة في الفاصل الزمني (X-EPSILON، X + EPSILON) قيمة صحيحة، يمكننا استخدامه.
2. ستعود القيمة من الفاصل الزمني (X-EPSILON، X + EPSILON) من الضروري تكرار الحساب مع الفاصل الزمني المعدل.
حتى لو افترضنا أن طريقة ألفا-بيتا للقطع لن تعطي أي فوز، فإن الزيادة الإجمالية في التحليل الزمني ستثبت فعلا أن تكون صغيرة نسبيا. في الواقع، على افتراض أن متوسط \u200b\u200bعدد الخيارات في كل مستوى هو D، وعدد المستويات المحرن هو P، ثم البحث التكراري إلى المستوى الأول، ثم إلى الثاني، إلخ. إلى P مستوى، ما يعادل (بدون لقطة ألفا بيتا) عرض D + + ... + مواقع.
هذا المبلغ متساو، في حين أن عدد المناصب التي ينظر إليها في التحليل التقليدي متساو. النسبة بين هذين الأرقامين في حد كبير P هي نفس الشيء، وبالتالي، على مقربة من 1 في الحالات عندما تكون D كبيرة بما فيه الكفاية
أيضا، عند استخدام البحث التكراري، يمكنك إدخال عنصر التحكم في الوقت، مما سيسمح للكمبيوتر في أي وقت لتقديم حل مرض. وبالتالي، إذا كان وقت التفكير يقتصر على 5 ثوان، فسوف ينظر في جميع الوظائف على المستوى 2، على سبيل المثال، في 0.001 ثانية، إلى المستوى 3 - في 0.01 ثانية، إلى المستوى 4 - في 1 ثانية، ثم بعد بدء التحليل على مستوى 5، سيتم إجباره على المقاطعة بسبب عدم وجود وقت. ومع ذلك، في الوقت نفسه، سيكون لدى الكمبيوتر بالفعل حل جيد إلى حد ما وجدت في مستوى 4.
نتيجة لذلك، يكون الكمبيوتر قادرا على إعطاء إجابة في الوقت المحدد (على سبيل المثال، لجعل 50 خطوة في ساعتين). من الواضح أيضا أن البرنامج الذي يدعم هذه الطريقة سيلعب مع نقاط القوة المختلفة على أجهزة كمبيوتر مختلفة.
على الرغم من حقيقة أن بعض فروع الأشجار يجب أن تحقق عدة مرات هذه الطريقة تعطي كمية كافية من قطع.
3.3 فرزالتحركات
تتأثر نتائج قطع ألفا بيتا للغاية في النظام الذي يتم فحص التحركات. النظر في هذا على الأمثلة:
في الحالة الأولى، سنقوم بإجراء حساب فرز التحركات "من الأسوأ للأفضل"
الشكل 10 - ألفا بيتا قطع التحركات "من الأسوأ للأفضل"
كما يمكن أن ينظر إليها من المثال، لم يتم قطع أي فروع الأشجار.
الآن فرز التحركات "من الأفضل إلى الأسوأ"
الشكل 11 - ألفا بيتا قطع التحركات "من الأفضل إلى الأسوأ"
في الحالات الأمثل، يجب عرض القوة الغاشمة من قطع ألفا-بيتا من قبل W ^ ((D + 1) / 2) + W ^ (D / 2) - موضع واحد. إنه أقل بكثير من الحد الأدنى.
لزيادة كفاءة مقطورة ألفا بيتا، تحتاج إلى التفكير في ما يجب التحقيق في التحركات أولا. لهذه الأغراض، يتم استخدام الاستدلال القاتل المزعوم.
هذه الفكرة هي أنه إذا كانت هذه الخطوة كانت جيدة في جزء واحد من الشجرة، إذا كان ذلك ممكنا، فإن الأمر يستحق محاولة التحقق من ذلك في الآخرين (في نفس العمق). للقيام بذلك، يتم إدخال مجموعة يتم إدخالها حيث يتم إدخال العديد من أفضل التحركات لكل عمق، إذا كانت هناك تحركات من هذا الجدول في موضعه للعمق الحالية - يتم فحصها أولا.
بالنسبة للتحركات الأخرى، تفضل الخوارزمية تتحرك مع Shaghas وتأخذ.
3 .4 نيجا الكشفية(negascout)
negascout - الوظيفة الإضافية على ألفا بيتا. هذه هي خوارزمية البحث الموجهة لحساب قيمة عقدة minimax.
Negascout هي الخوارزمية الأكثر شعبية في الجهد الإجمالي اليوم. إنه بسيط للغاية ويعطي بعض التسارع (يصل إلى 50٪) دون إجراء أي خطأ إضافي في الحساب. يجمع بينها بشكل جيد للغاية مع السمات الحديثة لبرامج الشطرنج - جداول التجزئة.
تتمتع هذه الخوارزمية بميزة لن تستكشف العقدات التي لا يمكن تقطيعها بألفا بيتا، ولكن يمكن اعتبار بعض الفروع عدة مرات.
تفحص خوارزمية Negascout من العقدة الأولى مع النافذة الكاملة (ألفا، بيتا)، بالنظر إلى هذا الخيار هو الأفضل. العقد التالية التي يحاول قطعها مع نافذة صفرية، أي نافذة (ألفا، ألفا + 1). إذا كان نتيجة الحساب يحسن ألفا، فهذا يعني أن العقدة 1 ليست الأفضل، ويجب فحص هذه العقدة مع النافذة الكاملة، ولكن بدلا من ألفا يمكننا أن نأخذ القيمة (القيمة، بيتا). رمز هذه الطريقة أدناه:
negascout Int Int (خلية [،] لوحة الناظر، عمق Int، Int FinalDepth، Int Alpha، Int Beta، Int Possiblemoves، Bool Ismy)
iNT القيمة \u003d 0، MaxValue \u003d -1000، Leight \u003d 0؛
خلية [،] مجلس \u003d خلية جديدة؛
النقطة [،] التحركات \u003d نقطة جديدة؛
نقطة نقل \u003d نقطة جديدة؛
FindMoves (التحركات، المرفقة لايت، لوحة، حقيقية، حقيقية)؛
possiblemoves \u003d leight؛
FindMoves (التحركات، ref leight، board، خطأ، صحيح)؛
possiblemoves + \u003d leight؛
إذا ((عمق \u003d\u003d FinalDepth) || Gameisover (مجلس، ISMY))
إرجاع eval (مجلس، possiblemoves)؛
العودة -1 * eval (مجلس، possiblemoves)؛
FindMoves (التحركات، المرفوعة leight، board، havereequiredmove (مجلس، ismy)، ismy)؛
int a \u003d alpha، b \u003d beta؛
ل (INT I \u003d 0؛ أنا< leight; i++)
copymove (التحرك، التحركات، أنا)؛
Domove (مجلس، نقل)؛
القيمة \u003d -1 * negascout (مجلس، عمق + 1، finaldepth، -1 * b، -1 * a، possiblemoves،! ismy)؛
إذا (القيمة\u003e قيمة A && a \u003d -1 * negascout (مجلس، عمق + 1، finaldepth، -1 * beta، -1 * القيمة، possiblemoves،! ismy)؛ إذا (القيمة\u003e أ) مبسط (مجلس، لوحة الناظر)؛ كما يمكن أن ينظر إليها من الوصف أعلاه للكشفية السلبية، فإن عبور التحركات هي وظيفة مهمة. إذا قمت بترتيب جميع التحركات "من الأسوأ للأفضل"، فإن تمثال نصفي يمكن أن يستغرق المزيد من الوقت من MiniMax. 3
.5
جدول التجزئة 3
.5
.1
نظرية في الشطرنج أثناء البحث، اتضح ليس شجرة اللعبة، ولكن الرسم البياني غالبا ما يكون في كثير من الأحيان بعد تحركات التحركات التي نحصل عليها نفس الموقف. تتمثل طريقة استخدام جداول التجزئة في الحفاظ على تقييم المناصب التي تعتبر بالفعل. لكل موقف، من الضروري تخزين تقييمه (على وجه التحديد، والتقدير بموجب هذا المنصب)، عمق خرق، أفضل خطوة. الآن، بدأت في تفكيك الموقف، عليك أن تنظر - ولم نلتقي بها بالفعل؟ إذا لم تقابل، فإننا نفعل ذلك كما كان من قبل. إذا التقينا، فإننا ننظر إلى العمق الذي سبق لك تفكيكه. إذا كان الأمر كما نحتاج الآن، أو أعمق، فيمكنك استخدام التقدير القديم وتوفير الوقت. إذا كان أقل، فلا يزال بإمكاننا استخدام جزء من المعلومات، أي أفضل خطوة. أفضل خطوة للعمق n قد يكون الأفضل والعمق n + 1. وهذا هو، إلى جانب وجهةها الأولية، يتحول جدول التجهيز إلى أن يكون مفيدا لتبسيط التحركات. لا يزال يساعد بشكل غير متوقع العطلة التكرارية - عندما نبدأ في التكرار التالي، يتحول جدول التجزئة إلى معلومات عن المعلومات السابقة، وإلى بعض الوقت (إلى عمق 1)، وجميع المراكز لديها ببساطة في ذلك، بأفضل طريقة إلى عمق N-1. غالبا ما يؤدي البرنامج الذي يستخدم الجدول التكراري وجدول التجزئة جميع التكرارات من 1 إلى ن عدة مرات أسرع مما لو كان يبدأ التكرار بحق ن مع احتمال 75٪، فهي دائما أول من اختيار أفضل مسار، وباحتمال ~ 90٪ أفضل خطوة هي من بين الثلاثة الأولى التي تم النظر فيها. 3
.
5
.2
مبيعات Hashing هي واحدة من أقوى الطرق لزيادة أداء الكمبيوتر. باستخدام الجداول Hash هي الأداة الرئيسية في ألعاب الشطرنج البرمجة. جدول التجزئة - يمثل طاولة مفهرسة كبيرة، في الخلايا التي يتم تخزينها المعلومات التالية: مؤشر 2 هش · عمق سوء تقدير لهذه الخطوة · تقييم هذه الخطوة اختيار خوارزمية الإسكان في مؤشر الإسكان هو نقطة أساسية عند استخدام خوارزميات التجزئة. عند اختيار خوارزمية لحساب فهرس التجزئة، من الضروري أن تأخذ في الاعتبار 2 من أهم النقاط: يجب أن يعكس المؤشر أكثر معلومات التقدم الفريدة لتقليل عدد الاصطدامات. يجب أن يكون مؤشر Heshe بسيطا للعد توفر خوارزمية معقدة أفضل مؤشرات لعدد الاصطدامات، لكنها صعبة للغاية في سوء التقدير، وبالتالي تأخذ الكثير من الوقت المعالج. من الضروري بناء خوارزمية، من السهل الاعتماد، ولكن بعد الحد الأدنى لعدد الاصطدامات. لحساب الفهرس والعمليات مع بعض الأقنعة التي تم إنشاؤها عشوائيا تم تحديدها. في البداية، يتم ملء أقنعة التجزئة بأرقام عشوائية. لكل موضع، يتم احتساب مؤشر Hesh Hesh، يتم استخدام الأول للبحث عن موضعه في جدول التجزئة، والثاني للتحقق من التصادمات. قبل أي استخدام للمعلومات من جدول التجزئة، سيتم فحص مصادفة مؤشرات التجزئة الثانية إذا لم تتزامن، ثم حدث الاصطدام، ويتم تجاهل المعلومات. يجب إجراء تحديث معلومات الموقع إلا إذا كان عمق النقص الحالي أكبر من تلك المخزنة بالفعل في جدول التجزئة. معلومات من Hesh، من الممكن الثقة إلا إذا كان العمق في هاهيو، أكثر من عمق الإقلاع الحالي. 3.6
استخدامالمكتباتdebutov. تتمثل الخوارزمية في استخدام المكتبات الأول في المكتبات في استخدام قواعد البيانات المحسوبة مسبقا مع لاول ظهور الأطراف، حيث في بداية الحزب أكبر عدد من التحركات الممكنة لنفس التقديرات. 3
.7
تقييمموضع عند تطوير خوارزمية تقييم موقف ثابت (وظيفة الجودة)، هناك عدم اليقين في الاختيار بين الجودة والسرعة. تعمل الوظائف الثلاثية المقدرة بناء على الأساس الإحصائي ببطء، ولكنها تقدم تقديرات دقيقة للغاية، بعضها حتى دون استخدام إيداع الاستخبارات. أسرع بكثير، تعمل الوظائف البسيطة، مع مراعاة أبسط مبادئ اللعبة، أنها لا تعطي تقييما دقيقا، ولكن السماح للبحث العميق. وبالتالي، فإن درجة دقيقة، ولكن بطيئة، يمكن أن تعطي في غباء، ولكن بسرعة. يتم تحديد جودة التقييم من خلال معرفة اللعبة على أساس مقارنة الموقع. تناسب جودة التقييم مباشرة بسرعة العملية وحجم المعرفة. بما أن ممارسة 40 عاما في إنشاء برامج مع عروض استخبارات اصطناعية، فإن حجم معرفة وظيفة التقييم يتناسب عكسيا مع سرعته. وبصورة بيانية، يظهر هذا الاعتماد في الشكل في شكل عائلة من Hyperball. الشكل 12 - مثال على مقطع متعمق عند تطوير وظيفة تقييم لشطرنج، يجب أن يؤخذ في الاعتبار أنه في تقييم الشطرنج من جميع المعلمات تعتمد على مرحلة اللعبة. تصنع الشيسي للتقسيم على خشبة المسرح: لاول مرة - افتتاح الحزب، Mittelspil - منتصف اللعبة، النهاية هي المرحلة النهائية. بالنسبة للخوارزمية، تقرر تقسيم الأطراف إلى 3 مراحل حسب عدد الأرقام المتبقية على اللوحة مع مشغل الكمبيوتر. في البداية، على السبورة على 16 شخصا في اللاعبين. يوضح الجدول اعتماد مرحلة اللعبة من عدد الأرقام المتبقية: الجدول 1 - مراحل اللعبة 3
.
7
.1
مادةتقييم يعتبر ميزة المواد لأحد اللاعبين أهم المعلمة في نظرية الشطرنج، وبالتالي فإن تقييم المواد يجعل أكبر تأثير على التقييم العام للموقف. يعتبر تقييم المواد بمجموع معاملات الوزن لجميع الأشكال على اللوحة. لا يتم تضمين الملك في تقدير المواد، كما هو الحال في فقدان الملك، يخسر اللاعب تلقائيا. تقييم المقاييس للأرقام هي المهمة الرئيسية في بناء وظيفة التقييم. لتحديد موازين الأرقام، تقرر الاستفادة من خوارزمية ذاتية ذاتيا بناء على الخوارزمية الوراثية. لا تعتمد أوزان الأرقام على مرحلة اللعبة. الخوارزمية الوراثية هي خوارزمية البحث في مجال البحث المستخدمة في حل مشاكل التحسين ومحاكاة الاختيار العشوائي، والجمع بين المعلمات المرغوبة باستخدام الآليات التي تشبه التطور البيولوجي الذي اقترحه هولندا (1975). 3
.
7
.
2
وصفعملوراثيخوارزمية يتم ترميز المهمة الأولية بطريقة يمكن تمثيل حلها كجاغر ("كروموسوم"). يخلق عشوائيا عددا من المتجهات الأولية ("السكان الأولي"). يتم تقييمها باستخدام "وظيفة القدرة على التكيف"، ونتيجة لذلك يتم تعيين كل ناقلات قيمة معينة ("اللياقة")، والتي تحدد احتمال بقاء الجسم يمثلها هذا المتجه. بعد ذلك، باستخدام القيم التي تم الحصول عليها من اللياقة البدنية، يتم تحديد المتجهات (الاختيار)، المسموح بها إلى "Crossbow"،. يتم تطبيق "المشغلين الوراثيين" (عادة "عبور" و "طفرة") على هذه المخلفات)، مما يخلق "الجيل" التالي. يتم تقييم الأفراد من الجيل التالي أيضا، يتم اختيار الاختيار، يتم استخدام المشغلين الوراثيين، إلخ. هذه هي الطريقة التي يتم فيها محاكاة "العملية التطورية"، والتي تواصل عدة دورات حياة (الأجيال) حتى يتم تنفيذ المعيار لوقف الخوارزمية. مثل هذا المعيار يمكن أن يكون: العثور على الحل الأمثل؛ استنفاد عدد الأجيال الصادرة عن التطور؛ استنفاد الوقت الذي صدر للتطور. تخدم الخوارزميات الوراثية بشكل رئيسي للعثور على حلول في مساحات البحث الكبيرة المعقدة للغاية. وبالتالي، من الممكن العمل الخوارزمية الوراثية في المخطط التالي: الشكل 13 - مثال على مقطع متعمق 3
.
7
.
3
مراحلعملوراثيخوارزمية إنشاء السكان الأولي - يتم إنشاء السكان الأولي بشكل عشوائي؛ حتى لو اتضح أن تكون غير تنافسية تماما، فإن الخوارزمية الوراثية ستظل ترجمها بسرعة إلى سكان قابلة للحياة. وبالتالي، في الخطوة الأولى، يمكنك بشكل خاص عدم محاولة جعل الأفراد المجهزة، يكفي لتتناسب مع تنسيق السكان. الاختيار (الاختيار) - من جميع السكان يتم اختيار نسبة معينة ستبقى "على قيد الحياة" في هذه المرحلة من التطور. عبور (الاستنساخ) - من أجل إنتاج سلالة، تحتاج إلى العديد من الآباء والأمهات؛ عادة، بالطبع، نحن بحاجة إلى اثنين تماما. يتم تحديد الاستنساخ في الخوارزميات المختلفة بطرق مختلفة -، بالطبع، يعتمد على عرض البيانات. الشرط الرئيسي للإنجاب هو أن الدردقة أو الأرسل لديهم الفرصة لورث ميزات الوالدين، "خلط" لهم بطريقة معقولة إلى حد ما. الطفرات هي تغيير عشوائي في جزء من الأفراد (الكروموسومات). 3
.
7
.
4
تعريفوزنهاتينمن عنديساعدوراثيخوارزمية تشمل كروموسوم الخوارزمية الوراثية أوزان أرقام الشطرنج، باستثناء الملك. لتعيين السكان الأولي، يتم تعيين قيمة Chromosoma بشكل عشوائي في الفاصل الزمني، باستثناء بيادق وأوزان الملكة، يتم إصلاح قيم موازينها، البيدق - 100، ملكة - 1000. للاختيار، يتم استخدام اختيار البطولة. هناك عشوائي 2 كروموسومات فيما بينهم، ما يصل إلى أربعة فوز، اذهب أولا بدوره. لا يزال الفائز في المبارزة، تتم إزالة الخاسر من السكان. عند العبور، يتم استخدام طريقة عبور نقطة واحدة. يستغرق الأمر 2 الوالدين عشوائيا، ويتم تحديد عدد الكروموسوم بالصدفة، ويظهر الرسم البياني في الشكل 14. نتيجة لذلك، سيعرض كل سليل من الأول من الوالد الثاني من والآخر. الشكل 14 - مثال على مقطع متعمق يتم إجراء الطفرات على النحو التالي: يختار مع بعض احتمالات الكروموسوم، وهم، كل "جين" يتغير حسب عدد عشوائي في النطاق [-50؛ 50]، باستثناء قيمة التقييمات الثابتة للملكة والبجيلات. للقيم النهائية، يتم تقسيم الأوزان التي تم الحصول عليها على 100. 3
.
7
.
5
مجموعتقييم عند تقييم الموضع الذي انتباه الانتباه إلى المكونات الثمانية: 1. قوى المواد من المنافسين 2. عدد الحقول تحت المعركة 3. الحقول الرئيسية 4. تمرير السراويل 5. بيادق مزدوجة 6. هزاز 7. الترويج للبيد 8. سلاسل Hound [* 1] يتم احتساب عدد الحقول الموجودة تحت المعركة في عمق الخشب 2، بالنظر إلى تكلفة مثمرة كبيرة. بالنسبة لكل حقل يدق على رقم الكمبيوتر لتقدير الموضع يضاف 1 نقطة، بالنسبة للحقول التي تحفز أرقام اللاعب تتم إزالة النقاط. يتم نقل القيمة الناتجة إلى أسفل الشجرة كمعلمة. أيضا في عمق 2، النقاط المحسوبة بالسلاسل البحرية، والبيان المزدوج. لحضور الحضور على البيادق اليسرى أو اليمينية، يتلقى الجانب نقطة واحدة. يعتبر البيدق ممرا، إذا كان على رأسه، وكذلك على المجاورة معها، فلا توجد بيادق متنافسة يمكنها منعها لتمريرها إلى النهاية. البيادق المزدوجة - 2 بيادق من لون واحد يقف على رأس واحد. للحصول على وجود بيادق مزدوج، تتم إزالة 4 نقاط، تتم إضافة 5 نقاط لوجود كل بيدق تمرير. الشطرنج لديها الحقول الرئيسية: الشكل 15 - الحقول الرئيسية بالنسبة لاحتلال كل واحد منهم، فإن 4 نقاط إضافية. لأن بعد أن يتم ملك الملك، يقع الملك في وضع مستدام للغاية، يتلقى الجانب 3 نقاط للصب المثالي. أقرب البيدق إلى آخر أفقي، وأكثر من ذلك أقرب إلى التحول. بالنسبة لكل خلية تمر إلى قيمة البيدون المضافة 1. بعد حساب عدد النقاط لكلا الطرفين، يتم الحصول على التقدير النهائي للموقف، من خلال طرح نقاط اللاعب من نظارات خصم الكمبيوتر. 4
.
تطويربرنامجس 4
.1
متطلباتلشطرنجخوارزمية أثناء تطوير نموذج لنمط البرنامج لتشغيل الشطرنج، يجب أن تؤخذ المعلمات التالية في الاعتبار: * خوارزميات الشطرنج تتطلب أيضا الأداء، ويعتمد قوة البرنامج للبرنامج مباشرة على أداء البرنامج * يجب أن تكون وحدات البرامج سهلة التطوير والاختبار * ينبغي أن تكون واجهة المستخدم سهلة وسهولة قابلة للتخصيص 4
.2
الآراءشطرنجخوارزمية يمكن تقسيم معظم البرامج الحديثة إلى 3 فئات: * الفئة الأولى من الباحثين السريعين هي أن الفكرة هي أنه، مما يفسر حد وظيفة التقييم، ودائع تحسين البرنامج بأكمله ككل (الذي يتحقق عادة عن طريق كتابة البرنامج على المجمع)، يمكنك إحضار عدد المناصب التي ينظر فيها البرنامج (NPS - العقد في الثانية الواحدة) إلى رقم فلكي، على سبيل المثال، ما يصل إلى 150-200K NPS على P / 200. وهذا هو، ينفق البرنامج حوالي ألفي أو ألف أوامر إلى كل موقف. يتضمن هذا الرقم التقدم المحرز في الموقف السابق في هذا، وتقدير الموقف، وتوليد التحركات من هذا الموقف، ومنطق الإدارة، إلخ. بشكل عام، تظل الميزة المقدرة في جميع الفتات - حوالي مئات الفرق. يتم تنفيذ البرامج بسرعة بجنون وتصرف تماما في المناصب التكتيكية المعقدة، وكذلك حل المهام المجموع الجنسي بشكل مثالي، ولكن لديها لعبة ضعيفة * الفئة الثانية هي برنامج يستند إلى المعرفة. هنا يتم إلقاء جميع القوى في كتابة وظيفة التقييم المعقدة. تفاعل الأرقام مع بعضها البعض، وغطاء الملك، والسيطرة على المناصب، وتقريبا مرحلة من القمر هي تقريبا. من حيث NPS، يعمل البرنامج 10-100 مرة أبطأ من عمليات البحث السريعة، ولكنها تلعب لعبة الشطرنج الموضعية الجيدة. بتعبير أدق، هذه الشطرنج جيدة، فقط عندما تكون هناك تكتيكات عميقة على اللوحة، أو وقت التحكم في ذلك هو أن البرنامج لديه ما يكفي من الوقت لحساب هذا التكتيك. 4
.3
يتحكممن الوقتفيشطرنجالخوارزميات أهم المعلمة في بناء ذكاء اصطناعي لخصم الشطرنج هو السيطرة على وقت السكتة الدماغية. يعتمد نظام لعبة برنامج الشطرنج على التحكم في الوقت. قبل "التفكير" من قبل الكمبيوتر، يجب حساب الوقت المتاح للكمبيوتر. عند حساب الوقت المتاح في الدورة التدريبية، من الضروري المتابعة من معلمين: * خوارزمية البحث عن بدور أفضل هي أن تكون مبنية على القوى العصرية لجميع التحركات الممكنة في بعض العمق، وبالتالي، يعتمد مباشرة على الوقت الذي يقضيه في تمثال نصفي. كلما زاد الوقت نستخدمه، أقوى الكمبيوتر يلعب * يجب ألا يكون وقت انتظار استجابة خصم الكمبيوتر كبيرا جدا. كأساس، يمكنك اتخاذ لوائح شطرنج دولية، حيث يوجد عدة أنواع من الأطراف: Blitz - 15 دقيقة لكل طرف، بسرعة - 60 دقيقة لكل دفعة، كلاسيكية - أكثر من 60 دقيقة على الحزب. بناء على المعلمات المطلوبة، يتم تحديده لحساب الوقت المتاح للذهال قبل الصيغة التالية: أين: الوقت - الوقت في الدورة؛ full_game_time - Total Party Time؛ AVG_MOVES - متوسط \u200b\u200bعدد السكتات الدماغية للاعب في الحزب؛ collect_time - الوقت المتراكم بالإضافة إلى ذلك؛ د - انخفاض طفيف في الوقت اللازم لحسابات إضافية. يمثل إجمالي الوقت الإجمالي للحزب ومتوسط \u200b\u200bعدد حركات اللاعبين في الحزب اثنين من المعلمات الخارجية الرئيسية، مما يتغير ما يمكنك تغيير قوة اللعبة. وفقا لإحصاءات بوابة الشطرنج Thechess.ru، فإن متوسط \u200b\u200bعدد اللاعبين للحزب يساوي 30، لذلك تقرر أن تأخذ متوسط \u200b\u200bعدد اللاعبين يتحرك في الطرف يساوي 30. وهكذا، من خارج إجمالي الوقت من الطرف محدد. عند تطوير خوارزمية لسلوك خصم الكمبيوتر (الذكاء الاصطناعي)، تم استخدام الخوارزميات التالية: * خوارزمية البحث التكرار، مع التحكم في الوقت * الخوارزمية القصاصة ألفا بيتا و nega-scout * مكتبات Debutov * جدول التجزئة * لفرز التحركات، واستخدمت الاستدلال القاتل والتاريخ. 4
.4
متطوربرنامج في البرنامج في لغة البرمجة، تم تنفيذ جميع الخوارزميات والإضافات المذكورة أعلاه. تظهر لقطات من البرنامج أدناه: الشكل 16- اختيار اللون الشكل 17 - لقطة شاشة البرنامج الشكل 18 - لقطة شاشة البرنامج عندما تحوم على شكل لونك، يتم تمييزه بالأبيض. عند اختيار شخصية للسكتة الدماغية، يصبح لون الحقل برتقالي وجميع الخلايا التي يمكن أن تذهب فيها الشكل إليها، تبرزها بيضاء. عندما تحوم على مثل هذه الخلية، يصبح لونه أيضا برتقاليا. أثناء اللعبة، يتم عرض التحركات المثالية في الجهاز اللوحي على اليسار، يمكن للاعب حفظ القصة في ملف منفصل. 4
.5
يتمركزدورةيبحثأفضلضربة المهمة الرئيسية لدورة البحث الأساسية لأفضل السكتة الدماغية هي إيجاد وأداء أفضل طريقة لخصم الكمبيوتر. تستخدم الدورة مكتبات لاول مرة والبحث التكراري مع التحكم في الوقت. يوضح الشكل 12 عملية العثور على طريقة أفضل: الشكل 19 - دورة البحث الأساسية لأفضل دورة 4
.6
يبحثأفضلضربةأولامستوى تتمثل المهمة الرئيسية في خوارزمية العمل للبحث عن أفضل حركة المستوى الأول (استجابة العدو) في العثور على أفضل خطوة للخصم في المستوى الأول. تم بناء الخوارزمية على خوارزمية Negascout باستخدام التقدير المتعمق، لتحديد تقدير السكتة الدماغية الحالية. يوضح الشكل 13 عمل الخوارزمية: الشكل 20 - ابحث عن المستوى الأول أفضل 4
.7
العثور علىعمقتقديراتضربة المهمة الرئيسية لإيجاد تقييم عمق هي العثور على تقييم الدورة الحالية باستخدام خوارزمية Negascout، واللباس من الصفر، والبيانات من الجدول لديه جدول وتقييم موقف ثابت. يوضح الشكل 14 عملية حساب تقييم الدورة التدريبية في العمق: الشكل 21 - العثور على تصنيف السكتة الدماغية العميقة 4.8
آحرونعارضات ازياءوجدول النموذج الرياضي للبرنامج كما يلي: الشكل 22 - النموذج الرياضي من الرقم الدراسي التجريدي، تتم مناقشة 7 فصول من الورثة، والتي تصف أعمال وخصائص الأرقام. هناك أيضا فئة فارغة، مما يدل على أن الخلية فارغة. المجلس عبارة عن مجموعة من 64 عناصر من الشكل، كل منها يمكن أن يصبح أي من فئات وريث. تم تمثيل الدورة التدريبية في الكمبيوتر في شكل 4 أرقام - إحداثيات (من 1 إلى 8) نقطة بداية وإحداثيات نهاية النهاية. فيما يلي مخطط الحالة للبرنامج: الشكل 23 - الرسم البياني الحالة 5
.
تجريبيتقييمجودةرديئةelizanno.خوارزمية
تعرضت الخوارزميات المنفذة للتحليل المقارن من أجل تحديد الأمثل على سرعة وجودة التكوين. خلال التجربة، عقد عدد من البطولات بين كل زوج من مختلف التطبيقات. 5
.1
تقييمعملالحروف الأبجديةقطع مع هذه التجربة، كان من الضروري معرفة ما إذا كان العامل المتفرع قد تقلص، ونتيجة لتحسين سرعة الخوارزمية، دون أن تفقد جودة القرار بشأن الدورة المكلفة. لتقييم جودة الخوارزمية النهائية، تم مقارنة خوارزمية البحث هذه تجريبيا عن مبدأ Minimax. تقدم الجداول المعاملات التي توضح تصنيف عدد العناصر للخوارزميات، وكذلك نسبة المرات المعينة إلى هذه المشاهدة. الجدول 1 - مقارنة مؤشرات خوارزمية خوارزمية خوارزمية القطع مع خوارزمية Minimax. تظهر نتائج التجارب أن القصاصات ألفا بيتا أفضل بكثير من البحث البسيط minimax. 5
.2
تقييمعملترابطييغوصوفرزالتحركات لتقييم جودة الخوارزمية، تتم مقارنة خوارزمية البحث هذه من ALFA-Beta Cut-Off، ومجرد قطع ألفا بيتا. وصف قواعد اللعبة "معركة البحر". ميزات أجهزة الكمبيوتر الحديثة والذكاء الاصطناعي. إنشاء مخطط كتلة مشتركة للبرنامج، مظهره. المتغيرات والإجراءات والوظائف المطلوبة. خصائص الكائنات المستخدمة في التطبيق. الدورات الدراسية، وأضاف 05.11.2012 التنمية بناء على نهج لعبة "النقاط" لبرمجة "الذكاء الاصطناعي" في الألعاب الموضعية وإمكانية تطبيق هذا النهج لحل المشكلات في مجال الاقتصاد والإدارة وغيرها من المناطق العلمية. نموذج لحالة الألعاب. الأطروحة، وأضاف 07/21/2013 الرسم البياني الهيكلية لوحدة البرنامج. تطوير وحدة البرنامج ومخطط واجهة المستخدم. تنفيذ وحدة البرنامج: رمز البرنامج؛ وصف المشغلين المستخدمين والوظائف. عرض نموذج مخصص مع مصفوفة مملوءة. العمل بالطبع، وأضاف 01.09.2010 دراسة القواعد العامة للعبة في لعبة الداما، دليل المستخدم والمبرمج. خصائص الخوارزميات الرئيسية التي تؤدي المهام فئة القطعة العمرية. تقييم تحركات الكمبيوتر والرجل. بناء شجرة بحث شجرة بناء على تقييم الوظائف. الفحص، وأضاف 12/20/2012 المراحل الرئيسية للتنمية، ومبادئ اختبار وتصحيح وحدة برامج VFS. ميزات التصميم في UML. طرق "الطاقة الخشنة" وتطبيقها عند تصحيح البرنامج. العوامل الضارة الموجودة في مكان عمل المبرمج. الأطروحة، وأضاف 03/07/2012 تحليل النماذج والأساليب لتنفيذ الألعاب الذكية في نظام الشخص الروبوت. بيئة تطوير الرقص. خوارزميات من وحدة الاعتراف ومعالجة البيانات ووظائف وحدة اللعبة. اختبار حزمة البرامج والتصحيح والطاقات. وأوضح 12.08.2017 جوهر ومشكلة تحديد الذكاء الاصطناعي ومهامها ووظائفها الرئيسية. المشاكل الفلسفية لخلق الذكاء الاصطناعي وضمان السلامة البشرية عند العمل مع الروبوت. اختيار طريقة لإنشاء الذكاء الاصطناعي. الامتحان، وأضاف 07.12.2009 برنامج لعبة "لعبة الداما" للعبة بين الرجل والكمبيوتر. تطوير الخوارزميات، التنمية التاريخية للمهام. مناهج مختلفة لبناء أنظمة. إدراج إدراج برامج ووصف الخوارزمية. مكونات الذكاء الاصطناعي. العمل بالطبع، وأضاف 03/26/2009 بناء وتحليل النموذج الرياضي للعبة. تحديد احتمال اكتشاف السفن مع جميع الموقع الممكن وأنظمة البحث المختلفة. تطوير الخوارزميات للاستخبارات الاصطناعية. هيكل البرنامج ومكوناته. الدورات الدراسية، وأضاف 12/22/2012 مفهوم الذكاء الاصطناعي كخصائص للأنظمة الآلية لاتخاذ المهام الفردية للذكاء البشري. أنظمة الخبراء في مجال الطب. مناهج مختلفة لبناء أنظمة الاستخبارات الاصطناعية. خلق الشبكات العصبية. النظر في بعض المفاهيم الأساسية التي ستساعدنا في إنشاء ذكاء اصطناعي بسيط يمكن أن يلعب الشطرنج: في كل خطوة، سنقوم بتحسين خوارزميةنا باستخدام إحدى طرق البرمجة التي تم فحصها. سترى كيف يؤثر كل منهم على نمط لعبة الخوارزمية. يمكن العثور على الخوارزمية النهائية على جيثب. سوف نستخدم مكتبات Chess.js لتوليد التحركات والشطرز .js لتصور اللوحة. تنفذ المكتبة لتوليد التحركات جميع قواعد الشطرنج. بناء على ذلك، يمكننا حساب جميع التحركات لهذه الحالة من اللوحة. تصور وظيفة توليد الوظيفة. يتم استخدام الموضع الأولي كمدخل، وفي الإخراج - كل التحركات الممكنة من هذا الموقف. سيساعدنا استخدام هذه المكتبات على التركيز فقط على المهمة الأكثر إثارة للاهتمام - إنشاء خوارزمية تجد أفضل مسار. سنبدأ في كتابة وظيفة ترجع دورة عشوائية من جميع التحركات الممكنة: Var CalculateBestMove \u003d وظيفة (لعبة) (// جيل من جميع التحركات لهذا المنصب var newgamemoves \u003d game.ugly_moves ()؛ إرجاع newgamemoves؛)؛ على الرغم من أن هذه الخوارزمية ليست لاعبا شطرنج صلب للغاية، إلا أن هذه نقطة انطلاق جيدة، لأن مستواه يكفي للعب معنا: اللعب الأسود بواسطة التحركات العشوائية jsfiddle. الآن دعونا نحاول فهم أي من الجانبين أقوى في موقف معين. أسهل طريقة لتحقيق ذلك هي حساب نقاط القوة النسبية للأرقام الموجودة في المجلس باستخدام الجدول التالي: باستخدام وظيفة التقييم، يمكننا إنشاء خوارزمية تختار أعلى تصنيف: var calculatebestmove \u003d وظيفة (لعبة) (var newgamemoves \u003d game.ugly_moves ()؛ var bestmove \u003d null؛ // استخدم أي عدد سلبي var bestvalue \u003d -9999؛ ل (var i \u003d 0؛ أنا< newGameMoves.length; i++) {
var newGameMove = newGameMoves[i];
game.ugly_move(newGameMove);
//Возьмите отрицательное число, поскольку ИИ играет черными
var boardValue = -evaluateBoard(game.board())
game.undo();
if (boardValue > BestValue) (bestvalue \u003d boardValue؛ bestmove \u003d newgamemove)) العودة bestmove؛ ) التحسين الملموس الوحيد هو أن خوارزمية لدينا الآن ستأكل شخصية، إن أمكن: اللعب الأسود باستخدام وظيفة تقييم بسيطة انظر ماذا حدث في هذه المرحلة، يمكنك في JSfiddle. ثم سنقوم بإنشاء شجرة بحث يمكن منها أن تختار الخوارزمية أفضل مسار. يتم ذلك باستخدام خوارزمية "MiniMax". تقريبا. يترجم في إحدى مقالاتنا، تناولنا بالفعل - تعلمنا إنشاء منظمة العفو الدولية، والتي من المستحيل التغلب على Noliki Cross. في هذه الخوارزمية، يتم التحقيق في الشجرة العودية لجميع التحركات الممكنة بعمق معين، ويقدر الموقف في "أوراق" الشجرة. بعد ذلك، نعيد إما أصغر، أو أكثر قيمة أقل الجلاد في العقدة الأصل، اعتمادا على ما إذا كانت الدورة محسوبة (أي، نحاول تقليل النتيجة أو تعظيمها في كل مستوى). تصور minimax في وضع اصطناعي. أفضل السكتة الدماغية للأبيض - B2-C3، حتى نتمكن من ضمان أننا سنصل إلى الموقف الذي يساوي فيه التقدير -50 Var MiniMax \u003d وظيفة (عمق، لعبة، ISMAXIMISCIPLAYER) (إذا (العمق \u003d\u003d\u003d 0) (إرجاع -EvalBoardBoard (Game.board (Work.board ())؛) Var Newgamemoves \u003d game.ugly_moves ()؛ إذا (Ismaximisplayer) (Var BestMove \u003d -999999؛ ل (var i \u003d 0؛ أنا< newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
} else {
var bestMove = 9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
}
};
مع Minimax، تبدأ خوارزميةنا في فهم التكتيكات الرئيسية لشعر: minimax مع مستوى عمق 2 انظر ماذا حدث في هذه المرحلة، يمكنك في JSfiddle. تعتمد كفاءة Minimax إلى حد كبير على عمق البحث المحقق. هذا ما سنحسن فيه في الخطوة التالية. المواقف التي لا نحتاج إليها إذا تم استخدام مقطع ألفا بيتا. تم زيارة الشجرة في الطلب الموصوف. مع القصاصة ألفا بيتا، نحصل على تحسن كبير في MiniMax، كما هو موضح في المثال التالي: عدد المناصب التي تحتاج إلى تقديرها في حالة البحث بعمق 4 والموقف الأولي الموضح في الصورة. انظر ماذا حدث في هذه المرحلة، يمكنك في JSfiddle. وظيفة التقييم الأولية ساذجة جدا، حيث نحسب نقاط الأرقام الموجودة في المجلس. لتحسينه، سنبدأ النظر في موقف الأرقام. على سبيل المثال، حصان في وسط اللوحة "أغلى"، لأنه يحتوي على تحركات أكثر سهولة، وبالتالي أكثر نشاطا من الحصان على حافة اللوحة.وثائق مماثلة
الخطوة 1. جيل من التحركات والتصور من رقعة الشطرنج
الخطوة 2. لوحة النتائج
الخطوة 3. البحث شجرة و minimam
الخطوة 4. ألفا بيتا كليب
الخطوة 5. تحسين وظيفة التقييم
