تي دي غامون

برنامج TD-Gammon هو برنامج حاسوبي للعبة الطاولة، طُوِّر في التسعينيات على يد جيرالد تيسورو في مركز أبحاث توماس ج. واتسون التابع لشركة IBM . ويستمد اسمه من كونه شبكة عصبية اصطناعية مُدرَّبة باستخدام نوع من أنواع التعلّم بالفرق الزمني ، وتحديدًا TD-Lambda . وقد استكشف البرنامج استراتيجيات لم يسبق للبشر اتباعها، مما أدى إلى تطورات في نظرية اللعب الصحيح للعبة الطاولة.

في عام 1993، تم تدريب برنامج TD-Gammon (الإصدار 2.1) من خلال 1.5 مليون مباراة لعب ذاتي، وحقق مستوى لعب أقل بقليل من مستوى أفضل لاعبي الطاولة البشريين في ذلك الوقت. وفي عام 1998، خلال سلسلة من 100 مباراة، هُزم البرنامج أمام بطل العالم بفارق ضئيل بلغ 8 نقاط فقط. وقد لاقى تقييمه غير التقليدي لبعض استراتيجيات الافتتاح قبولًا واعتمادًا من قبل اللاعبين الخبراء. ^{[ 1 ]}

يُشار عادةً إلى TD-gammon باعتباره نجاحًا مبكرًا للتعلم المعزز والشبكات العصبية، وقد تم الاستشهاد به، على سبيل المثال، في أوراق بحثية حول التعلم العميق Q ^{[ 2 ]} و AlphaGo . ^{[ 3 ]}

أثناء اللعب، يقوم برنامج TD-Gammon في كل دور بفحص جميع الحركات القانونية الممكنة وجميع ردودها المحتملة ( بحث استباقي )، ثم يُدخل كل وضعية رقعة ناتجة في دالة التقييم الخاصة به ، ويختار الحركة التي تؤدي إلى وضعية الرقعة التي حصلت على أعلى نتيجة. من هذه الناحية، لا يختلف TD-Gammon عن أي برنامج آخر لألعاب الطاولة على الكمبيوتر تقريبًا. تكمن ابتكارية TD-Gammon في كيفية تعلمه لدالة التقييم الخاصة به.

تعتمد خوارزمية التعلم في TD-Gammon على تحديث الأوزان في شبكتها العصبية بعد كل دور لتقليل الفرق بين تقييمها لمواقع القطع في الأدوار السابقة وتقييمها لموقع القطع في الدور الحالي، ومن هنا جاء مصطلح " التعلم بالفرق الزمني ". وتُحسب نتيجة أي موقع على رقعة الشطرنج كمجموعة من أربعة أرقام تعكس تقدير البرنامج لاحتمالية كل نتيجة ممكنة للعبة: فوز الأبيض بشكل طبيعي، فوز الأسود بشكل طبيعي، فوز الأبيض بـ جامون، فوز الأسود بـ جامون. أما بالنسبة لموقع القطع النهائي في اللعبة، فتقارن الخوارزمية النتيجة الفعلية للعبة بدلاً من تقييمها الخاص لموقع القطع. ^{[ 4 ]}

يتكون جوهر TD-gammon من شبكة عصبية بثلاث طبقات. ^{[ 5 ]}

• تحتوي طبقة الإدخال على نوعين من الخلايا العصبية.
  • يُمثل أحد أنواع البيانات موضع رقعة الشطرنج. وهي أعداد صحيحة غير سالبة تتراوح بين 0 و15، تُشير إلى عدد قطع الشطرنج البيضاء أو السوداء في كل موضع على الرقعة. يوجد 99 عصبونًا مُدخلًا لكل نوع، ليصبح المجموع 198 عصبونًا.
  • نوع آخر من الرموز مخصص للميزات المصممة يدويًا والتي سبق استخدامها في Neurogammon . هذه الميزات تشفر المفاهيم القياسية التي يستخدمها الخبراء البشريون، مثل "المرساة المتقدمة" و"قوة الحصار" و"قوة اللوحة الرئيسية" واحتمالية إصابة "بقعة" (مربع واحد).
• تحتوي الطبقة المخفية على خلايا عصبية مخفية. وقد احتوت الإصدارات اللاحقة على عدد أكبر منها.
• تحتوي طبقة الإخراج على 4 خلايا عصبية، تمثل تقدير الشبكة لاحتمالية ("التوازن") التي ستؤدي إليها اللوحة الحالية. ترمز هذه الخلايا الأربع إلى: فوز الأبيض العادي، فوز الأبيض بـ"غامون"، فوز الأسود العادي، فوز الأسود بـ"غامون". يُعد فوز "الطاولة" نادرًا جدًا لدرجة أن تيسورو اختار عدم تمثيله.

بعد كل دورة، تقوم خوارزمية التعلم بتحديث كل وزن في الشبكة العصبية وفقًا للقاعدة التالية:

${\displaystyle w_{t+1}-w_{t}=\alpha (Y_{t+1}-Y_{t})\sum _{k=1}^{t}\lambda ^{tk}\nabla _{w}Y_{k}}$

أين:

${\displaystyle w_{t+1}-w_{t}}$	هو مقدار تغيير الوزن عن قيمته في الدور السابق.
${\displaystyle Y_{t+1}-Y_{t}}$	هو الفرق بين تقييمات مجلس الإدارة في الدورة الحالية والدورة السابقة.
${\displaystyle \alpha }$	هو مُعامل " معدل التعلم ".
${\displaystyle \lambda }$	هو معيار يؤثر على مدى تأثير الاختلاف الحالي في تقييمات المجلس على التقديرات السابقة.${\displaystyle \lambda =0}$يجعل البرنامج يصحح فقط تقدير الدور السابق؛${\displaystyle \lambda =1}$يجعل البرنامج يحاول تصحيح التقديرات في جميع الدورات السابقة؛ وقيم${\displaystyle \lambda }$تحدد القيم بين 0 و 1 معدلات مختلفة ينبغي أن "تتلاشى" عندها أهمية التقديرات القديمة بمرور الوقت.
${\displaystyle \nabla _{w}Y_{k}}$	يمثل تدرج مخرجات الشبكة العصبية بالنسبة للأوزان: أي مدى تأثير تغيير الوزن على المخرجات. [ 4 ]

وقد تبين أن اختيار الصغار${\displaystyle \lambda }$قدم أداءً جيدًا بشكل متقارب، وكبيرًا${\displaystyle \lambda }$تراجع الأداء. ولهذا السبب، بعد عام 1992، تم تدريب تي دي غامون مع${\displaystyle \lambda =0}$، مما يؤدي إلى التحول إلى التعلم الزمني القياسي. وقد وفر هذا الأمر ضعف الحساب. ^{[ 5 ]}

استخدم الإصدار 1.0 بحثًا بسيطًا من طبقة واحدة: يتم تسجيل كل حركة تالية بواسطة الشبكة العصبية، ويتم اختيار الحركة ذات أعلى درجة.

استخدمت الإصدارات 2.0 و 2.1 البحث المكون من طبقتين:

• قم بإجراء تحليل من طبقة واحدة لإزالة التحركات غير المحتملة ("التقليم الأمامي").
• قم بإجراء تحليل مينيمكس ثنائي اللعب للحركات المحتملة فقط. اختر أفضل حركة، مع ترجيح احتمالية كل رمية نرد محتملة من رميات الخصم الـ 21 (مع إعطاء وزن للرميات غير المزدوجة ضعف وزن الرميات المزدوجة).

استخدمت الإصدارات 3.0 و3.1 البحث ثلاثي الطبقات، باستخدام${\displaystyle 21^{2}=441}$احتمالات رمي ​​النرد بدلاً من 21.

تم تدريب الإصدار الأخير، 3.1، خصيصًا لمباراة استعراضية ضد مالكولم ديفيس في قاعة أبطال AAAI عام 1998. وخسر بنتيجة -8 نقاط، ويعود السبب الرئيسي إلى خطأ واحد، حيث اختار TD-Gammon مضاعفة الرهان وخسر بنتيجة -32 نقطة.

على عكس برامج الطاولة السابقة القائمة على الشبكات العصبية، مثل برنامج Neurogammon (الذي كتبه تيسورو أيضًا)، حيث كان خبير يدرب البرنامج من خلال تقديم التقييم "الصحيح" لكل وضعية، تمت برمجة برنامج TD-Gammon في البداية "بدون معرفة مسبقة". ^{[ 4 ]} في التجارب المبكرة، وباستخدام ترميز لوحة خام فقط دون أي ميزات مصممة بشريًا، وصل برنامج TD-Gammon إلى مستوى لعب مماثل لبرنامج Neurogammon: مستوى لاعب طاولة بشري متوسط ​​المستوى.

على الرغم من أن برنامج TD-Gammon اكتشف خصائص ثاقبة بنفسه، تساءل تيسورو عما إذا كان من الممكن تحسين أدائه باستخدام خصائص مصممة يدويًا مثل تلك الموجودة في برنامج Neurogammon. وبالفعل، سرعان ما تفوق برنامج TD-Gammon، الذي يعتمد على التدريب الذاتي والخصائص المصممة من قبل خبراء، على جميع برامج الطاولة الحاسوبية السابقة. وتوقف عن التحسن بعد حوالي 1,500,000 مباراة (لعب ذاتي) باستخدام شبكة عصبية ثلاثية الطبقات، تضم 198 وحدة إدخال تشفر الخصائص المصممة من قبل خبراء، و80 وحدة مخفية، ووحدة إخراج واحدة تمثل احتمالية الفوز المتوقعة. ^{[ 6 ]}

