كيفية العودة إلى أفضل مستوى في هذه F# minimax?

Question

هذا السؤال هو أكثر الدلالي-حسابي-البيانات-هيكل السؤال من F# نحويا السؤال.لدي خوارزمية Minimax.خوارزمية minimax يجب أن تعود أفضل الخطوة التالية من بداية الموقف.للقيام بذلك ، حساب التفاضل والتكامل جميع التحركات المقبلة ، ثم التالي-التالي-يتحرك حتى تحديد العمق أو حتى لا يوجد المزيد من التحركات.فإنه يبني شجرة مثل هذا:

     P  
   /  \  
 a      b  
/ \  
c d

لدي إراحة بيانات البنية التعامل مع الشجرة:

type TreeOfPosition =
    | LeafP   of Position * int
    | BranchP of Position * TreeOfPosition list

في سبيل المثال شجرة أعلاه ، P و a هي الفروع ، b, c و d هل يورق.رمز أدناه هو خوارزمية minimax:

let evaluateTree ( tree : TreeOfPosition, player : int) =
    let rec loop minOrmax node =
        match node with
        | LeafP(position, 0) -> 
            LeafP(position, evaluateLeaf(position))
        | BranchP(position, children)  -> 
            minimax.[minOrmax](List.map (loop (1 - minOrmax)) children)
    loop player tree

هذا الرمز تعود لي ورقة ، على سبيل المثال ، c.عندما غيرت مكالمة العودية

| BranchP(position, children)  -> 
    LeafP(position, 
          getStaticEvalFromNode(minimax.[minOrmax](
                       List.map (loop (1 - minOrmax)) children)))

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

تحرير 1

شكرا لجميع إجابات الرجال أنها تساعد لي الكثير.آسف لم تحدد الأمور كثيرا.دعونا نذهب في أجزاء:

1) أنا مطابقة بلدي LeafP مثل LeafP(position, 0) لأن عند إنشاء شجرة بلدي أنا وضعت يورق مع قيمة افتراضية 0 كما لها قيمة ثابتة.كما انا ذاهب الى بلدي قيم ثابتة ، والقضاء على ورقة و جعل (قبل الفروع) يورق مع (الحد الأدنى أو الحد الأقصى) قيم ثابتة أعتقد أن هذه الطريقة سوف تمنع لتقييم السابقين فرع ورقة (لأنه لن يكون لها قيمة 0).

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

let evaluateTreeHOF ( tree, player : int) =
    let rec loop minOrmax node =
        match node with
        | LeafP(position, 0) -> LeafP(position, evaluateLeaf(position))
        | BranchP(position, children) -> LeafP(position,(children 
                                                         |> List.map (loop (1 - minOrmax)) 
                                                         |> minimax.[minOrmax] 
                                                         |> getStaticEvalFromNode))
    match tree with
    | BranchP(position, children) -> children |> List.map (loop (1 - player)) |> minimax.[player]

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

اعتقدت kvb إجابات مثيرة جدا للاهتمام ، لكن معقد قليلا بالنسبة لي.تلك الأخرى لا understudied ، لكنها فقط أعطني قيمة ثابتة – و أنا لا يمكن أن تجعل لهم العمل بالنسبة لي :(

شكرا جزيلا على كل الأجوبة ، كل منهم أوحت لي الكثير.

هنا هو بلدي كامل رمز:(http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)

بيدرو Dusso

Answer 1

أنا لا أفهم تماما بعض جوانب النموذج الخاص بك (على سبيل المثاللماذا المباراة الوحيد ضد يترك مع 0s؟), لذلك سأقوم ببعض التغييرات أدناه.أولا, دعونا نعمم نوع الشجرة قليلا ، بحيث يمكن تخزين أي نوع من أنواع البيانات في أوراق وفروع:

type Tree<'a,'b> = 
| Leaf of 'a 
| Branch of 'b * Tree<'a,'b> list

دعونا أيضا استخدام مخصصة نوع اللاعب بدلا من استخدام 0 أو 1:

type Player = Black | White

وأخيرا دعونا نعمم تقييم أفضل تتحرك قليلا ، بحيث ورقة مهمة التقييم مرت في حجة:

let bestMove evalPos player tree =
  // these replace your minimax function array
  let agg1,agg2,aggBy = 
    match player with
    | Black -> List.min, List.max, List.maxBy
    | White -> List.max, List.min, List.minBy

  // given a tree, this evaluates the score for that tree
  let rec score agg1 agg2 = function
  | Leaf(p) -> evalPos p
  | Branch(_,l) -> agg1 (List.map (score agg2 agg1) l)

  // now we use just need to pick the branch with the highest score
  // (or lowest, depending on the player)
  match tree with
  | Leaf(_) -> failwith "Cannot make any moves from a Leaf!"
  | Branch(_,l) -> aggBy (score agg1 agg2) l 

Answer 2

أعتقد يمكنك استخدام متبادل وظائف العودية:

let maxTree t = 
  match t with
  | child -> xxx
  | subtrees s ->
      s |> Seq.map minTree |> Seq.max

and minTree t = 
  match t with
  | child -> xxx
  | subtrees s ->
      s |> Seq.map maxTree |> Seq.min

Answer 3

الحل لهذه المشكلة هو موضح في F#.NET مقال في مجلة برمجة الألعاب:تيك تاك تو (31 كانون الأول / ديسمبر 2009) و يستخدم النمط التالي:

type t = Leaf | Branch of t seq

let aux k = function
  | Leaf -> []
  | Branch s -> k s

let rec maxTree t = aux (Seq.map minTree >> Seq.max) t
and minTree t = aux (Seq.map maxTree >> Seq.min) t

انظر أيضا لعب تجريبي.