0

これらの機能をどのように結びつければ、負けることのないハード AI になるかわかりません。なんらかの形またはファジョンで再帰を使用することになっており、これらの関数名とコントラクトは事前に作成されており、実際の定義に記入しました。後でグーグルで検索しても、関連するものは何も見つかりません。何かアイデアはありますか？

"""


State S2 is a *successor* of state S1 if S2 can be the the
next state after S1 in a legal game of tic tac toe.

safe: state -> Bool
successor: state x state -> Bool

1. If S is over, then S is safe if 'x' does not have 3 in a row in S.
2. If it is o's move in S, then S is safe iff at least one successor of S is safe.
3. If it is x's move in S, then S is safe iff all successors of S are safe.

A *stateList* is a list of states. 
"""


# safe: state-> Bool
#
# A state S is *safe* if player 'o' can force a win or tie from S.

def safe(S):
    if over(S): return not threeInRow('x',S)
    if turn(S)=='o': return someSafeSuccessor(S)
    if turn(S)=='x': return allSafeSuccessors(S)

def threeInRow(p,S):
    if p == 'x':
        if all(t in S[0] for t in (1,2,3)):
            return True
        elif all(t in S[0] for t in (4,5,6)):
            return True
        elif all(t in S[0] for t in (7,8,9)):
            return True
        elif all(t in S[0] for t in (1,4,7)):
            return True
        elif all(t in S[0] for t in (2,5,8)):
            return True
        elif all(t in S[0] for t in (3,6,9)):
            return True
        elif all(t in S[0] for t in (1,5,9)):
            return True
        elif all(t in S[0] for t in (3,5,7)):
            return True
    else:
        if all(t in S[1] for t in (1,2,3)):
            return True
        elif all(t in S[1] for t in (4,5,6)):
            return True
        elif all(t in S[1] for t in (7,8,9)):
            return True
        elif all(t in S[1] for t in (1,4,7)):
            return True
        elif all(t in S[1] for t in (2,5,8)):
            return True
        elif all(t in S[1] for t in (3,6,9)):
            return True
        elif all(t in S[1] for t in (1,5,9)):
            return True
        elif all(t in S[1] for t in (3,5,7)):
            return True

# someSafeSuccessor: state -> Bool
#
# If S is a state, someSafeSuccessor(S) means that S has
# at least one safe successor.

def someSafeSuccessor(S):
    flag = False
    # flag means we have found a safe successor
    for x in successors(S):
        if safe(x): flag = True
    return flag

# allSafeSuccessors: state -> Bool
#
# If S is a state, allSafeSuccessors(S) means that every
# successor of S is safe.
def allSafeSuccessors(S):
  flag = True
  for x in successors(S):
    if not safe(x): flag = False
  return flag    


# successors: state -> stateList
#
# successors(S) is a list whose members are all of the successors of S.
def successors(S):
  stateList=[]
  for i in range(1,10):
    if empty(i,S):
      stateList.extend(S[0],S[1]+[i])
  return stateList
4

1 に答える 1

2

私のコメントのフォローアップ。

ミニマックス (/alpha-beta pruning) アルゴリズムを記述するときに視覚化されるツリーは、ツリー全体をメモリ内に構築するという意味で「実際のツリー」ではありません。これは概念的なツリーであり、最初にすべての移動深度をテストし、各リーフ (アルファ、ベータなど) でスコアを記録し、それらを伝播した結果です。

深さ優先という言葉に注意してください。これは、再帰的なミニマックス実装関数が、最初に実行できる移動で自分自身を呼び出すことから始まることを意味します。これは、それが行うことができる最初の動きで自分自身を呼び出すことから始まります. というように、最大​​の深さに到達するか、最終的な動きに到達するまで、戻ってきます。このロジックから、現在検討されている 1 つの一連の動き以外に、メモリや外部ストレージにボードが増えることはないことがわかります (そして、各レベルで、可能な動きのリストを反復処理します)。それ-つまり、あなたがどれだけ離れているかなどの記憶もあります）。

tl;dr 深さ優先のミニマックス再帰を実行すると、単一の再帰関数以外の新しい関数は作成されません。

于 2013-04-18T05:26:00.967 に答える