challenge マルバツゲーム:賢いプレイヤー

#6190 の続編です。
マルバツゲームで、賢いプレイヤーの思考ルーチンを実装してください。

賢いといってもいろいろありますが、
1.負けない
2.できるだけ勝つ
という条件でいってみたいと思います。

ランダムプレイヤーと1万回バトルした結果(勝ち・負け・分け)を表示してください。
先攻になっても後攻になっても無敗!となれば言うことなしです。

Posted feedbacks - Flatten

Nested Hidden

前回のソースに、新たにPlayerを追加しました。 RandomPlayerと対決した場合、完封できることを確認しました。 また、追加したPlayer同士だと常に引き分けになります。

  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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
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;
    }
}

微妙な感じですがとりあえず・・・CleverPlayerを追加しました。

1万回対戦させてみたところ

Cleverが先行

Clever won:9,379
Random won:0
draw      :621

Randomが先行

Clever won:8,596
Random won:0
draw      :1,404

Clever vs Clever

Clever won:0
Clever won:0
draw      :10,000

という感じでした。戦略は優先度順に

  1. 置けば勝ち、置かなければ負ける、という位置があればそこに置く
  2. 自分が後手で1ターン目に相手が真ん中に置かなかった場合の2ターン目
    • 相手が置いているところが全て角なら角以外の淵に置く
    • でなければ相手の置いているところから距離が一番近い角に置く
  3. 真ん中が空いていれば真ん中に置く
  4. 角が空いていれば角に置く
  5. 置けるところに置く

としてみました。

 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
import java.util.Random

class TicTacToe(val players:List[Player]) {
  val size = 3
  protected val field = new Array[Array[char]](size,size)
  val lines = (_stline((v,v2) => (v,v2))++_stline((v,v2) => (v2,v))++
              List(((size-1).until(-1,-1)).map(v=> (v,(size-1-v)))) ++
              List((0 until size).map(v=>(v,v)))).map(_.toList)

  def _stline(f:(int,int) => Pair[int,int]) = 
    (0 until size).map(v => (0 until size).map(v2 => f(v,v2)))

  def start:Option[Player] = {
    for(val i<-(0 until size); val j<-(0 until size)) { field(i)(j) = ' '}
    Stream.const(players).flatMap(v=>v).take(size*size).find {player => 
      val p@Pair(y,x) = player.put(this)
      if(!available_?(p)) error("Oops!")
      field(y)(x) = player.mark
      judge
    }
  }

  def judge = lines.exists(l => l.forall(!available_?(_)) && l.forall(v => at(l(0)) == at(v)))
  def available_?(pos:Pair[int,int]) = at(pos) equals ' '
  def at(pos:Pair[int,int]) = field(pos._1)(pos._2)
  def at_eq(pos:Pair[int,int], mark:char) = at(pos) equals mark
  def enemy_of(player:Player) = players.find{_.mark != player.mark}.get
}

abstract class Player{
  val mark:char
  val name:String
  def put(ttt:TicTacToe):Pair[int,int]
}

class RandomPlayer(override val mark:char, override val name:String) extends Player{
  val rnd = new Random
  override def put(ttt:TicTacToe) = {
    def _n = (rnd.nextInt(ttt.size), rnd.nextInt(ttt.size))
    def next(v:Pair[int,int]):Stream[Pair[int,int]] = Stream.cons(v, next(_n))
    next(_n).find(ttt.available_?).get
  }
}

class CleverPlayer(override val mark:char, override val name:String) extends Player {
  override def put(ttt:TicTacToe):Pair[int,int] = {
    val enemy = ttt.enemy_of(this)
    val return_if_available_find = (l:Seq[Pair[int,int]]) => l.find(ttt.available_?) match {
      case Some(pos) => return pos
      case _ => ()
    }

    def line2(v:char) = ttt.lines.filter(_.count(ttt.at_eq(_,v)) == 2)
    return_if_available_find(List(mark, enemy.mark).flatMap(line2).flatMap(v=>v))

    val all  = (for(val i<-(0 until ttt.size); val j<-(0 until ttt.size)) yield (i,j)).toList
    val center = (ttt.size/2, ttt.size/2)
    val corners = List((0,0), (ttt.size-1,ttt.size-1), (0,ttt.size-1), (ttt.size-1, 0))
    val others = all.diff(center::corners)

    if(all.count(ttt.at_eq(_, enemy.mark)) == 2 && ttt.at_eq(center, this.mark)) {
      if(!others.forall(ttt.available_?)) {
        val ps = all.filter(ttt.at_eq(_, enemy.mark))
        def vecv(a:Pair[int,int]) = (0 /: ps){(r, p) => r+(a._1 - p._1).abs+(a._2 - p._2).abs}
        return_if_available_find(corners.sort(vecv(_) < vecv(_)))
      }
      return_if_available_find(others)
    }

    return_if_available_find(List(center))
    return_if_available_find(corners)
    others.find(ttt.available_?).get
  }
}

無敗のアルゴリズムはネット上にあんまり転がっていないと思って出題したのですが、結構あっさり解かれてしまいますね。。。

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

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

