MIMIMIMINER APPTH First Search Game Tree

Question

أريد بناء شجرة لعبة لتسع لعبة Morris للرجال. أريد تطبيق خوارزمية الحد الأدنى على الشجرة لإجراء تقييمات العقدة. يستخدم Minimax DFS لتقييم العقد. لذا ، هل يجب أن أقوم ببناء الشجرة أولاً حتى عمق معين ثم تطبيق الحد الأدنى أو هل يمكن لعملية بناء الشجرة والتقييم أن تحدث معًا في الحد الأدنى العودية DFS؟

شكرا لك آرفيند

Answer 1

يمكنك إلقاء نظرة على عمق التكرار عمق البحث الأول.

Answer 2

نعم يمكنك بناء وتقييم في نفس الوقت في الحد الأدنى العودية.
هذا نهج جيد لأنه سيوفر مساحة الذاكرة.

في الواقع ، يمكنك حتى التقديم ألفا بيتا التقليم في نفس الوقت.

تعديل: هنا رمز كاذب من ويكي الحد الأدنى:

function integer minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    for child in node: # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

نظرًا لأننا (ربما) نقوم بتخزين دولة لعبة / لوح في كل عقدة ، يمكننا تضمين إنشاء حالات اللعبة
في خوارزمية الحد الأدنى ، أي

function integer play_minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    LOOP: # try all possible movements for this node/game state
        player = depth mod 2
        move = make_game_move(node, player)
        break if not any move
        α = max(α, -play_minimax(move, depth-1))
    return α