Hromádky

Hra pro dva hráče s jednoduchými pravidly.

Na stole před oběma hráči je několik hromádek kamínků. Hráči se střídají v tazích. V každém tahu smí hráč odebrat několik kamenů (vždy alespoň jeden; maximální počet není určen) z některé hromádky (vždy pouze z jedné). Hráč, který odebere poslední kámen prohrává.

Počet hromádek není pevně dán, ani počet kamínků v jednotlivých hromádkách; velikost hromádek může být různá. Nelze se zdržet tahu (tedy neodebrat žádný kamínek). Nelze odebrat kamínky z několika hromádek najednou.

Vaším úkolem je naprogramovat strategii hráče, tedy algoritmus, který na základě informace o aktuálním počtu kamínků v jednotlivých hromádkách rozhodne, kolik kamínků ze které hromádky chce odebrat.

V modulu player.py vytvořte funkci play(), jejíž kostra může vypadat třeba takto:

def play(heaps):
    selected_heap = 0
    number_of_stones = 1
    return selected_heap, number_of_stones

Tento hráč hraje stále stejný tah, tedy “z první hromádky (z hromádky č. 0) odeber 1 kámen”. Tato strategie samozřejmě není optimální, a navíc se tento tah nejspíš brzy stane nevalidním. Vaším úkolem je vymyslet a implementovat chytřejší strategii a samozřejmě hrát pouze přípustné tahy.

Popis vstupů a výstupů této funkce:

Vrátí-li funkce např. dvojici (0, 1), znamená to, že si přejete odebrat 1 kamínek z první hromádky (z hromádky s indexem 0). Vrátí-li funkce např. dvojici (3, 5), znamená to, že si přejete odebrat 5 kamínků ze čtvrté hromádky (hromádky s indexem 3).

Vrácený tah musí být validní, tj.

• index hromádky musí být v rozmezí 0 až len(heaps)-1 (počet hromádek minus 1) a
• počet kamínků odebíraných z dané hromádky musí být alespoň 1, ale nesmí být vyšší než je aktuální počet kamínků ve zvolené hromádce.

Pokud tedy vaše funkce dostane aktuální stav hry popsaný seznamem [3, 0], pak nevalidní tahy jsou např.

• (2, 1), protože hromádky jsou jen dvě a tento tah vyžaduje odebrání 1 kamene ze třetí hromádky,
• (1, 1), protože ze druhé hromádky nelze odebrat žádný kámen,
• (0, 0), protože musíte odebrat alespoň jeden kámen,
• (0, 5), protože z první hromádky nelze odebrat 5 kamenů, když tam jsou jen 3 apod.

Odevzdejte soubor player.py nebo ZIP archív obsahující tento soubor spolu s dalšími moduly, pokud nemáte vše v jednom Pythonovském modulu.

Hodnocení bude probíhat na základě her s různě obtížnými protihráči. Každá hra se hraje 2x, jednou začíná hráč 1, podruhé hráč 2.

1. Pokud váš hráč alespoň jednou vrátí nevalidní tah (tedy dvojici čísel s tahem, který nelze provést), získáte 0 bodů.
2. Pokud váš hráč alespoň 1x prohraje s naší “nejhloupější” strategií, získáte 10% bodů.
3. Pokud bude úspěšnost vašeho hráče proti středně obtížné strategii >20% a proti obtížné strategii >10%, získáte 20% bodů.
4. Pokud bude úspěšnost vašeho hráče proti středně obtížné strategii >50% a proti obtížné strategii >30%, získáte 50% bodů.
5. Pokud bude úspěšnost vašeho hráče proti středně obtížné strategii >80% a proti obtížné strategii >40%, získáte 100% bodů.