SCOUT

SCOUT jest algorytmem podejmowania decyzji w grach dwuosobowych.

Opis algorytmu

SCOUT opiera się na dwóch rekurencyjnych funkcjach: TEST oraz EVAL. Funkcja EVAL(S) zwraca wartość $V(S)$ wierzchołka $S$ opisującego stan gry. TEST(S, v, r) sprawdza czy zachodzi relacja $r\left(V(S),v\right).$

Funkcja TEST przyjmuje trzy argumenty: wierzchołek $S,$ wartość $v$ oraz relację $r\in \{>,\geqslant \}.$ Jeśli $S$ jest wierzchołkiem typu MAX funkcja zwraca true jeśli istnieje potomek $S,$ który jest większy (większy lub równy) niż $v.$ Jeśli $S$ jest wierzchołkiem MIN funkcja zwraca false jeśli istnieje potomek $S,$ który jest mniejszy (mniejszy lub równy) niż $v.$

Niech $S$ będzie wierzchołkiem typu MAX opisującym stan gry, a $S_{i}$ to jego bezpośredni potomkowie. Funkcja EVAL zwraca wartość wierzchołka $S$ poprzez rekurencyjne wywołanie siebie dla pierwszego potomka $S_{1},$ a następnie sprawdzenie przy pomocy metody TEST czy dla każdego z pozostałych potomków $S_{i}$ zachodzi $V(S_{i})>V(S_{1}).$ Jeśli dla wierzchołka $S_{k}$ nierówność nie zachodzi, poprzez wywołanie EVAL wyznaczana jest jego wartość i jest ona używana w miejsce $V(S_{1})$ do sprawdzenia czy powyższa nierówność zachodzi dla pozostałych potomków $S.$ Gdy wszystkie wierzchołki $S_{i}$ zostaną sprawdzone funkcja EVAL zwraca jako $V(S)$ ostatnią wartość $V(S_{k}).$

Funkcja EVAL wywołana dla wierzchołka typu MIN zachowuje się analogicznie, z tą różnicą, że zamiast nierówności ostrej sprawdzana jest nierówność nieostra.

Pseudokod

def scout(state):
	eval(state)

def eval(state):
	if state.is_terminal():
		return state.value()
	value = None
	if state.is_max():
		for child in state.children():
			if value is None or test(child, value, >):
				value = eval(child)
	else: # state.is_min()
		for child in state.children():
			if value is None or not test(child, value, >=):
				value = eval(child)
	return value

def test(state, value, rel):
	if state.is_terminal():
		return rel(state.value(), value)
	if state.is_max():
		for child in state.children():
			if test(child, value, rel):
				return True
		return False
	else: # state.is_min()
		for child in state.children():
			if not test(child, value, rel):
				return False
		return True