Jarní soustředění KSP 2012

Šestvorková aréna

Na tomto místě existovalo rozhraní pro vkládání vašich řešení šestvorkové seriálové úlohy první série.

Vyhodnocení

Jak psát algoritmus?

Chceme od vás dvě funkce: jedna z dané situace nageneruje tahy, které chcete, aby minimax dále zkoumal, druhá bude přiřazovat situaci číselné ohodnocení. Tyto funkce zasadíme do programu, který budeme spouštět interpretem Pythonu 3 – chcete-li mít šanci na úspěch, je tedy vhodné, abyste své algoritmy vyjádřili v Pythonu 3. ☺

Syntaxe Pythonu 3 je velmi podobná Pythonu 2, nicméně nějaké drobné změny tam jistě potkáte. Rozumný přehled můžete získat v dokumentu What's new in Python 3.0 (bohužel jen v angličtině; kdybyste věděli o něčem použitelném v češtině, dejte prosím vědět).

Hlavičky musí být v následujícím tvaru: 

def Generuj(Situace) :
   ...

def Ohodnot(Situace) :
   ...

Název argumentu si samozřejmě upravit můžete. Co je zcela jistě zakázáno (a co pokud projde automatikou, bude odstraněno dohlížejícím správcem) je snažit se uchovávat data, která by přežívala běh funkce. Nějaké pomocné funkce si vedle dvou hlavních dodefinovat můžete.

Také je samozřejmě zakázáno snažit se pípat na systémovém reproduktoru, otevírat síťový socket, spouštět z funkce hru Nethack apod., ale to je vám už dávno jasné.

V argumentu Situace najdete dvojrozměrný seznam 15x15 (seznam patnácti seznamů délky patnáct), jehož prvky obsahují právě číselné hodnoty 0, 1, 2; kde 0 značí prázdné pole, 1 pole, kam zahrál protihráč a 2 pole, kde jsou značky vaše.

Funkce Generuj musí vrátit seznam dvojic souřadnic piškvorek (přičemž souřadnice je opět dvojice celých čísel), na které chcete dál spustit prohledávání. Příklad funkce, která chce prohledat všechno (což není úplně dobrý nápad): 

def Generuj(Situace) :
	volne = []

	for radek in range(15) :
		for sloupec in range(15) :
			if Situace[radek][sloupec] == 0 :
				volne.append((radek, sloupec))
	# Dvojice zavorek na predchozim radku je spravne,
	# nebot syntaxe (a, b) v Pythonu definuje dvojici.

	dvojice = []

	for i in range(len(volne)) :
		for j in range(i+1, len(volne)) :
			dvojice.append((volne[i], volne[j]))

	# Vracime tedy seznam dvojic dvojic celych cisel 0..14.
	return dvojice

(Proč pokaždé dvojici tahů, když úplně první tah je pouze jeden? První tah začínajícího hráče sudí umístí doprostřed desky sám, bez zkoumání prázdné desky minimaxem.)

Pokud funkce nahlásí k prozkoumávání pozici, která už je obsazená či neexistuje, hru prohráváte – stejně tak, pokud vrátí data v nesprávném tvaru, či jakkoliv havaruje.

Formulář, který předkládáme výše, kód nijak nekontroluje, pouze ho uloží pro pozdější, noční zpracování na úplně jiném počítači. Chcete-li si před odesláním správnost ověřit a nemáte po ruce interpret Pythonu, zkuste si pohrát s připraveným zdrojovým kódem na Ideone.

Funkce Ohodnot musí vrátit jediné celé číslo, které bude vyjadřovat kvalitu pozice – vyšší hodnota je lepší.

Jak bude vypadat vyhodnocování?

Vaše funkce budou zapojeny do minimaxového algoritmu, který se bude zkoušet propočítávat s větší a větší hloubkou, dokud mu nedojde přidělený čas. Potom vezme nejlepší tah z běhu s největší hloubkou prohledávání, který se dopočítal a zahraje ho.

Doba běhu minimaxu bude v řádu sekund a bude-li hra trvat mnoho tahů, zkrátí se. Informaci o tom, jak hluboko se váš program dopočítal a jak moc se větvil, dostanete s výsledky utkání.