مكّن التدريب الحصري الذي خضع له برنامج TD-Gammon من خلال اللعب الذاتي (بدلاً من التعلم بالتقليد ) من استكشاف استراتيجيات لم يسبق للبشر التفكير فيها أو استبعدوها خطأً. وكان لنجاحه في استخدام استراتيجيات غير تقليدية أثر كبير على مجتمع لعبة الطاولة. ^{[ 4 ]}

في أواخر عام ١٩٩١، دُعي كلٌّ من بيل روبرتي ، وبول ماغريل، ومالكولم ديفيس، للعب ضد برنامج TD-Gammon (الإصدار ١.٠). لُعب ما مجموعه ٥١ مباراة، خسر فيها TD-Gammon بمعدل -٠.٢٥ نقطة في المباراة الواحدة. وجد روبرتي أن TD-Gammon يُضاهي مستوى اللاعب المتقدم الماهر، وأنه أفضل من أي برنامج سابق للعبة الطاولة. ^{[ ٥ ]} كتب روبرتي لاحقًا عن استخدام TD-Gammon في دراسة لعبة الطاولة. ^{[ ٧ ] [ ٨ ]}

على سبيل المثال، في بداية اللعب، كان الرأي السائد أنه عند رمي النرد والحصول على نتيجة 2-1 أو 4-1 أو 5-1، يجب على الأبيض تحريك قطعة واحدة من النقطة 6 إلى النقطة 5. تُعرف هذه التقنية باسم "التمركز"، وهي تُقلل من مخاطرة التعرض للضرب مقابل فرصة بناء وضعية هجومية. وجد تي دي غامون أن اللعب الأكثر تحفظًا بتقسيم القطع 24-23 كان أفضل. بدأ لاعبو البطولات بتجربة حركة تي دي غامون، وحققوا نجاحًا. في غضون بضع سنوات، اختفى التمركز من البطولات، وحل محله التقسيم، ^{[ 4 ]} على الرغم من أنه عاد للظهور في عام 2006 للحصول على نتيجة 2-1. ^{[ 9 ]}

وجد خبير لعبة الطاولة كيت وولسي أن الحكم الموضعي لبرنامج TD-Gammon، وخاصة موازنة المخاطر مقابل الأمان، كان متفوقًا على حكمه أو حكم أي إنسان آخر. ^{[ 4 ]}

كان أداء برنامج TD-Gammon الممتاز في اللعب الموضعي يُقوَّض أحيانًا بضعف أدائه في نهاية اللعبة. تتطلب نهاية اللعبة نهجًا تحليليًا أكثر دقة، وأحيانًا استشرافًا معمقًا للمستقبل. وقد حدَّ اقتصار استشراف TD-Gammon على خطوتين فقط من إمكانياته في هذا الجزء من اللعبة. كانت نقاط قوة وضعف TD-Gammon معاكسة لبرامج الذكاء الاصطناعي الرمزي ومعظم برامج الحاسوب عمومًا: فقد كان بارعًا في الأمور التي تتطلب حدسًا فطريًا، لكنه ضعيف في التحليل المنهجي.

كما أنه ضعيف في استراتيجيات المضاعفة. ويرجع ذلك على الأرجح إلى أن الشبكة العصبية تُدرَّب دون استخدام مكعب المضاعفة، حيث تُضاف المضاعفة عن طريق إدخال تقديرات الأسهم غير المكعبة للشبكة العصبية في صيغ استدلالية قائمة على أسس نظرية. وقد تجلى ذلك بوضوح في المباراة الاستعراضية عام 1998، حيث خاضت 100 جولة ضد مالكولم ديفيس. وتسبب خطأ واحد في المضاعفة في خسارة المباراة. ^{[ 5 ]}

لم يتم تسويق برنامج TD-gammon أو إصداره للجمهور بأي شكل آخر، ولكنه ألهم برامج الطاولة التجارية القائمة على الشبكات العصبية، مثل JellyFish (1994) و Snowie (1998). ^{[ 10 ]}

• الاتحاد العالمي للطاولة

• ساتون، ريتشارد س.؛ بارتو، أندرو ج. (2018). "11.1 TD-Gammon" . التعلم المعزز: مقدمة (  الطبعة الثانية). كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا.

• تي دي غامون في شركة آي بي إم
• TD-Gammon على GitHub
• TD-Gammon ، مسودة من جيرالد تيسورو على موقع Scholarpedia .