RedBot 2014 jaro: Jak se hrálo

Od autorů výherních strategií jsme dostaly popisy toho jak se jednotlivé strategie praly o vítězství - nechejte se inspirovat. V závěru článku také najdete přehled použitých programovacích jazyků. Tentokrát neodevzdal v Haskellu nikdo.

Strategie nejlepších strategií

Strategie LEM (Pavel Grunt)

Strategie je spíše defensivní, snaží se stlačit ceny na takovou úroveň, aby soupeř prodělával více. Jádrem je evoluční algoritmus LEM, který hledá nejlepší nastavení cen, cílem je maximalizovat rozdíl zisku obou hráčů. Nejdříve takto odhadne, jak by ceny nastavil soupeř, potom zjistí nejlepší ceny pro sebe. Nový obchod staví pouze pokud nemá žádný, nebo pokud má soupeř větší zisk a má alespoň o dva více obchodů.

Strategie Wallsmart (Michal Bilanský, Jan Bílek, Miloš Chromý)

Obchody stavíme jenom když jich nemáme příliš mnoho a když na to máme dost peněz: (penize >= 250 + 600*pocetObchodu^2). Ceny obchodů udržujeme v intervalu (1.13, 5), nižší cena by jistě byla prodělečná, 5 je optimum, vyšší než 5 se určitě nikdy nevyplatí, to plyne z analýzy funkce zisku: (zisk(cena)=cena-1-cena^2/10).

  1. Nejdříve si zjistíme, které obchody jsme v minulém kole chtěli postavit a nepovedlo se, protože soupeř chtěl stavět na stejném místě. Pro každý takový obchod náhodně zvolíme jiné volné místo v bezprostředním okolí a postavíme tam.
  2. Pokud nemáme žádné resty z minulého kola, tak se podíváme, zda chceme expandovat. Expandujeme pokud: (máme vyšší zisky, než je nájemné) && (máme méně nebo zhruba stejně peněz jako soupeř || soupeř má zisky > 100). Expandování probíhá tak, že všechna volná políčka do vzdálenosti 40 od měst ohodnotíme jejich "lidnatostí". čemž dáváme pozor, abychom nestavěli příliš blízko sebe. Na lidnatých mapách (náš zisk > 100) dovolíme minimální rozestup mezi obchody 3, na řídkých mapách 9. V případě, že by počet měst byl větší, než 3000, pak by algoritmus na hledání nejvýhodnějších políček nedoběhl ve stanoveném limitu, takže byla připravena jednodušší varianta stavění přímo do nejlidnatějších měst.
  3. Konkurence soupeři probíhá jenom v případě, že soupeř má větší zisk než my. Podíváme se na všechny soupeřovy výdělečné obchody a zjistíme, jestli v okolí také nemáme obchod. Pokud nemáme, tak postavíme u nedalekého města. Pokud máme, tak upravíme cenu obchodu směrem k soupeřově ceně (o trochu výhodnější než má soupeř).
  4. U nových obchodů nebo u obchodů, kde neproběhl konkurenční boj, zkusíme náhodně změnit cenu. Pokud je to nový obchod, tak se necháme inspirovat okolními obchody (pokud nějaké jsou), nebo nastavíme cenu kolem 3. Pokud vyděláváme, tak změníme pouze s malou pravděpodobností, pokud proděláváme, tak zvolíme cenu uniformně náhodně v rozmezí (1.6, 3).

Obecně jsme počítali s většíma mapama, tak jsme optimalizovali spíše na ně. Náš hlavní problém na mapě 5 bylo asi to, že jsme se hned na začátku snažili postavit 2 obchody, a jelikož jsme měli k dispozici pouze 500 eur a na mapě byla pouze 4 města, byla velká pravděpodobnost, že se soupeřem budeme chtít stavět na stejném místě, a tak s nulovým počtem peněz dojde k remíze.

Strategie matiniero (Stefan Hasko)

Priradzujem polickam vahy podla poctu obyvatelov v okolitych mestach, z ktorych nasledne vyberiem policko s najvacsou hodnotou. Predchadzajuci algoritmus neaplikujem na celu mapu, kedze funkcia vahy klesa velmi rychlo, algoritmus aplikujem na okna velkosti 5x5 skrz celu mapu, s tym ze uvazujem maximalne 1 obchod v kazdom takomto okne. V kazdom okne vyberiem najlepsieho kandidata na obchod a zo vsetkych okien vyberiem toho najlepsieho, kde postavim novy obchod a cenu prisposobim podla vahy tak, aby obchod zarobil na najomne.

Okrem toho ceny znizujem kazdych 250 kol, takze sa menia 4 krat pocas jednej hry.

V pripade ze som v minuse, zavriem obchod s najnizsim ziskom. Minimalna a maximalna cena je prisposobena funkcii zisku. Kedze to je symetricka parabola ktorej funkcna hodnota rastie na intervale <0,5> a na intervale <5,10> klesa, nema zmysel uvazovat druhy interval, takze maximalna cena je 5. Minimalna cena je priesecnik paraboly s osou x (5-sqrt(15)), kde je zisk rovny nule, nizsia cena nema zmysel lebo vedie k strate.

Strategie BSOD (Jan Horacek, Adam Kovář, Filip Široký)

Strategie postaví obchody jednorázově na začátku hry a pak v nich průběžně nastavuje ceny. Vždy se snaží umístit obchod do hlavního města a několik dalších obchodů podle výsledku heuristiky, kterou provede nad mapou. V dalších kolech probíhá občasné přidání obchodu (pravděpodobnost 0.5 % pro každé kolo), ale hlavně nastavování cen v již existujících obchodech. To zabezpečuje algoritmus, který se pokusí odhadnout cenu v mém obchodě z cen v okolních obchodech. Tuto cenu následně zkoriguje tak, aby nasadil mírně nižší cenu, než je cena v obchodech okolních a tím zajistil vyšší výdělek.

Jazyky strategií

jazykpočet strategiířádků kódu
C++43570
C2696
Java21344
C#1184
Pascal1472
Python1563
116829