كتابة محرك شطرنج بسيط في Go

مخصص لكل من يشاهد الآن المسلسل التلفزيوني الشهير "The Queen's Gambit". المزيد من مصطلحات الشطرنج في ترجمتنا الجديدة.

في هذه المقالة ، سنحاول فهم كيفية عمل محركات الشطرنج عن طريق نقل محرك شطرنج السمكة إلى Go. تتميز Sunfish ببساطتها وصغر حجمها ، لكنها لا تزال قادرة على لعب لعبة شطرنج جيدة. من ناحية أخرى ، تُعرف Go بأنها لغة برمجة بسيطة وقابلة للقراءة ، لذلك آمل أن يصنعوا معًا زوجًا رائعًا.



لإنشاء محرك شطرنج ، عليك أولاً تحديد ثلاث نقاط مهمة:

• كيف تمثل رقعة الشطرنج (الخلايا ، القطع ، الحركات المسموح بها)؟
• كيف تقيم اللوحة (من المرجح أن يفوز)؟
• كيف تجد الحركة المثالية؟

تم تبسيط مقتطفات التعليمات البرمجية في هذا المنشور وتحتوي فقط على الأجزاء الأكثر أهمية. يمكنك العثور على رمز محرك الكامل في github.com/zserge/carnatus (carnatus هو الاسم اللاتيني لباس البحر، والأنواع carnatus Sebastes).

الخلايا والأشكال

من المهم العثور على تمثيل مناسب للوحة لا يشغل مساحة كبيرة ، حيث سيتم تخزين آلاف الأشكال المختلفة للوحة في الذاكرة أثناء البحث عن الحركة المثلى.



عادة ما تكون اللوحة عبارة عن مجموعة من الخلايا. سنضيف حشوة حول اللوحة القياسية 8x8 بحيث تقع تحركات القطع غير الصالحة في هذه المنطقة. سيسمح لنا ذلك بتجنب فحص الحدود وتبسيط الشفرة بشكل كبير.



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



وبالتالي ، نحتاج إلى مساحة من خليتين على طول حواف اللوحة. يمكننا إنشاء لوحة بحجم 12 × 12 ، ولكن نظرًا لأننا نمثلها كمصفوفة خطية ، فنحن بحاجة إلى لوحة مقاس 12 × 10 لأنه يمكن استخدام مربع المسافة البادئة في أقصى اليمين في السطر السابق كمربع مسافة بادئة في أقصى اليسار في السطر التالي (× = مسافة بادئة):

××××××××××
××××××××××
×........×
×........×
×........×
×........×
×........×
×........×
×........×
×........×
××××××××××
××××××××××
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

في تدويننا ، سيبدو "a1" مثل 9 × 10 + 1 = 91 ، وسيبدو "a8" مثل "2 × 10 + 1" = 21. تمثل



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

          |
          |
 RNBQKBNR |
 PPPPPPPP |
 ........ |
 ........ |
 ........ | <-     
 ........ |
 ........ |
 ........ |
 pppppppp |
 rnbkqbnr |
          |
          |
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

أخيرًا ، يمكننا البدء في كتابة الكود:

type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }

type Board [120]piece
func (b Board) Flip() Board { ... }

