Tekst źródłowy strony SCOUT

'''SCOUT''' jest [[algorytm]]em podejmowania decyzji w [[gra]]ch dwuosobowych<ref>J. Pearl: ''Scout: A simple game-searching algorithm with proven optimal properties'', 1980.</ref>.

== Opis algorytmu ==
SCOUT opiera się na dwóch [[rekurencja|rekurencyjnych]] [[Podprogram|funkcjach]]: ''TEST'' oraz ''EVAL''. Funkcja ''EVAL(S)'' zwraca wartość <math>V(S)</math> wierzchołka <math>S</math> opisującego stan gry. ''TEST(S, v, r)'' sprawdza czy zachodzi [[Relacja (matematyka)|relacja]] <math>r\left(V(S), v\right).</math>

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

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

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==
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== Przypisy ==
{{Przypisy}}

[[Kategoria:Algorytmy]]