Iti0210lab63

Otsing mängupuul

Sissejuhatus

"Connect Four" on mäng, kus mängijad kordamööda 7x6 raami mängunuppe kukutavad ja proovivad esimesena 4 oma nuppu saada ritta horisontaalis, vertikaalis või diagonaalile. Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Kasutame mängu mängimiseks Monte Carlo meetodit.

Kasutajaliides

Kasutajaliides võib olla nii tekstipõhine kui graafiline. Mängimine võiks tekstipõhise liidesega välja näha umbes nii:

...

|       |
|       |
|       |
|       |
|   O   |
| OXXXO |
|0123456|
To move: X
Your move? 2

|       |
|       |
|       |
|  O    |
|  XO   |
| OXXXO |
|0123456|
To move: X
Your move?

Programm näitab mänguseisu, küsib käiku, seejärel teeb oma käigu ja näitab jälle mänguseisu. See tsükkel kordub, kuni mäng läbi saab.

Näites on võimalikud käigud (kuhu oma nupp kukutada) nummerdatud 0-6.

Mängimine puhta Monte Carlo meetodiga

Puhas Monte Carlo meetod teeb lihtsalt mingi arvu (N iga käigu kohta) juhuslikke mänge ja valib käigu, millega kõige rohkem võite saavutati.

def pure_mc(pos, N=200):
    # kõik käigud algseisus
    my_side = pos["to_move"]
    initial_moves = moves(pos)
    # loendurid iga käigu jaoks
    win_counts = dict((move, 0) for move in initial_moves)

    for move in initial_moves:
        for i in range(N):
            # mängi juhuslikult seis kuni lõpuni
            res = simulate(pos, move, my_side)
            if res == WIN:
                win_counts[move] += 1
            elif res == DRAW:
                win_counts[move] += 0.5

    # leia suurima võitude arvuga käik, tagasta

    # ...

Funktsioon tekstipõhise liidesega mängimiseks:

def play_game(pos, player_side = "X"):
    playing = True
    while playing:
        if pos["to_move"] == player_side:
            # prindi info seisu kohta
            dump_pos(pos)
            movestr = input("Your move? ")
            # tõlgi kasutaja tekst oma sisemisse käiguformaati (kui vaja)
            move = parse_move(movestr)
        else:
            move = pure_mc(pos)

        pos = make_move(pos, move)
        # kontrolli kas mäng sai läbi
        if is_over(pos):
            playing = False

Ja testime:

play_game(starting_pos)

Toodud kooditükid on näide, ehk siis võib kasutada ka teistsuguseid lahendusi. Kui antud näidet kasutada, tuleb realiseerida kõik puuduolevad funktsioonid: moves(), make_move(), simulate(), dump_pos(), parse_move(), is_over().

Vajalikud asjad

Mänguseisu sisemine esitus

Lähtu sellest, et oleks võimalikult lihtne käike leida ja seda kontrollida, kas 4 nuppu on ritta saadud.

Käikude ja seisude genereerimine

Leia käigule mingi sisemine esitus (kasvõi number 0-6) ja tee funktsioon, mis igast seisust legaalsed käigud genereerib. Teiseks on vaja funktsiooni, mis võtab seisu ja käigu ning annab uue seisu.

Simulatsioon

Simulatsioon peab tegema järjest juhuslikke käike, kuni mäng on lõppenud ning tagastama, kas tulemus oli võit, viik või kaotus. Viikide eraldi arvestamine on vajalik selleks, et programm üritaks vältida kaotust ka olukordades, kus ta võitu ei näe.

Nõuded

• programm peab kasutama juhuslikul simulatsioonil põhinevat (Monte Carlo) algoritmi. Ei tohi olla minimax vms
• lisaks koodile pane reposse ka näide (tekstifail sobib), kus mingi seisu puhul võimalikud käikud ja nende võiduprotsendid

Lisaülesanne

Ei ole kohustuslik ja ei anna lisapunkte.

Uuri, kuidas töötab UCT versioon Monte Carlo puuotsingust ja proovi see realiseerida.

poster