DouKaku? 6234 horiuchi: 前回のソースに、新たにPlayerを追加...(マルバツゲーム：賢いプレイヤー)

Comment detail

前回のソースに、新たにPlayerを追加しました。 RandomPlayerと対決した場合、完封できることを確認しました。また、追加したPlayer同士だと常に引き分けになります。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class TicTacToe {
    public static final int SIZE = 3;

    private static final Pair[][] lines_ = new Pair[][] {
            { Pair.get(0, 0), Pair.get(0, 1), Pair.get(0, 2) },
            { Pair.get(1, 0), Pair.get(1, 1), Pair.get(1, 2) },
            { Pair.get(2, 0), Pair.get(2, 1), Pair.get(2, 2) },
            { Pair.get(0, 0), Pair.get(1, 0), Pair.get(2, 0) },
            { Pair.get(0, 1), Pair.get(1, 1), Pair.get(2, 1) },
            { Pair.get(0, 2), Pair.get(1, 2), Pair.get(2, 2) },
            { Pair.get(0, 0), Pair.get(1, 1), Pair.get(2, 2) },
            { Pair.get(2, 0), Pair.get(1, 1), Pair.get(0, 2) }, };
    public static final List<List<Pair>> LineList = new ArrayList<List<Pair>>();
    static {
        for (Pair[] line: lines_) {
            List<Pair> list = new ArrayList<Pair>();
            for (Pair pair: line) {
                list.add(pair);
            }
            LineList.add(Collections.unmodifiableList(list));
        }
    }

    private final Mark[][] fields_ = new Mark[SIZE][SIZE];

    public TicTacToe() {
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                fields_[x][y] = Mark.E;
            }
        }
    }

    public Mark getMark(Pair pair) {
        return fields_[pair.x][pair.y];
    }

    public void setMark(Pair pair, Mark mark) {
        fields_[pair.x][pair.y] = mark;
    }

    public boolean nextStep(Pair pair, Mark mark) {
        if (getMark(pair) != Mark.E)
            return false;
        setMark(pair, mark);
        return true;
    }

    public Mark isEndGame() {
        for (Pair[] row : lines_) {
            Mark m = null;
            boolean isSame = true;
            for (Pair cell : row) {
                Mark mark = fields_[cell.x][cell.y];
                if (m == null) {
                    m = mark;
                    continue;
                }
                if (m != mark) {
                    isSame = false;
                    break;
                }
            }
            if (isSame)
                return m;
        }
        return Mark.E;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 0))),
                toString(getMark(Pair.get(1, 0))),
                toString(getMark(Pair.get(2, 0)))));
        builder.append(String.format("-+-+-%n"));
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 1))),
                toString(getMark(Pair.get(1, 1))),
                toString(getMark(Pair.get(2, 1)))));
        builder.append(String.format("-+-+-%n"));
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 2))),
                toString(getMark(Pair.get(1, 2))),
                toString(getMark(Pair.get(2, 2)))));
        return builder.toString();
    }
    private String toString(Mark mark) {
        switch (mark) {
            case O:
            case X:
                return mark.toString();
            case E:
            default:
                return " ";
        }
    }

    public static void main(String[] args) {
        Player random1 = new RandomPlayer(Mark.O, "random1");
        Player random2 = new RandomPlayer(Mark.X, "random2");
        Player think1 = new ThinkingPlayer(Mark.O, "think1");
        Player think2 = new ThinkingPlayer(Mark.X, "think2");

        playGame(random1, random2);
        playGame(think1, random2);
        playGame(random1, think2);
        playGame(think1, think2);
    }

    private static void playGame(Player player1, Player player2) {
        int maxTurn = TicTacToe.SIZE * TicTacToe.SIZE;
        int[] result = new int[3];
        for (int round = 0; round < 10000; round++) {
            TicTacToe game = new TicTacToe();
            for (int turn = 0; turn <= maxTurn; turn++) {
                if (turn == maxTurn) {
                    result[2]++;
                    break;
                } else if (turn % 2 == 0) {
                    player1.put(game);
                } else {
                    player2.put(game);
                }
                Mark mark = game.isEndGame();
                if (mark == Mark.O) {
                    result[0]++;
                    break;
                } else if (mark == Mark.X) {
                    result[1]++;
                    break;
                }
            }
        }

        System.out.println("Result:");
        System.out.printf("%s won: %d%n", player1.name, result[0]);
        System.out.printf("%s won: %d%n", player2.name, result[1]);
        System.out.printf("draw game  : %d%n", result[2]);
    }
}

enum Mark {
    E {
        @Override public Mark getOpponent() { return E; }
    },
    O {
        @Override public Mark getOpponent() { return X; }
    },
    X {
        @Override public Mark getOpponent() { return O; }
    };

    public abstract Mark getOpponent();
}

class Pair {
    public final int x;
    public final int y;

    private Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    private static final List<Pair> cache = new ArrayList<Pair>();
    static {
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                cache.add(new Pair(x, y));
            }
        }
    }
    public static Pair get(int x, int y) {
        return cache.get(x * TicTacToe.SIZE + y);
    }

    @Override
    public int hashCode() {
        return x * 3 + y;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof Pair)) return false;
        Pair other = (Pair) obj;
        return this.x == other.x && this.y == other.y;
    }
}

abstract class Player {
    public final Mark mark;
    public final String name;

    public Player(Mark mark, String name) {
        this.mark = mark;
        this.name = name;
    }
    public abstract void put(TicTacToe game);
}

class RandomPlayer extends Player {
    private final Random random_ = new Random();

    public RandomPlayer(Mark mark, String name) {
        super(mark, name);
    }