こんにちは。前回投稿した#6205を改造してプレイヤをつくりました。今回は1ソースのお手軽実装です。 元のシステムの流れを変えないようにしながらも幾らか追加点がありますがシステムのコードが長いので省略させていただきます。 で、ベターなほうのプレイヤ同士だと全部引き分けでした。ランダム要素が無いのでしょうがないですね。 あと、盤面の幅は3に依存しています。 あぁ、バグ取りはしましたけど保障はしません。

Result:

Random Player.[103] BetterThinkPlayer.[7210] Draw[2687]

BetterThinkPlayer.[9287] Random Player.[0] Draw[713]

 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
#include "Player.h"

class BetterPlayer:public Player{//長さ3専用
public:
    char*GetName(){ return "BetterThinkPlayer.";}
    void Play(MBGame& in){
        if(in.HasEmpty() && in.Length()>3) {
            while(in.SetStone(rand()%in.Length(),rand()%in.Length(),Mark_));
            return;
        }
        //マスの重み
        short Point[]={    43,27 ,41,
                        28,100,26,
                        42,29 ,44,
        };
        int op=0;
        do{
            if(!in.HasEmpty()) return;
            think(in,Point,sizeof(Point));
            for(int i=0;i<sizeof(Point);i++){
                if(Point[i] >Point[op]){
                    op=i;
                }
            }
            Point[op]=-10000;
        }while(!in.SetStone(op%3,op/3,Mark_));
        
    }
protected:
    
    void think(MBGame& in,short Point[],int N){
        const short Posi = 10;
        const short Nega = -5;
        const short denger =9999;
        char Lines[8][3]={
                        {0,1,2},{3,4,5},{6,7,8},//横
                        {0,3,6},{1,4,7},{2,5,8},//縦
                        {0,4,8},{2,4,6},//斜め
        };
        char Side[9][9]={    
                        {1,3,-1},//-1は番兵
                        {0,2,4,-1},
                        {1,5,-1},
                        {0,4,6,-1},
                        {0,1,2,3,5,6,7,8,-1},
                        {2,4,8,-1},
                        {3,7,-1},
                        {6,4,8,-1},    
                        {5,7,-1},
        };
        for(int i=0;i<9;i++){//こまの配置による判定
            for(int j=0;Side[i][j]!= -1;j++){
                int x=0,y=0;
                int N = Side[i][j];
                x = N%3;
                y = N/3;
                Mark M= in.At(x,y);
                if(M == Mark_) Point[Side[i][j]]+= Posi;
                if(M != Mark_ && M != None ) Point[Side[i][j]]+= Nega;
            }
        }
        for(int i=0;i<8;i++){//超危ない時の判定
            int P=0;
            int x=0,y=0;
            for(int j=0;j<3;j++){
                int N= Lines[i][j];
                x = N%3;
                y = N/3;
                Mark M = in.At(x,y);
                if(M == Mark_) P++;
                if(M != None && M != Mark_) P--;
            }
            for(int j=0;j<3;j++){
                if(P == 2) Point[Lines[i][j]]+=denger;
                if(P == -2) Point[Lines[i][j]]+=denger;
            }
        }
    }

};

バグ見つけてしまいました。面目ない。 コメントの位置を参考にして必要なら差し替えてください。

Random Player.[293] BetterThinkPlayer.[8721] Draw[986]

BetterThinkPlayer.[9858] Random Player.[0] Draw[142]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        for(int i=0;i<9;i++){//こまの配置による判定
            int x,y;
                x = i%3;
                y = i/3;
            Mark M= in.At(x,y);
            for(int j=0;Side[i][j]!= -1;j++){
                if(M == Mark_) Point[Side[i][j]]+= Posi;
                if(M != Mark_ && M != None ) Point[Side[i][j]]+= Nega;
            }
        }

Squeak Smalltalk で。

勝ちの手か、負け回避の必要がなければ、

  • 中央が空いていれば中央
  • 隅が空いていれば、相手が陣取ったマス目に近いほうの開いている隅。ただし、後手で ○×○ と斜めに列んだときは隅以外。
  • ランダム

の判断順としてみました。

 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
| 全マス目 全ライン 勝敗カウンタ 中央のマス 隅のマス群 縁のマス群 |

中央のマス := #(2 2).
隅のマス群 := #((1 1) (3 3) (1 3) (3 1)).
縁のマス群 := #((1 2) (3 2) (2 1) (2 3)).
全マス目 := (中央のマス, 隅のマス群, 縁のマス群) asOrderedCollection.

全ライン := OrderedCollection new.
(1 to: 3) do: [:座標1 |
    全ライン add: ((1 to: 3) collect: [:座標2 | {座標1. 座標2}]).
    全ライン add: ((1 to: 3) collect: [:座標2 | {座標2. 座標1}])].
全ライン add: #((1 1) (2 2) (3 3)); add: #((1 3) (2 2) (3 1)).