type Square int
func (s Square) Flip() Square { ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

الأشكال لها قيمة معينة. هذه القيم مطلوبة لتقييم المواقف على السبورة وفهم من هو الفائز. عادة ما يكون البيدق = 100 ، والفارس = 280 ، والأسقف = 320 ، والغراب = 479 ، والملكة = 929 ، والملك ذو قيمة كبيرة لدرجة أنه يتفوق على 8 ملكات (بيادق تحولت إلى ملكات) جنبًا إلى جنب مع أزواج من الفرسان والأساقفة والغربان. إذا كانت لدينا كل هذه الثروة ، لكننا فقدنا الملك ، فسيظل العد يظهر أننا سنخسر.



كل نوع له طريقة Flip () تُرجع نفس القيمة بعد قلب اللوحة قبل أن يتحرك الخصم. بالنسبة للأشكال ، فإنه يغير حالة رمز الشكل. في المربعات ، أعاد 119 مربعًا (العد من الطرف الآخر للوحة). أما بالنسبة للوحة ، فقد قام بنسخ جميع القطع من المربعات بترتيب عكسي ، وتغيير حالتها.

مولد السكتة الدماغية

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



ما هي الحركة؟ هذا هو مزيج من خليتين - الخلية حيث كانت القطعة قبل النقل ، والخلية حيث تحركت القطعة. المركز عبارة عن رقعة شطرنج بها نقاط وقواعد التبييت لكل لاعب ومربعات مرور / تجول. كلا النوعين لهما أيضًا طريقة Flip () لتحركات الخصم.

type Move struct {
  from Square
  to   Square
}
func (m Move) Flip() Move { ... }

type Position struct {
  board Board   //  
  score int     //    —   ,  
  wc    [2]bool //    
  bc    [2]bool //    
  ep    Square  //  ,       
  kp    Square  //    ,     
}
func (p Position) Flip() Position { ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

الآن يمكننا كتابة أول طريقة كبيرة - مولد الحركات المسموح به. نحن نهتم فقط بالقطع البيضاء ، لأننا نلعب باللون الأسود سنقلب اللوحة وننتقل إلى اللون الأبيض مرة أخرى.



لإنشاء جميع الحركات الصحيحة ، نحتاج إلى:

• قم بعمل قائمة بجميع التحركات ذات الخطوة الواحدة في كل اتجاه لكل قطعة ؛
• افعل الشيء نفسه مع جميع الخلايا ، مع تجاهل القطع غير البيضاء ؛
• حدد حركة في كل اتجاه ممكن لكل قطعة بيضاء ؛
• إذا لم يكن طول حركة القطعة محدودًا (رخ ، أسقف ، ملكة) ، استمر في تحريكها حتى تواجه عقبة في الطريق: قطعة الخصم أو المسافة البادئة خلف حافة اللوحة.

هذا رمز مبسط لا يأخذ في الاعتبار الالتقاط والتبييت. يمكنك العثور على التطبيق الكامل على Github ، فهو لا يختلف كثيرًا.



لجعل حساب الاتجاه أكثر قابلية للقراءة ، سنستخدم ثوابت الاتجاه N / E / S / W:

const N, E, S, W = -10, 1, 10, -1

var directions = map[Piece][]Square{
  'P': {N, N + N, N + W, N + E},
  'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
  'B': {N + E, S + E, S + W, N + W},
  'R': {N, E, S, W},
  'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
  'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}

func (pos Position) Moves() (moves []Move) {
  for index, p := range pos.board {
    if !p.ours() {
      continue
    }
    i := Square(index)
    for _, d := range directions[p] {
      for j := i + d; ; j = j + d {
        q := pos.board[j]
        if q == ' ' || (q != '.' && q.ours()) {
          break
        }
        if p == 'P' {
          if (d == N || d == N+N) && q != '.' {
            break
          }
          if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
            break
          }
        }
        moves = append(moves, Move{from: i, to: j})
        if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
          break
        }
      }
    }
  }
  return moves
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

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

func (pos Position) Move(m Move) (np Position) {
  np = pos
  np.board[m.to] = pos.board[m.from]
  np.board[m.from] = '.'
  return np.Flip()
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

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



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



لكن كيف نفهم أننا نخسر؟

تصنيف المجلس

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



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



طريقة أكثر دقة وبسيطة بشكل مدهش هي جداول نسبة الشكل إلى المربع ( PST- طاولات مربعة الشكل). لكل قطعة ، يتم إنشاء جدول بنفس حجم رقعة الشطرنج ، حيث يتم تعيين قيمة مقابلة لكل مربع. هذه القيم تجريبية ، لذا أخذتها للتو من محرك Sunfish.



في الواقع ، تقوم محركات الشطرنج الأكثر تقدمًا بتحديث PSTs أثناء اللعبة لأن قيمة القطع تتغير (أي تصبح البيادق أكثر قيمة في نهاية اللعبة). لكن سيكون لدينا محرك بسيط.



لتقييم المركز بعد الانتقال ، نحتاج إلى:

• تحديد تصنيف الموقف الحالي ،
• اطرح قيمة القطعة التي يتم تحريكها ،
• إضافة قيمة شخصية جديدة وفقًا لجدول PTS ،
• أضف قيمة القطعة الملتقطة ، إن وجدت.

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

var pst = map[Piece][120]int{
  'P': { ... },
  'N': { ... },
  'B': { ... },
  'R': { ... },
  'Q': { ... },
  'K': { .... },
}

func (pos Position) value(m Move) int {
  i, j := m.from, m.to
  p, q := Piece(pos.board[i]), Piece(pos.board[j])
  //      PST-
  score := pst[p][j] - pst[p][i]
  if q != '.' && q != ' ' && !q.ours() {
    //      PST-
    score += pst[q.Flip()][j.Flip()]
  }
  return score
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

الآن يمكننا صنع محرك أكثر تقدمًا بقليل والذي سيختار أفضل حركة ممكنة ، بدلاً من أي حركة صالحة.



لكن محركات الشطرنج الحقيقية تقوم بتحليلات أعمق وتكرر فروع التحركات المحتملة على كل جانب للعثور على أفضل حركة ممكنة على المدى الطويل.

خوارزمية البحث

تعد خوارزمية البحث الأكثر شيوعًا في محركات الشطرنج أبسط - البحث العميق أولاً ، والذي يبدأ من الجذر وينخفض ​​إلى حد عمق معين ، ويكرر جميع الحركات الممكنة قبل العودة. يتم حساب قيمة موضع كل ضربة باستخدام خوارزمية minimax (minimax) c alpha-beta pruning ( alpha-beta pruning ).



Minimax هي قاعدة تُستخدم لتقليل الخسائر المحتملة في أسوأ السيناريوهات: يأخذ اللاعب في الاعتبار جميع التحركات الأفضل للخصم ويختار حركة بحيث تجلب أفضل استراتيجية للخصم أكبر عدد ممكن من النقاط.



قد تكون خوارزمية minimax البسيطة بطيئة جدًا للشطرنج وستتطلب تكرار العديد من الحركات للعثور على واحدة جيدة.



يستخدم تقليم ألفا بيتا لتسريع خوارزمية الحد الأدنى من خلال إزالة العقد التي لا تستحق الدراسة. يعتمد اقتطاع Alpha-beta على المنطق التالي: تخيل أنك تلعب الشطرنج وتجد حركة جيدة جدًا أ. تستمر في النظر إلى اللوحة وتجد خطوة أفضل ب. ولكن بعد ذلك تقوم بتحليل الموقف بشكل أعمق وتفهم ذلك إذا اخترت في الخطوة B ، سيعلن العدو عن الشيك وكش ملك في بضع حركات. الآن سوف تتجاهل B ولن تضيع الوقت في تحليل التوليفات المحتملة الأخرى بعد B.



يعتبر كل من minimax و alpha-beta clipping مهمين في فهم كيفية عمل محرك الشطرنج. يستخدم محرك Sunfish خوارزمية بحث متقدمة MDF (f) ، والتي تعد أيضًا متغيرًا من خوارزمية minimax جنبًا إلى جنب مع القص.



في محركنا ، سنعمل تدريجياً على زيادة عمق البحث واستدعاء خوارزمية MDF (f) للعثور على الحدود الدنيا والعليا للنتيجة المثلى. ستستخدم خوارزمية MDF (f) تكرار قص ألفا بيتا مع ذاكرة تخزين مؤقت للتبديل.



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



لن أنشر رمز خوارزمية البحث هنا ، حيث إنها مجرد بضعة أسطر من البحث المتكرر ، ولكن يمكنك دائمًا العثور على كود المصدر الكامل لمحرك الشطرنج على GitHub .

ماذا بعد؟

إذا كنت مهتمًا بمحركات الشطرنج البسيطة ، فإنني أوصي بشدة باللعب مع Sunfish. بالمناسبة ، يعتمد Sunfish على محرك Micromax ويأتي مع بعض الوثائق الرائعة من المؤلف ، والتي تستحق القراءة بالتأكيد.







بالنسبة لمحركنا في Go ، أضفت تطبيقًا صغيرًا لبروتوكول UCI بحيث يمكن استخدامه مع واجهة مستخدم PyChess. على الأرجح ، لا يزال يحتوي على مجموعة من الأخطاء والكثير من إمكانات التحسين ، لكنه كان مسارًا مثيرًا للاهتمام: من فكرة تطوير محرك الشطرنج إلى برنامج شطرنج حاسوبي كامل وعامل.



نعم ، إنه ضعيف ، لكنه يلعب ألعاب شطرنج حقيقية!



آمل أن يحظى هذا المقال بإعجابكم. يمكنك متابعتي على جيثب ، تويتر أو الاشتراك عن طريق آر إس إس .