    @Override
    public void put(TicTacToe game) {
        if (game.isEndGame() != Mark.E) return;
        for (;;) {
            Pair pair = getNextPair();
            boolean res = game.nextStep(pair, mark);
            if (res)
                break;
        }
    }
    private Pair getNextPair() {
        return Pair.get(random_.nextInt(TicTacToe.SIZE), random_.nextInt(TicTacToe.SIZE));
    }
}

class ThinkingPlayer extends Player {
    private static final Pair CENTER = Pair.get(1, 1);
    private static final List<Pair> CORNER = new ArrayList<Pair>();
    private static final List<Pair> SIDES = new ArrayList<Pair>();

    public ThinkingPlayer(Mark mark, String name) {
        super(mark, name);
        CORNER.add(Pair.get(0, 0));
        CORNER.add(Pair.get(2, 2));
        CORNER.add(Pair.get(2, 0));
        CORNER.add(Pair.get(0, 2));
        SIDES.add(Pair.get(1, 0));
        SIDES.add(Pair.get(1, 2));
        SIDES.add(Pair.get(0, 1));
        SIDES.add(Pair.get(2, 1));
    }

    @Override
    public void put(TicTacToe game) {
        if (game.isEndGame() != Mark.E) return;
        
        int turn = 0;
        Map<Pair, Boolean> map = new HashMap<Pair, Boolean>();
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                Pair pair = Pair.get(x, y);
                Mark mark = game.getMark(pair);
                if (mark == Mark.E) continue;
                turn++;
                map.put(pair, mark == this.mark);
            }
        }

        switch (turn) {
            case 0:
            case 1:
                priorityStep(game);
                break;
            case 2:
                {
                    if (map.get(CENTER) == null) {
                        game.nextStep(CENTER, this.mark);
                    } else {
                        for (int index = 0, size = CORNER.size(); index < size; index++) {
                            if (map.get(CORNER.get(index)) == Boolean.FALSE) {
                                int i = (index & 2) + (~index & 1);
                                boolean step = game.nextStep(CORNER.get(i), this.mark);
                                if (step) return;
                            }
                        }
                        priorityStep(game);
                    }
                }
                break;
            case 3:
                {
                    Set<Pair> winPair = searchWinPair(game, this.mark.getOpponent());
                    if (!winPair.isEmpty()) {
                        boolean step = game.nextStep(winPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    if (game.getMark(CENTER) == this.mark) {
                        if ((game.getMark(CORNER.get(0)) == this.mark.getOpponent() && game.getMark(CORNER.get(1)) == this.mark.getOpponent())
                                || (game.getMark(CORNER.get(2)) == this.mark.getOpponent() && game.getMark(CORNER.get(3)) == this.mark.getOpponent())) {
                            for (Pair pair: SIDES) {
                                boolean step = game.nextStep(pair, this.mark);
                                if (step) return;
                            }
                        }
                    }
                    Set<Pair> goodPair = searchGoodPair(game, this.mark.getOpponent());
                    if (!goodPair.isEmpty()) {
                        boolean step = game.nextStep(goodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    priorityStep(game);
                }
                break;
            default:
                {
                    Set<Pair> winPair = searchWinPair(game, this.mark);
                    if (!winPair.isEmpty()) {
                        boolean step = game.nextStep(winPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> losePair = searchWinPair(game, this.mark.getOpponent());
                    if (!losePair.isEmpty()) {
                        boolean step = game.nextStep(losePair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> noGoodPair = searchGoodPair(game, this.mark.getOpponent());
                    if (!noGoodPair.isEmpty()) {
                        boolean step = game.nextStep(noGoodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> goodPair = searchGoodPair(game, this.mark);
                    if (!goodPair.isEmpty()) {
                        boolean step = game.nextStep(goodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    priorityStep(game);
                }
                break;
        }
    }

    private void priorityStep(TicTacToe game) {
        boolean step = false;
        {
            step = game.nextStep(CENTER, this.mark);
            if (step) return;
        }
        for (Pair pair: CORNER) {
            step = game.nextStep(pair, this.mark);
            if (step) return;
        }
        for (Pair pair: SIDES) {
            step = game.nextStep(pair, this.mark);
            if (step) return;
        }
    }

    private Set<Pair> searchWinPair(TicTacToe game, Mark mark) {
        Set<Pair> list = new HashSet<Pair>();
        for (List<Pair> line: TicTacToe.LineList) {
            int count = 0;
            Pair empty = null;
            for (Pair pair: line) {
                if (game.getMark(pair) == mark) {
                    count++;
                } else if (game.getMark(pair) == mark.getOpponent()) {
                    count = -1;
                    break;
                } else {
                    empty = pair;
                }
            }
            if (count == 2 && empty != null) list.add(empty);
        }
        return list;
    }

    private Set<Pair> searchGoodPair(TicTacToe game, Mark mark) {
        Set<Pair> list = new HashSet<Pair>();
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                Pair pair = Pair.get(x, y);
                if (game.getMark(pair) == Mark.E) {
                    game.setMark(pair, mark);
                    Set<Pair> winPair = searchWinPair(game, mark);
                    if (winPair.size() > 1) list.add(pair);
                    game.setMark(pair, Mark.E);
                }
            }
        }
        return list;
    }
}
無敗のアルゴリズムはネット上にあんまり転がっていないと思って出題したのですが、結構あっさり解かれてしまいますね。。。

これから投稿される方も、ぜひ自力でアルゴリズムを考えてみてください。自分だったらこうするという手順をプログラムに落とし込んでいくのは結構楽しいですよ！

ちなみに出題者の実装は #6235 の yuin さんの書かれた戦略とほぼ同じものになりました。
DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq
