Connect 4 - Bewertungsfunktion

CyborgBeta · 19. April 2019 um 05:46

Moin Moin,
ich weiß, dazu gibt es viel im Internet, aber noch nicht viel Brauchbares, finde ich. Wie würdet ihr das bewerten (diese Ausgangssituation…):

[ ,  , O,  ,  ,  ,  ]
[ ,  , O,  ,  ,  ,  ]
[ ,  , O,  ,  ,  ,  ]
[ ,  , x,  ,  ,  ,  ]
[ ,  , O,  ,  ,  ,  ]
[ ,  , O,  ,  , O, O]

bewerten( 1) 3
bewerten(-1) -41

Das Spielfeld ist immer 7x6-lang. O hat 2x 2 in einer Reihe und 1x 3 in einer Reihe; x hat nur 1x 1 in einer Reihe. Kann dann 3 und -41 ungefähr stimmen?

Hier ist der Code mit der Bewertungsfunktion (es sind nur 100 Zeilen ):

import java.util.Arrays;
/**
 * @author CB on 04-19-2019
 */
public class VG {
    private static Boolean[][] b = new Boolean[6][7];

    private static void print() {
        for (int i = 0; i < 6; i++) {
            System.out.println(Arrays.toString(b[i]).replace("null", " ").replace("true", "x").replace("false", "O"));
        }
        System.out.println();
    }

    private static void take(int x, boolean a) {
        int i = 5;
        for (; i >= 0; i--) {
            if (b[i][x] == null) {
                break;
            }
        }
        b[i][x] = a;
    }

    public static void main(String[] args) {
        print();
        take(2, false);
        take(2, false);
        take(2, true);
        take(2, false);
        take(2, false);
        take(2, false);
        take(6, false);
        take(5, false);
        print();
        System.out.println("bewerten( 1) " + bewerten( 1));
        System.out.println("bewerten(-1) " + bewerten(-1));
    }

    private static int bewerten(int spieler) {
        int c1 = 0;
        Boolean s = spieler == 1;
        int c2 = 0;
        
        //horizontally
        for (int i = 0; i < 6; i++) {
            int c3 = 0;
            for (int j = 0; j < 7; j++) {
                if (s.equals(b[i][j])) {
                    c3++;
                }
            }
            if (shift(c3) > c2) {
                c2 = shift(c3);
            }
        }
        if (c2 > 0) {
            c1 += c2;
        }
        c2 = 0;
        
        //vertically
        for (int i = 0; i < 7; i++) {
            int c3 = 0;
            for (int j = 0; j < 6; j++) {
                if (s.equals(b[j][i])) {
                    c3++;
                }
            }
            if (shift(c3) > c2) {
                c2 = shift(c3);
            }
        }
        if (c2 > 0) {
            c1 += c2;
        }
        c2 = 0;
        
        //diagonally
        for (int i = 0; i < 6; i++) {
            int c3 = 0;
            for (int j = 0, k = i; j < 7 && k < 6; j++, k++) {
                if (s.equals(b[k][j])) {
                    c3++;
                }
            }
            if (shift(c3) > c2) {
                c2 = shift(c3);
            }
        }
        if (c2 > 0) {
            c1 += c2;
        }
        
        return spieler * c1;
    }

    private static int shift(int c) {
        return (1 << c) - 1;
    }
}

Ich bin da echt überfragt…

CyborgBeta · 21. April 2019 um 10:06

Ich denke, es müsste richtig sein. Wenn nicht, müsste man zeigen, dass es keine i. Spielsituation gibt, wobei in der (i+1.) Spielsituation Spieler +1 besser ist als Spieler -1, aber dennoch bewerten(+1) <= bewerten(-1) für die i. Spielsituation gilt… Das kann ich aber nicht zeigen, da es viel zu viele Spielsituationen gibt. Oder man müsste die Korrektheit von bewerten() ie-wie anders zeigen (vst. Induktion?). Wie beweist man denn Bitte, ob eine Heuristik korrekt ist? Man definiert doch nicht einfach eine und lässt sie gegen einen anderen starken Spieler spielen und schaut, was dabei herauskommt?

Und die zweite Frage wäre, ob diese Heuristik bewerten() „kleinstmögliche,“ eindeutige Bewertungen zurückgibt oder nicht. Also sozusagen „minimal“ wäre.

… Frohe Ostern euch allen!