-->

maandag 10 april 2017

4 op een rij (twee menselijke spelers)

Introductie

Een AI-agent is een combinatie van algoritmen dat er voor zorgt dat de best mogelijk beslissing wordt genomen gegeven bepaalde onzekerheid in de omgeving waarin de agent acteert.

Vier op een rij is een voorbeeld van het vinden van een oplossing in een adversarial-omgeving. M.a.w. een omgeving met een tegenspeler. Een veel gebruikt algoritme om in deze omgeving om de beste beslissing te nemen is het minmax-algoritme.

Uiteindelijk is het best een ingewikkeld programma om een goede 4 op een rij speler te programmeren. Daarom ga ik het programma stapsgewijs opzetten:

Stap 1. 4 op een rij met twee menselijke spelers. Dit lijkt mij de meest eenvoudige versie om te maken

Stap 2. 4 op een rij waarbij de gebruiker tegen een (zeer simpele) AI-agent speelt. De AI-agent weet enkel wat geldige zetten zijn (kies een kolom tussen 0 en 7 en die niet vol is). Als keuze voor de kolom gebruikt ie een randomize-functie.

Stap 3. 4 op een rij waarbij de gebruiker tegen een iets intelligentere agent speel. Deze agent kent ook de geldige zetten, maar kijkt ook naar de stand van het bord om zijn keuze te maken. Hierbij zijn twee varianten te maken. Een agent die alleen kijkt of hij bij de volgende stap 2,3, op 4 op een rij heeft of een agent die ook kijkt of hij kan voorkomen dat de gebruiker 4 op een rij krijgt.

Stap 4. De agent kijkt niet alleen naar geldige stappen en maakt een inschatting wat de beste volgende stap. Deze agent houdt bij zijn inschatting ook rekeing met 2 of meer toekomstige stappen van hem en zijn tegenstander.  Dit is in feite het minmax algoritme  in combinatie met een utitliteitsfunctie. Meestal worden deze agenten pas echt als enigzins intelligent gezien. Vooral als agenten meer dan twee of drie stappen vooruit kunnen redeneren. Stap 4 lijkt een recursieve versie van stap drie te zijn. 

Spelregels

  1. Vier op een rij wordt gespeeld op een (verticaal) bord van 8x6 vakken
  2. Er zijn twee spelers
  3. De spelers spelen om de beurt
  4. Een beurt bestaat uit het vullen van een vak met het symbool van de betreffende speler (rood, geel: hier kruisje, rondje)
  5. Een vak kan alleen gevuld worden als het op de bodem van het veld is of als het onderliggende vak gevuld is.
  6. Degene die als een eerste een reeks van vier dezelfde symbolen heeft horizontaal, verticaal of diagonaal, heeft gewonnen.

Stap 1: Java programma (twee menselijke spelers)


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication9;
import java.util.Scanner;

/**
 *
 * @author gerard
 */

public class VierOpEenRij {
    private static final char[] spelers = new char[] { 'X', 'O' };

    private final int breedte, hoogte;
    private final char[][] bord;
    private int gekozenKolom = -1; // laatst gekozen kolom
    private int grensRij = -1;// hoogste rij (grensrij)bij deze kolom

    public VierOpEenRij(int pbreedte, int phoogte) {
        this.breedte = pbreedte;
        this.hoogte = phoogte;
        this.bord = new char[phoogte][pbreedte];
        char aChar = '.';

        for (int rij = 0; rij < this.bord.length; rij++)
          {
        for (int kolom = 0; kolom < this.bord[rij].length; kolom++)
        {
            this.bord[rij][kolom] = aChar;
        }
    }   
}   
        
    public String toString() {
        String BordBeeld = "";
        for (int rij = 0; rij < this.bord.length; rij++)
           {
           for (int kolom = 0; kolom < this.bord[rij].length; kolom++)
           {
            BordBeeld = BordBeeld + this.bord[rij][kolom];
           }
           BordBeeld = BordBeeld + "\n";
           }
       return BordBeeld; 
       
     }

    /**
     * geeft speler een keus tot een geldige keus is gemaakt
     */ 
    public void KiesKolom(char psymbol) {
        
           Scanner keyboard = new Scanner(System.in);
             
           
        
      do {           
            int kol = keyboard.nextInt();

            if (! (0 <= kol && kol < this.breedte)) {
                System.out.println("Kolom moeten tussen 0 and " +
                                   (this.breedte - 1) + " zijn");
                continue;
            }
            
            for (int h = this.hoogte - 1; h >= 0; h--) {
                               
                if (this.bord[h][kol] == '.') {// er is nog ruimte
                    this.gekozenKolom = kol;
                    this.grensRij = h;
                    this.bord[this.grensRij][this.gekozenKolom] = psymbol;
                    return;
                }
               
            }
             System.out.println("Kolom " + kol + " is vol.");
        } while (true);
    }

    /**
     * bekijk per zet of er een winnende reeks is gemaakt
     */
    public boolean WinnendeZet() {
     
        char sym = this.bord[this.grensRij][this.gekozenKolom];
        String reeks = String.format("%c%c%c%c", sym, sym, sym, sym);
        return bevat(this.horizontaal(), reeks) ||
               bevat(this.vertikaal(), reeks) ||
               bevat(this.slashDiagonaal(), reeks) ||
               bevat(this.backslashDiagonaal(), reeks);
    }

    /**
     * zit er een winnende reeks in de horizontale rij
     */
    private String horizontaal() {
        return new String(this.bord[this.grensRij]);
    }

    /**
     * zit er een winende reeks en ide verticale rij
     */
    private String vertikaal() {
        StringBuilder sb = new StringBuilder(this.hoogte);
        for (int h = 0; h < this.hoogte; h++) {
            sb.append(this.bord[h][this.gekozenKolom]);
        }
        return sb.toString();
    }

    /**
     *  
     * 
     */
    private String slashDiagonaal() {
        StringBuilder sb = new StringBuilder(this.hoogte);
        for (int h = 0; h < this.hoogte; h++) {
            int w = this.gekozenKolom + this.grensRij - h;
            if (0 <= w && w < this.breedte) {
                sb.append(this.bord[h][w]);
            }
        }
        return sb.toString();
    }

    /**
     *
     */
    private String backslashDiagonaal() {
        StringBuilder sb = new StringBuilder(this.hoogte);
        for (int h = 0; h < this.hoogte; h++) {
            int w = this.gekozenKolom - this.grensRij + h;
            if (0 <= w && w < this.breedte) {
                sb.append(this.bord[h][w]);
            }
        }
        return sb.toString();
    }

    private boolean bevat(String hooiberg, String naald) {
        return hooiberg.contains(naald);
    }

    public static void main(String[] args) {
        
        int speler = 0;
        VierOpEenRij bord = new VierOpEenRij(8, 6);
     
       
        System.out.println("Kies tussen 0 en 7 voor je kolom.");
             
            for (int maxzetten=6*8; maxzetten>0; maxzetten--) {
                char symbol = spelers[speler];
                             
                   
                   System.out.println(bord);
                   System.out.print("\nSpeler " + symbol + " aan zet: ");
                           
                   bord.KiesKolom(symbol);
                   
                   
                
                   if (bord.WinnendeZet()) {
                       System.out.println("Speler " + symbol + " wint!");
                      return;
                   }
                
                speler = 1 - speler;
              }  
           
            System.out.println("Remise.");
        }
    }


Gepost door op

Geen opmerkingen:

Een reactie posten

Abonneren op: Reacties posten (Atom)