^#(賢い先手 #賢い後手 #賢い両者) collect: [:モード |

    勝敗カウンタ := Bag new.

    1e4 timesRepeat: [
        | 残りマス群 先手 後手 打ち手順 ランダム 手番 結果 |
        残りマス群 := 全マス目 copy.
        先手 := OrderedCollection new. 後手 := 先手 copy.
        打ち手順 := {先手. 後手}.
        ランダム := モード caseOf: {
                [#賢い先手] -> [後手].
                [#賢い後手] -> [先手]}
            otherwise: [nil].
        手番 := 0.
        結果 := nil.

        [残りマス群
            ifEmpty: [結果 := #引き分け]
            ifNotEmpty: [
                | 打ち手 敵の手 必勝手検索 必勝の手 守りの手 詰み回避の手 最善手 打つ手 |
                打ち手 := 打ち手順 atWrap: (手番 := 手番 + 1).
                敵の手 := 打ち手順 atWrap: 手番 + 1.

                必勝手検索 := [:対象マス群 |
                    | 候補群 |
                    全ライン
                        detect: [:構成マス群 |
                            (候補群 := 構成マス群 difference: 対象マス群) size = 1 and: [
                                残りマス群 includesAllOf: 候補群]]
                        ifNone: [候補群 := #()]..
                    候補群 ifNotEmpty: [候補群 first] ifEmpty: [nil]].

                必勝の手 := [必勝手検索 value: 打ち手].
                守りの手 := [必勝手検索 value: 敵の手].

                詰み回避の手 := [
                    (残りマス群 includes: 中央のマス) ifTrue: [中央のマス] ifFalse: [
                        (敵の手 includesAnyOf: {隅のマス群 first: 2. 隅のマス群 last: 2})
                            ifTrue: [縁のマス群 first]
                            ifFalse: [
                                (隅のマス群 intersection: 残りマス群)
                                    ifNotEmptyDo: [:候補群 |
                                        候補群 detectMin: [:候補 |
                                            敵の手 inject: 0 into: [:総和 :敵のマス |
                                                総和 + (敵のマス * 候補) sum]]]
                                    ifEmpty: [nil]]]].

                最善手 := [
                    必勝の手 value ifNil: [
                        守りの手 value ifNil: [
                            詰み回避の手 value ifNil: [残りマス群 atRandom]]]].

                打つ手 := 打ち手 ~~ ランダム ifTrue: [最善手 value] ifFalse: [残りマス群 atRandom].
                打ち手 add: (残りマス群 remove: 打つ手).
                (全ライン anySatisfy: [:必須マス群 | 打ち手 includesAllOf: 必須マス群])
                    ifTrue: [結果 := 打ち手 == 先手 ifTrue: [#先手勝ち] ifFalse: [#後手勝ち]]].
        結果 isNil] whileTrue.

        勝敗カウンタ add: 結果].

    モード -> 勝敗カウンタ sortedCounts asArray]

"=> {#賢い先手->{9774->#先手勝ち. 226->#引き分け}. 
    #賢い後手->{7962->#後手勝ち. 2038->#引き分け}. 
    #賢い両者->{10000->#引き分け}} "

プレイヤの説明が抜けてましたね。

基本構造。

評価関数というものを使っています。

説明。

Playの中の変数Pointにマスの重みを持たせています。優先順位は「1、真ん中。2、隅。3、残り。」 重みの高い順に選んでいっておける場所を発見したら手を終了します。 で、重みは変化します。 あるポイントに自分のコマがあったら周りをポイント+。逆に相手のコマがあったらポイント-しています。さらに危険な場所を発見したら巨数を+して回避にあてます。重みをいじれば幾らかバリエーションがだせます。そんな感じの流れです。

最後に。

幾らか急いだために作りこみが甘かったことをここに懺悔いたします。 修正版だと先手が常に勝つようになってしまいました。重みを調整すれば平等になります。


バグがありました。いったい何を思ってそんなふうに書いてしまったのか、それでなぜそれっぽく動いていたのかまったく不思議です(^_^;)。以下、差分です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
6c6
< 全マス目 := (中央のマス, 隅のマス群, 縁のマス群) asOrderedCollection.
---
> 全マス目 := ({中央のマス}, 隅のマス群, 縁のマス群) asOrderedCollection.
51c51,52
<                         (敵の手 includesAnyOf: {隅のマス群 first: 2. 隅のマス群 last: 2})
---
>                         (敵の手 size = 2 and: [{隅のマス群 first: 2. 隅のマス群 last: 2}
>                                 anySatisfy: [:二隅 | (敵の手 copyWithoutAll: 二隅) isEmpty]])
58c59
<                                                 総和 + (敵のマス * 候補) sum]]]
---
>                                                 総和 + ((候補 - 敵のマス) * (候補 - 敵のマス)) sum]]]
76,77c77,78
< "=> {#賢い先手->{9774->#先手勝ち. 226->#引き分け}. 
<     #賢い後手->{7962->#後手勝ち. 2038->#引き分け}. 
---
> "=>  {#賢い先手->{9607->#先手勝ち. 393->#引き分け}.
>     #賢い後手->{8544->#後手勝ち. 1456->#引き分け}.

AIぽい解だと思