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ぽい解だと思います。この方法を使えば、評価関数をうまく設定することで4×4などへの応用がききそうです。

一つ言わせていただくと、BetterThinkPlayerが後攻の場合、わずかですがランダムプレイヤーに負ける結果があります。実は匿名さんのBetterThinkPlayerには急所があり、そこを先攻に狙われると負けてしまうのです。その部分を改善すれば、無敗のBestThinkPlayerになると思います。ぜひやってみてください。

(出題者としては、ここで皆さんが悩んでくれることを期待していました)

1
2
3
4
5
6
7
ヒント:
short Point[]={    20,15 ,18,
                    14,16,13,
                    17,12 ,19,
        };
このような重み付けの相手に弱くはありませんか?
(実際に試してはいないので、違ったらスミマセン。)

全パターン列挙型にしました。

ox_play_tuyoi(LPOXGAME g, const char player)
を追加した形です。

random:
O:5828, X:2899, T:1273
O:5785, X:2911, T:1304
O:5863, X:2899, T:1238

tuyoi O: (強いプレイヤー先手)
O:9593, X:0, T:407
O:9598, X:0, T:402
O:9560, X:0, T:440
O:9630, X:0, T:370

tuyoi X: (強いプレイヤー後手)
O:49, X:8573, T:1378
O:45, X:8584, T:1371
O:65, X:8571, T:1364
O:48, X:8560, T:1392


負けパターン:
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|X| |O| |X| |O| |X| |O| |X| |O| | | |O| | | |O| | | |O|
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
| |X|X| | |X|X| | |X| | | |X| | | |X| | | |X| | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|O|O|O| |O| |O| |O| |O| |O| | | |O| | | | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

負けパターン:
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|X| |X| |X| |X| |X| | | |X| | | |X| | | |X| | | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|X|O| | |X|O| | |X|O| | |X|O| | | |O| | | |O| | | |O| |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|O|O|O| |O| |O| |O| |O| | | |O| | | |O| | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

  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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct tag_game
{
    int map_x;
    int map_o;
} OXGAME , *LPOXGAME;

#define Match(x,pat) ((((x) & 0x0FFF) & (pat)) == (pat))

/* フィールド固有フラグ */
#define NO_0 0x0001
#define NO_1 0x0002
#define NO_2 0x0004
#define NO_3 0x0010
#define NO_4 0x0020
#define NO_5 0x0040
#define NO_6 0x0100
#define NO_7 0x0200
#define NO_8 0x0400

/* フィールド逆引き用 */
static int map_num[9] = {
    NO_0, NO_1, NO_2,
    NO_3, NO_4, NO_5,
    NO_6, NO_7, NO_8,
};

/* フィールド表示 */
static char ox_print_sub(LPOXGAME g, int pat)
{
    if(Match(g->map_o, (pat))) return 'O';
    if(Match(g->map_x, (pat))) return 'X';
    return ' ';
}
int ox_print(LPOXGAME g)
{
    printf( "+-+-+-+\n"
            "|%c|%c|%c|\n"
            "+-+-+-+\n"
            "|%c|%c|%c|\n"
            "+-+-+-+\n"
            "|%c|%c|%c|\n"
            "+-+-+-+",
        ox_print_sub(g,NO_0), ox_print_sub(g,NO_1), ox_print_sub(g,NO_2),
        ox_print_sub(g,NO_3), ox_print_sub(g,NO_4), ox_print_sub(g,NO_5),
        ox_print_sub(g,NO_6), ox_print_sub(g,NO_7), ox_print_sub(g,NO_8));

    return 0;
}

/* 点数計算 */
/* @- int ox_match(LPOXGAME g)
 *    ^^^  > 0 : win O
 *        == 0 : tie
 *         < 0 : win X
 */
static int ox_match_sub(int x)
{
    int pts = 0;

    if(Match( x , (NO_0|NO_1|NO_2))) pts++;
    if(Match( x , (NO_3|NO_4|NO_5))) pts++;
    if(Match( x , (NO_6|NO_7|NO_8))) pts++;

    if(Match( x , (NO_0|NO_3|NO_6))) pts++;
    if(Match( x , (NO_1|NO_4|NO_7))) pts++;
    if(Match( x , (NO_2|NO_5|NO_8))) pts++;

    if(Match( x , (NO_0|NO_4|NO_8))) pts++;
    if(Match( x , (NO_2|NO_4|NO_6))) pts++;

    return pts;
}
int ox_match(LPOXGAME g)
{
    return ox_match_sub(g->map_o) - ox_match_sub(g->map_x);
}

/* 打ち位置計算 ロボ */
/* @- int ox_play(LPOXGAME g)
 *    ^^^ != 0 : 打ち位置
 *    ^^^ == 0 : error
 */
int ox_play(LPOXGAME g)
{
    int x, m;

    m = g->map_o | g->map_x;
    if(Match(m, (NO_0|NO_1|NO_2|
                 NO_3|NO_4|NO_5|
                 NO_6|NO_7|NO_8))) return 0; /* map full */
    for(;;) {
        x = map_num[rand() % 9]; /* ←頭脳 */
        if(!Match(m, x)) return x; /* 空いてるならここ */
    }

    return 0;
}

/* ox_play_tuyoi */
int ox_is_reach( LPOXGAME g, int x )
{
    int m;
    m = g->map_o | g->map_x;
/*
 012
 345
 678
*/
    /* リーチ 置石優先順位 4 > 0,2,6,8 > 1,3,5,7 */
/* --- */
    if(Match( x , (NO_0|NO_8)) && (!Match( m , (NO_4))) ) return NO_4;
    if(Match( x , (NO_2|NO_6)) && (!Match( m , (NO_4))) ) return NO_4;
    if(Match( x , (NO_3|NO_5)) && (!Match( m , (NO_4))) ) return NO_4;
    if(Match( x , (NO_1|NO_7)) && (!Match( m , (NO_4))) ) return NO_4;

    if(Match( x , (NO_1|NO_2)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( x , (NO_3|NO_6)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( x , (NO_4|NO_8)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( x , (NO_5|NO_8)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( x , (NO_4|NO_6)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( x , (NO_0|NO_1)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( x , (NO_7|NO_8)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( x , (NO_0|NO_3)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( x , (NO_2|NO_4)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( x , (NO_6|NO_7)) && (!Match( m , (NO_8))) ) return NO_8;
    if(Match( x , (NO_2|NO_5)) && (!Match( m , (NO_8))) ) return NO_8;
    if(Match( x , (NO_0|NO_4)) && (!Match( m , (NO_8))) ) return NO_8;
                                                
    if(Match( x , (NO_0|NO_2)) && (!Match( m , (NO_1))) ) return NO_1;
    if(Match( x , (NO_4|NO_7)) && (!Match( m , (NO_1))) ) return NO_1;
    if(Match( x , (NO_0|NO_6)) && (!Match( m , (NO_3))) ) return NO_3;
    if(Match( x , (NO_4|NO_5)) && (!Match( m , (NO_3))) ) return NO_3;
    if(Match( x , (NO_2|NO_8)) && (!Match( m , (NO_5))) ) return NO_5;
    if(Match( x , (NO_3|NO_4)) && (!Match( m , (NO_5))) ) return NO_5;
    if(Match( x , (NO_1|NO_4)) && (!Match( m , (NO_7))) ) return NO_7;
    if(Match( x , (NO_6|NO_8)) && (!Match( m , (NO_7))) ) return NO_7;

    return 0;
}
int ox_play_tuyoi(LPOXGAME g, const char player)
{
    int xa, xb, m, xr;

    if(player == 'O') {
        xa = g->map_o; /* O プレイヤ優先*/
        xb = g->map_x;
    }

    if(player == 'X') {
        xa = g->map_x; /* X プレイヤ優先 */
        xb = g->map_o;
    }
    m = g->map_o | g->map_x;
    if(Match(m, (NO_0|NO_1|NO_2|
                 NO_3|NO_4|NO_5|
                 NO_6|NO_7|NO_8))) return 0; /* map full */

    /* リーチなら埋めて勝つ */
    if(xr = ox_is_reach(g, xa)) return xr;

    /* 敵リーチ 阻止 */
    if(xr = ox_is_reach(g, xb)) return xr;

/*
  0 1 2
  3 4 5
  6 7 8
*/
    /* とりあえず 4 > (xb) > 0,2,6,8 > 1,3,5,7 */
    if(!(Match( m , (NO_4)))) return NO_4;

/*
 3パターン 2パターン混合:
 16 => 0
 18 => 2

 32 => 0
 38 => 6

 50 => 2
 56 => 8

 70 => 6
 72 => 8
*/
    if(Match( xb , (NO_1|NO_6)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_1|NO_8)) && (!Match( m , (NO_2))) ) return NO_2;

    if(Match( xb , (NO_3|NO_2)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_3|NO_8)) && (!Match( m , (NO_6))) ) return NO_6;

    if(Match( xb , (NO_5|NO_0)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( xb , (NO_5|NO_6)) && (!Match( m , (NO_8))) ) return NO_8;

    if(Match( xb , (NO_7|NO_0)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( xb , (NO_7|NO_2)) && (!Match( m , (NO_8))) ) return NO_8;

/*
  0 1 2
  3 4 5
  6 7 8
*/
/* 
 3パターン用) 近接置石: 真ん中 > 角 > そのほか
 0 => 4,> 2, 6 > 1, 3
 2 => 4,> 0, 8 > 1, 5
 6 => 4,> 0, 8 > 3, 7
 8 => 4,> 2, 6 > 5, 7
*/
    if(Match( xb , (NO_0)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( xb , (NO_0)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( xb , (NO_0)) && (!Match( m , (NO_1))) ) return NO_1;
    if(Match( xb , (NO_0)) && (!Match( m , (NO_3))) ) return NO_3;

    if(Match( xb , (NO_2)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_2)) && (!Match( m , (NO_8))) ) return NO_8;
    if(Match( xb , (NO_2)) && (!Match( m , (NO_1))) ) return NO_1;
    if(Match( xb , (NO_2)) && (!Match( m , (NO_5))) ) return NO_5;

    if(Match( xb , (NO_4)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_4)) && (!Match( m , (NO_8))) ) return NO_8;
    if(Match( xb , (NO_4)) && (!Match( m , (NO_3))) ) return NO_3;
    if(Match( xb , (NO_4)) && (!Match( m , (NO_7))) ) return NO_7;

    if(Match( xb , (NO_8)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( xb , (NO_8)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( xb , (NO_8)) && (!Match( m , (NO_5))) ) return NO_5;
    if(Match( xb , (NO_8)) && (!Match( m , (NO_7))) ) return NO_7;

/*
  0 1 2
  3 4 5
  6 7 8
*/
/*
 2パターン用) 近接置石: 真ん中 > 角

 1 => 4,> 0, 2
 3 => 4,> 0, 6
 5 => 4,> 2, 8
 7 => 4,> 6, 8
*/

    if(Match( xb , (NO_1)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( xb , (NO_1)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_3)) && (!Match( m , (NO_0))) ) return NO_0;
    if(Match( xb , (NO_3)) && (!Match( m , (NO_6))) ) return NO_6;

    if(Match( xb , (NO_5)) && (!Match( m , (NO_2))) ) return NO_2;
    if(Match( xb , (NO_5)) && (!Match( m , (NO_8))) ) return NO_8;
    if(Match( xb , (NO_7)) && (!Match( m , (NO_6))) ) return NO_6;
    if(Match( xb , (NO_7)) && (!Match( m , (NO_8))) ) return NO_8;

/*
 012
 345
 678
*/  
/* 適当に置く: 真ん中 > 角 */
    if(!(Match( m , (NO_0)))) return NO_0;
    if(!(Match( m , (NO_2)))) return NO_2;
    if(!(Match( m , (NO_6)))) return NO_6;
    if(!(Match( m , (NO_8)))) return NO_8;

    if(!(Match( m , (NO_1)))) return NO_1;
    if(!(Match( m , (NO_5)))) return NO_5;
    if(!(Match( m , (NO_3)))) return NO_3;
    if(!(Match( m , (NO_7)))) return NO_7;

    return 0;
}



/* フィールドにコマ打ち */
int ox_write(LPOXGAME g, const char player, const int x)
{
    int m;

    m = g->map_o | g->map_x;
    if(Match(m, (NO_0|NO_1|NO_2|
                 NO_3|NO_4|NO_5|
                 NO_6|NO_7|NO_8))) return 0; /* map full */

    if(Match(m, x)) return 0; /* error */
    if(player == 'O') g->map_o |= x; /* O プレイヤ処理 */
    if(player == 'X') g->map_x |= x; /* X プレイヤ処理 */

    return 0;
}

/* フィールド初期化処理 */
int ox_init(LPOXGAME g)
{
    g->map_o = 0;
    g->map_x = 0;

    return 0;
}

/* OX プロセス */
int ox_proc(LPOXGAME g)
{
    int x,t;

    ox_init(g);

    for(;;) {
        /*---------*/
        x = ox_play(g); /* 打てる場所を捜す */
//        x = ox_play_tuyoi(g, 'O'); /* tuyoi O */
        ox_write(g, 'O', x); /* 打つ */
        t = ox_match(g); /* 並んでいるか? */
        if(t) break; /* 並んでいる */
        if(!x) break; /* map full */

        /*---------*/
//        x = ox_play(g); /* 打てる場所を捜す */
        x = ox_play_tuyoi(g, 'X'); /* tuyoi X */
        ox_write(g, 'X', x);
        t = ox_match(g);
        if(t) break;
        if(!x) break; /* map full */
    }
    ox_print(g); /* フィールド表示 */
    t = ox_match(g);

    if(t > 0)       printf("... [Win: O]\n");
    else if(t < 0)  printf("... [Win: X]\n");
    else            printf("... [Tie]\n");

    return t;
}

/* */
int main()
{
    int i, t;
    int o = 0,x = 0, ox = 0;
    OXGAME g;

    srand(time(0));

    for(i= 0; i< 10000; i++) {
        t = ox_proc(&g);

        if(t > 0)       o++;
        else if(t < 0)  x++;
        else            ox++;
/*      printf("%ld) O:%ld, X:%ld, T:%ld\n", i,  o, x, ox);*/
    }

    printf("O:%ld, X:%ld, T:%ld\n", o, x, ox);
    return 0;
}

/**
random:
O:5828, X:2899, T:1273
O:5785, X:2911, T:1304
O:5863, X:2899, T:1238

tuyoi O:
O:9593, X:0, T:407
O:9598, X:0, T:402
O:9560, X:0, T:440
O:9630, X:0, T:370

tuyoi X:
O:49, X:8573, T:1378
O:45, X:8584, T:1371
O:65, X:8571, T:1364
O:48, X:8560, T:1392

**/

shuffle便利ですね。lset-ほにゃららをうまく使った方がきれいに書けますね。ということで、gemmaさんにインスパイアされた書き方で挑戦。 アルゴリズムは以下のURIから。 http://2.csx.jp/~3ji-shiki/karegame/tic-tac-toe.html ; random vs random player1 won: 5838 player2 won: 2892 draw: 1270 ; wise vs random player1 won: 9466 player2 won: 0 draw: 534 ; random vs wise player1 won: 0 player2 won: 8362 draw: 1638 ; wise vs wise player1 won: 0 player2 won: 0 draw: 10000
 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
(use srfi-1)
(use gauche.sequence)

(define lset-board  '(0 1 2 3 4 5 6 7 8))
(define lset-corner '(0 2 6 8))
(define lset-edge   '(1 3 5 7))

(define (win? l)
  (any (cut lset<= = <> l)
       '((0 1 2) (3 4 5) (6 7 8) (0 3 6) (1 4 7) (2 5 8) (0 4 8) (2 4 6))))

(define (vacant self other)
  (lset-difference = lset-board (append self other)))

(define (player-random self other)
  (cond ((vacant self other) pair?
     => (lambda (v)
          (cons (car (shuffle v)) self)))
    (else #f)))

(define (player-wise self other)
  (define (next-win v pself)
    (cond ((find win? (map (cut cons <> pself) v))
       => car)
      (else #f)))

  (define (corner-has-neighber corners)
    (define table '((0 1 3) (2 1 5) (6 3 7) (8 7 5)))
    (find (lambda (c)
        (and (pair? (lset-intersection = (cdr (assq c table)) other)) c))
      corners))
    
  (cond ((vacant self other) 
     pair? => (lambda (v)
            (cond ((next-win v self)  => (cut cons <> self))
              ((next-win v other) => (cut cons <> self))
              ((memq 4 v)            (cons 4 self))
              ((or (lset= = other '(0 8)) ;; oxo
                   (lset= = other '(2 6)))
               (cons (car (lset-intersection = v lset-edge))
                 self))
              ((lset-intersection = v lset-corner)
               pair? => (lambda (cs)
                      (cons
                       (or (corner-has-neighber cs)
                       (car cs))
                       self)))
              (else ; edge
               (cons (car v) self))
              )))
    (else #f)))

(define (a-play p1a p2a)
  (define (p1-turn p1 p2)
    (cond ((win? p2) 'lose)
      ((p1a p1 p2) => (cut p2-turn <> p2))
      (else 'draw)))
  (define (p2-turn p1 p2)
    (cond ((win? p1) 'win)
      ((p2a p2 p1) => (cut p1-turn p1 <>))
      (else 'draw)))
  (p1-turn () ()))

(define (play p1a p2a)
  (let new-game ((win 0)
         (lose 0)
         (draw 0))
    (if (<= 10000 (+ win lose draw))
    (format #t "player1 won: ~a\tplayer2 won: ~a\tdraw: ~a\n" win lose draw)
    (case (a-play p1a p2a)
      ((win)  (new-game (+ win 1) lose draw))
      ((lose) (new-game win (+ lose 1) draw))
      ((draw) (new-game win lose (+ 1 draw)))))))

(play player-random player-random)
(play player-wise player-random)
(play player-random player-wise)
(play player-wise player-wise)

お昼休みに少しチューニングしてみました。lset系をやめて、タイトループ中の探索はanyとかfindとか使わずに手で書いて、枝狩りをしたら10倍ぐらい速くなりました。

意外な発見。pa$はcutやlambda書くより遅いですね。

  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
(use srfi-1)
(use srfi-27)
(use util.list)

(define lset-board  '(0 1 2 3 4 5 6 7 8))
(define lset-corner '(0 2 6 8))
(define lset-edge   '(1 3 5 7))

(define (includes? a b)
  (cond
   ((null? b) ())
   ((memq (car b) a)
    (includes? a (cdr b)))
   (else #f)))

(define (sand a b)
  (filter (cut memq <> b) a))

(define (sdif a b)
  (remove (cut memq <> b) a))

(define (win? l)
  (let next ((pat '((0 1 2) (3 4 5) (6 7 8) 
            (0 3 6) (1 4 7) (2 5 8) 
            (0 4 8) (2 4 6))))
    (cond
     ((null? pat) #f)
     ((includes? l (car pat)) #t)
     (else (next (cdr pat))))))

(define (vacant self other)
  (sdif lset-board (append self other)))

(define (player-random self other)
  (define (random-take klist)
    (ref klist (random-integer (length klist))))

  (cond
   ((vacant self other)
    pair? => (lambda (v) (cons (random-take v) self)))
   (else #f)))

(define (player-wise self other)
  (define (next-win vs self)
    (cond
     ((< (length self) 2) #f) ;; shortcut
     ((find win? (map (cut cons <> self) vs))
      => car)
     (else #f)))

  (define (corner-has-neighber vcorners)
    (define table '((0 1 3) (2 1 5) (6 3 7) (8 7 5)))
    (define (has-neighber? vc)
      (and (includes? vc '(1 3 5 7)) ;; shortcut
       (pair? (sand (cdr (assq vc table)) other))))
    (find (lambda (vc) (and (has-neighber? vc) vc))
      vcorners))
    
  (cond
   ((vacant self other)
    pair? => (lambda (v)
           (cond
        ((next-win v self)  => (cut cons <> self))
        ((next-win v other) => (cut cons <> self))
        ((memq 4 v)            (cons 4 self))
        ((and (= 2 (length other))
              (or (includes? other '(0 8))
              (includes? other '(2 6))))
         (cons (car (lset-intersection = v lset-edge))
               self))
        ((sand v lset-corner)
         pair? => (lambda (cs)
                (cons
                 (or (corner-has-neighber cs)
                 (car cs))
                 self)))
        (else ; edge
         (cons (car v) self))
        )))
   (else #f)))

(define (a-play p1a p2a)
  (define (p1-turn p1 p2)
    (cond
     ((win? p2) 'lose)
     ((p1a p1 p2) => (cut p2-turn <> p2))
     (else 'draw)))
  (define (p2-turn p1 p2)
    (cond
     ((win? p1) 'win)
     ((p2a p2 p1) => (cut p1-turn p1 <>))
     (else 'draw)))
  (p1-turn () ()))

(define (play p1a p2a)
  (let new-game ((win 0)
         (lose 0)
         (draw 0))
    (if (<= 10000 (+ win lose draw))
    (format #t "player1 won: ~a\tplayer2 won: ~a\tdraw: ~a\n" win lose draw)
    (case (a-play p1a p2a)
      ((win)  (new-game (+ win 1) lose draw))
      ((lose) (new-game win (+ lose 1) draw))
      ((draw) (new-game win lose (+ 1 draw)))))))

(time (play player-random player-random))
(time (play player-wise player-random))
(time (play player-random player-wise))
(time (play player-wise player-wise))

再挑戦^^;
nelさんのアルゴリズムを使用しました。

後手 X
O:0, X:8549, T:1451
O:0, X:8637, T:1363
O:0, X:8611, T:1389

なるほどー
無敗ですね
 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
struct 
{
    int pat;
    int out;
} reach[] = {
 {NO_0|NO_8, NO_4}, {NO_2|NO_6, NO_4}, {NO_3|NO_5, NO_4}, {NO_1|NO_7, NO_4},

 {NO_1|NO_2, NO_0}, {NO_3|NO_6, NO_0}, {NO_4|NO_8, NO_0},
 {NO_5|NO_8, NO_2}, {NO_4|NO_6, NO_2}, {NO_0|NO_1, NO_2},
 {NO_7|NO_8, NO_6}, {NO_0|NO_3, NO_6}, {NO_2|NO_4, NO_6},
 {NO_6|NO_7, NO_8}, {NO_2|NO_5, NO_8}, {NO_0|NO_4, NO_8},

 {NO_0|NO_2, NO_1}, {NO_4|NO_7, NO_1},
 {NO_0|NO_6, NO_3}, {NO_4|NO_5, NO_3},
 {NO_2|NO_8, NO_5}, {NO_3|NO_4, NO_5},
 {NO_1|NO_4, NO_7}, {NO_6|NO_8, NO_7},
 { 0 , 0 }, 
};

struct 
{
    int pat;
    int out;
} pattern[] = {
 {0, NO_4 }, 
 {NO_4, NO_0}, { NO_4, NO_2}, {NO_4, NO_6}, {NO_4, NO_8}, 
 {NO_0|NO_8, NO_1}, {NO_0|NO_8, NO_3}, 
 {NO_0|NO_8, NO_5}, {NO_0|NO_8, NO_7}, 
 {NO_6|NO_2, NO_1}, {NO_6|NO_2, NO_3}, 
 {NO_6|NO_2, NO_5}, {NO_6|NO_2, NO_7}, 
 {NO_1|NO_6, NO_0}, {NO_1|NO_8, NO_2}, 
 {NO_3|NO_2, NO_0}, {NO_3|NO_8, NO_6}, 
 {NO_5|NO_0, NO_2}, {NO_5|NO_6, NO_8}, 
 {NO_7|NO_0, NO_6}, {NO_7|NO_2, NO_8}, 
 {NO_0, NO_2}, {NO_0, NO_6}, {NO_0, NO_1}, {NO_0, NO_3}, 
 {NO_2, NO_0}, {NO_2, NO_8}, {NO_2, NO_1}, {NO_2, NO_5}, 
 {NO_4, NO_0}, {NO_4, NO_8}, {NO_4, NO_3}, {NO_4, NO_7}, 
 {NO_8, NO_2}, {NO_8, NO_6}, {NO_8, NO_5}, {NO_8, NO_7}, 
 {NO_1, NO_2}, {NO_1, NO_0}, 
 {NO_3, NO_0}, {NO_3, NO_6}, 
 {NO_5, NO_2}, {NO_5, NO_8}, 
 {NO_7, NO_6}, {NO_7, NO_8}, 
 {0, NO_0}, {0, NO_2}, {0, NO_6}, {0, NO_8}, 
 {0, NO_1}, {0, NO_5}, {0, NO_3}, {0, NO_7}, 
 { 0 , 0 }, 
};


/* ox_play_tuyoi */
int ox_is_reach( LPOXGAME g, int x )
{
    int m, i;
    m = g->map_o | g->map_x;

   for(i = 0; reach[i].out != 0; i++ )
    if( Match( x , reach[i].pat )
       && (!Match( m , reach[i].out)) ) return reach[i].out;
    return 0;
}
int ox_play_tuyoi(LPOXGAME g, const char player)
{
    int xa, xb, m, xr, i;

    if(player == 'O') {
        xa = g->map_o; /* O プレイヤ優先*/
        xb = g->map_x;
    }

    if(player == 'X') {
        xa = g->map_x; /* X プレイヤ優先 */
        xb = g->map_o;
    }
    m = g->map_o | g->map_x;
    if(Match(m, (NO_0|NO_1|NO_2|
                 NO_3|NO_4|NO_5|
                 NO_6|NO_7|NO_8))) return 0; /* map full */

    /* リーチなら埋めて勝つ */
    if(xr = ox_is_reach(g, xa)) return xr;

    /* 敵リーチ 阻止 */
    if(xr = ox_is_reach(g, xb)) return xr;

   for(i = 0; pattern[i].out != 0; i++ )
    if( Match( xb , pattern[i].pat )
       && (!Match( m , pattern[i].out)) ) return pattern[i].out;

    return 0;
}

すごい面白いです。 自分はデバッグ時には思いつきませんでした。orz

割り切り方で負けちゃうんですね。 対策したいと思います。


できるとわかっていても結構骨が折れますね。大分思考のコードが変わってしまいました。はぁ~。限界!

色々考えながら、みながら、こねていった感じです。5時間くらいかかりましたよ。 データテーブルたくさん書いたので読みにくいと思います。自分でも明日になったらよめないとおもいます。orz

結果は重要でない奴は適当に端折っています。

Result:

Random Player.[36] BetterThinkPlayer.[882] Draw[82]

Random Player.[40] BetterThinkKiller.[870] Draw[90]

BetterThinkKiller.[1] BetterThinkPlayer.[0] Draw[0] ランダム要素なし

BetterThinkPlayer.[0] MoreBetterPlayer.[0] Draw[1] ランダム要素なし

BetterThinkKiller.[0] MoreBetterPlayer.[0] Draw[1] ランダム要素なし

MoreBetterPlayer.[0] BetterThinkKiller.[0] Draw[1] ランダム要素なし

MoreBetterPlayer.[953] Random Player.[0] Draw[47]

Random Player.[0] MoreBetterPlayer.[8331] Draw[1669]

システムのコードをさらにマイナーアップデートしましたが、長すぎるので省略します。アップローダがあれば融通きくんですけどねぇ。プロジェクトをZip圧縮して8kbくらいでした。おっと。これはいいか。

 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
#pragma once
#include "Player.h"
class MoreBetterPlayer:public Player{//長さ3専用っていうか最適化しちゃった。。。
public:
    char*GetName(){ return "MoreBetterPlayer.";}
    void Play(MBGame& in){
        if(in.HasEmpty() && in.Length()>3) {
            while(in.SetStone(rand()%in.Length(),rand()%in.Length(),Mark_));
            return;
        }
        //マスの重み
        short Point[]={    31,26 ,31,
                        26,100,30,
                        31,27 ,32,
        };
        int op=0;
        think(in,Point,9);
        do{
            if(!in.HasEmpty()) return;
            for(int i=0;i<9;i++){
                if(Point[i] >Point[op]){
                    op=i;
                }
            }
            Point[op]=-30000;
        }while(!in.SetStone(op%3,op/3,Mark_));
        
    }
protected:
    
    void think(MBGame& in,short Point[],int N){
        const short Posi = 10;
        const short Nega = -10;
        const short danger =999;
        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 Corner[4] = {0,2,6,8};//角
        char Hole[4] = {1,3,5,7};//変の真ん中。
        char Line2[4][3] = { {0,1,2},{0,3,6},{6,7,8},{2,5,8},};//辺のライン
        char Line3[4][2] ={ {0,1},{0,3},{1,2},{2,3}};//ラインの組み合わせ。
        char Corner2[2][2]={{0,8},{2,6}};

        for(int i=0;i<2;i++){//死にパターンつぶし2。角とその対角にコマがおかれてしまったら、さらに別の角にコマを置かれて死んでしまう。
            Mark M1 = in.At(Corner2[i][0]);
            Mark M2 = in.At(Corner2[i][1]);
            if(M1 == M2 && M1 != Mark_ && M1!= None){
                for(int j=0;j<4;j++){
                    Point[Hole[i]]+= Posi;
                }
            }
        }
        for(int i=0;i<4;i++){//死にパターンつぶし。ある角で繋がっている二辺に一個ずつコマがあって、次その接点である角にコマをおかれると死んでしまう。
            int P=0;
            for(int j=0;j<2;j++){
                for(int k=0;k<3;k++){
                    int N = Line2[Line3[i][j]][k];
                    Mark M = in.At(N);
                    if(M == Mark_ ) P++;
                    if(M != Mark_ && M != None ) P--;    
                }
            }
            if(P <= -2) {
                Point[Corner[i]] += Posi;
            }
        }
        if(in.At(1,1) == Mark_){//真ん中を自分がとってる場合、敵の4隅の重要性はほぼ他のマスと同じなので急がなくてもよい。って考えた。
            for(int i=0;i<4;i++){
                Point[Corner[i]]+=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];
                Mark M = in.At(N);
                if(M == Mark_) P++;
                if(M != None && M != Mark_) P--;
            }
            for(int j=0;j<3;j++){
                if(P == 2) Point[Lines[i][j]]+=danger+100;
                if(P == -2) Point[Lines[i][j]]+=danger-100;
            }
        }
    }
};

#6256(http://ja.doukaku.org/comment/6256/)の続きです

新たに実装したのは23行目以降
nextStates:新しい盤面のリストを作る補助関数
minimaxDecision:ミニマックス戦略
minimaxValue:ミニマックス値を計算する補助関数

マルがミニマックス戦略、バツがランダム・プレーヤーのとき、マルの9954勝0敗46分

Timing[
  result=Table[game[minimaxDecision,randomDecision],{10000}];
  Count[result,#]&/@{1,-1,0}
  ]

{65.656 Second, {9954, 0, 46}}

マルがランダム・プレーヤー、バツがミニマックス戦略のとき、バツの8024勝0敗1976分

Timing[
  result=Table[game[randomDecision,minimaxDecision],{10000}];
  Count[result,#]&/@{1,-1,0}
  ]

{68.484 Second, {0, 8024, 1976}}

マルバツともにミニマックス戦略のときは引き分け

game[minimaxDecision,minimaxDecision]

0
 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
wins={{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{3,5,7}};

isWinner[player_]:=MemberQ[Length[Intersection[player,#]]&/@wins,3]

judge[{p1_,p2_}]:=
  If[isWinner@p1,1,
    If[isWinner@p2,-1,
      If[Length@p1==5,0,Null]]]

operators[state_]:=Complement[Range@9,Flatten@state]

game[decision1_,decision2_]:=Module[{state={{},{}},result=Null},
    While[result===Null,
      If[Length@state[[1]]==Length@state[[2]],
        AppendTo[state[[1]],decision1[Sort/@state]],
        AppendTo[state[[2]],decision2[Sort/@state]]];
      result=judge@state];
    result]

randomDecision[state_]:=With[{x=operators@state},
    x[[Random[Integer,{1,Length@x}]]]]

nextStates[{p1_,p2_},ops_]:=
  Map[If[Length@p1==Length@p2,
      {Append[p1,#],p2}&,{p1,Append[p2,#]}&],ops]

Remove[minimaxDecision];
minimaxDecision[s_]:=
  Module[{ops=operators@s,vals,isMax=Length@s[[1]]==Length@s[[2]]},
    vals=minimaxValue[#,Not@isMax]&/@nextStates[s,ops];
    minimaxDecision[s]=ops[[Position[vals,If[isMax,Max,Min]@vals][[1,1]]]]]

minimaxValue[state_,isMax_]:=Module[{result=judge@state},
    If[result=!=Null,result,
      If[isMax,Max,Min][
        minimaxValue[#,Not@isMax]&/@nextStates[state,operators@state]]]]

総当りでやってみました。
ただ、1手目から総当りで評価すると時間がかかりすぎるので1~3手目は決めうちしてます。
以下の評価で場所を決めます。
・相手が勝てるパターンがない
・自分が相手よりも先に勝てる
・自分が勝てるパターンが多い
相手のリーチが2箇所になる場合の評価が別になってしまいましたが、統一的にできるのかもしれません。

結果

Aho Aho
{ result = Aho, count = 5873 }
{ result = Aho, count = 2914 }
{ result = draw, count = 1213 }
00:00:02.4866065

Aho Kasikoi
{ result = Kasikoi, count = 8790 }
{ result = draw, count = 1210 }
00:15:10.8550190

Kasikoi Aho
{ result = Kasikoi, count = 8927 }
{ result = draw, count = 1073 }
00:02:20.3465250

Kasikoi Kasikoi
{ result = draw, count = 10000 }
00:15:05.6982845
  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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;
using Strategy = System.Func<System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<System.Drawing.Point, bool>>, bool, System.Drawing.Point>;
using Board = System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<System.Drawing.Point, bool>>;
using System.Diagnostics;

namespace DoukakuMarubatsu
{
    public static class Marubatsu
    {
        internal static void Start()
        {
            var strategySet = new[] 
            { 
                new Strategy [] { Aho, Aho },
                new Strategy [] { Aho, Kasikoi },
                new Strategy [] { Kasikoi, Aho },
                new Strategy [] { Kasikoi, Kasikoi },
            };

            foreach( var set in strategySet )
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                Debug.WriteLine( string.Format( "{0} {1}", set[ 0 ].Method.Name, set[ 1 ].Method.Name ) );
                foreach( var result in from i in Enumerable.Range( 1, 10000 )
                                       let result = Start( set[ 0 ], set[ 1 ] )
                                       let dummy = Console.WriteLine( i ) is object
                                       group result by result into g
                                       let count = g.Count()
                                       orderby count descending
                                       select new { result = g.Key.HasValue ? ( g.Key.Value ? set[ 0 ].Method.Name : set[ 1 ].Method.Name ) : "draw", count } )
                    Debug.WriteLine( result );
                Debug.WriteLine( sw.Elapsed );
            }

            Console.ReadLine();
        }

        static bool? Start( Strategy getNext1, Strategy getNext2 )
        {
            var board = new Dictionary<Point, bool>();
            return new[] { new { player = true, getNext = getNext1 }, new { player = false, getNext = getNext2 } }
                .Cycle()
                .Select( p =>
                {
                    board.Add( p.getNext( board, p.player ), p.player );
                    return GetWinner( board, p.player );
                } )
                .First( winner => winner.HasValue || board.Count == 9 );
        }

        static bool? GetWinner( Board board )
        {
            return GetWinner( board, true ) ?? GetWinner( board, false );
        }
        static bool? GetWinner( Board board, bool player )
        {
            Func<Func<int, Point>, bool> check = toPoint => new[] { 0, 1, 2 }.All( i => board.Any( p => p.Key == toPoint( i ) && p.Value == player ) );
            if( new[] { 0, 1, 2 }.Any( i => check( x => new Point( x, i ) ) || check( y => new Point( i, y ) ) )
                || check( i => new Point( i, i ) )
                || check( i => new Point( 2 - i, i ) ) )
                return player;
            else
                return null;
        }

        static IEnumerable<Point> EnumeratePoints()
        {
            foreach( var y in new[] { 0, 1, 2 } )
                foreach( var x in new[] { 0, 1, 2 } )
                    yield return new Point( x, y );
        }

        static void TraceBoard( Board board )
        {
            foreach( var p in EnumeratePoints() )
                Console.Write( ToMark( board.Contains( p ) ? (bool?)board.First( pp => pp.Key == p ).Value : null ) + ( p.X == 2 ? "\n" : "" ) );
            Console.WriteLine( "----" );
        }

        static string ToMark( bool? player )
        {
            return player.HasValue ? ( player.Value ? "○" : "×" ) : "□";
        }

        static Random _rnd = new Random();
        static Point Aho( Board board, bool player )
        {
            var putable = board.EnumeratePutable().ToArray();
            return putable[ _rnd.Next( putable.Length ) ];
        }

        #region kasikoi

        static Point Kasikoi( Board board, bool player )
        {
            {//本来は不要だが総当りの回数を減らすために決めうち
                    if( board.Count() == 0 ) return new Point( 1, 1 );
                if( board.Count() == 1 ) return !board.Contains( new Point( 1, 1 ) ) ? new Point( 1, 1 ) : new Point( 0, 0 );
                if( board.Count() == 2 ) return !board.Contains( new Point( 1, 1 ) ) ? new Point( 1, 1 )
                    : new[] { 0, 2 }.SelectMany( y => new[] { 0, 2 }.Select( x => new Point( x, y ) ) ).First( kado => !board.Contains( kado ) );
            }

            //b:boardPattern d:dictionary p:player/keyValuePair/point o:otherPlayer g:group c:candidate
            var candidates0 = ( from b in EnumeratePatterns( board, Enumerable.Empty<KeyValuePair<Point, bool>>(), player )
                                let d = board.Concat( b ).ToDictionary( p => p.Key, p => p.Value )
                                let winner = GetWinner( d )
                                let count = d.Count
                                group new { winner, count } by b.First().Key into g
                                let pMin = g.Min( c => c.winner == player ? c.count : 9 )
                                let oMin = g.Min( c => c.winner == !player ? c.count : 9 )
                                let pCnt = g.Count( c => c.winner == player )
                                let oCnt = g.Count( c => c.winner == !player )
                                orderby pCnt + ( oCnt == 0 ? 1000 : 0 ) descending
                                select new { point = g.Key, pMin, oMin } ).ToArray();

            var katimenasi = candidates0.All( c => c.pMin > c.oMin );
            var candidates = candidates0.Where( c => ( katimenasi || c.pMin <= c.oMin ) && CanPut( board, c.point, player ) );
            return candidates.Count() > 0 ? candidates.First().point : board.EnumeratePutable().First();
        }

        static bool CanPut( Board board, Point point, bool player )
        {
            var virtualBoard = board.Add( point, player );
            return virtualBoard.EnumeratePutable().All( otherPlayerPoint =>
            {
                var virtualBoard2 = virtualBoard.Add( otherPlayerPoint, !player );
                //相手が次の次で勝てるポイント一覧
                    var list = virtualBoard2.EnumeratePutable()
                    .Where( otherPlayerPoint2 => GetWinner( virtualBoard2.Add( otherPlayerPoint2, !player ), !player ) == !player );
                //相手が勝てるポイントが複数あってもそこに自分が置いて勝てるなら問題なし
                    return list.Count() < 2 || list.Any( p => GetWinner( virtualBoard2.Add( p, player ), player ) == player );
            } );
        }

        static IEnumerable<Board> EnumeratePatterns( Board board, Board points, bool player )
        {
            var putable = board.EnumeratePutable().Except( points.Select( pp => pp.Key ) );
            if( putable.Count() == 0 || GetWinner( board ).HasValue )
                yield return points;
            else
                foreach( var p in putable )
                    foreach( var points2 in EnumeratePatterns( board.Add( p, player ), points.Add( p, player ), !player ) )
                        yield return points2;
        }

        #endregion

        #region extension

        public static IEnumerable<Point> EnumeratePutable( this Board board )
        {
            return EnumeratePoints().Except( board.Select( pp => pp.Key ) );
        }

        public static Board Add( this Board board, Point p, bool player )
        {
            return board.Concat( Enumerable.Repeat( new KeyValuePair<Point, bool>( p, player ), 1 ) );
        }

        public static bool Contains( this Board board, Point point )
        {
            return board.Any( p => p.Key == point );
        }

        public static IEnumerable<T> Cycle<T>( this IEnumerable<T> src )
        {
            while( true )
                foreach( T t in src )
                    yield return t;
        }

        #endregion
    }
}

C# 2.0で。
ダブルリーチになるところを探して狙う/防ぐようにしています。
 賢 vs 乱 ≒ 97: 0: 3
 乱 vs 賢 ≒  0:86:14
結構勝ってると思いますが、#6257のミニマックス戦略を用いた「先攻勝率99%」には負けた・・・。
ダブルリーチをチェックしても、例のダブルダブルリーチ(先攻が斜め角に置いていく手)は防げなかったので別対応しています。
  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
using System;
using System.Collections.Generic;
using System.Text;

namespace MaruBatu
{
    enum Cell { Empty, Maru, Batu, Draw };
    //盤面
    class Board
    {
        Cell[] cells;
        int fillCount;
        public int FillCount {
            get {
                return this.fillCount;
            }
        }
        public Board() {
            cells = new Cell[9];
        }
        public void Clear() {
            for (int i = 0; i < 9; i++) {
                cells[i] = Cell.Empty;
            }
            fillCount = 0;
        }
        public Cell this[int index] {
            get {
                return cells[index];
            }
            set {
                if (value == Cell.Empty && cells[index] != Cell.Empty) {
                    fillCount--;
                } else if (value != Cell.Empty && cells[index] == Cell.Empty) {
                    fillCount++;
                }
                cells[index] = value;
            }
        }
        public Cell Winner {
            get {
                for (int x = 0; x < 3; x++) {
                    if (cells[x] != Cell.Empty
                        && cells[x + 3] == cells[x]
                        && cells[x + 6] == cells[x]) {
                        return cells[x];
                    }
                }
                for (int y = 0; y < 9; y += 3) {
                    if (cells[y] != Cell.Empty
                        && cells[y + 1] == cells[y]
                        && cells[y + 2] == cells[y]) {
                        return cells[y];
                    }
                }
                if (cells[4] != Cell.Empty) {
                    if (cells[0] == cells[4]
                        && cells[8] == cells[4]) {
                        return cells[4];
                    }
                    if (cells[2] == cells[4]
                        && cells[6] == cells[4]) {
                        return cells[4];
                    }
                }
                if (fillCount == 9) {
                    return Cell.Draw;
                }
                return Cell.Empty;
            }
        }
        public override String ToString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                if (cells[i] != Cell.Empty) {
                    sb.Append(cells[i] == Cell.Maru ? "O" : "X");
                    sb.Append(" ");
                } else {
                    sb.Append(i + 1);
                    sb.Append(" ");
                }
                if ((i % 3) == 2)
                    sb.Append("\n");
            }
            return sb.ToString();
        }
    }
    //プレイヤー型
    interface IPlayer
    {
        int GetNext(Board brd);
        String Name {
            get;
            set;
        }
    }
    //ランダムプレイヤー
    class RandomPlayer : IPlayer
    {
        Random rand;
        public RandomPlayer() {
            rand = new Random();
        }
        public int GetNext(Board brd) {
            int random = rand.Next(9 - brd.FillCount);
            for (int i = 0; i < 9; i++) {
                if (brd[i] == Cell.Empty) {
                    if (random == 0) {
                        return i;
                    }
                    random--;
                }
            }
            throw new ApplicationException();
        }
        public string Name {
            get { return "ランダムプレイヤー"; }
            set { }
        }
    }
    //賢いプレイヤー
    class WisePlayer : IPlayer
    {
        Cell self;
        public WisePlayer(Cell self) {
            this.self = self;
        }
        int[] priority = new int[] { 4, 0, 2, 6, 8, 1, 3, 5, 7 };
        protected virtual int[] Priority {
            get {
                return priority;
            }
        }
        public int GetNext(Board brd) {
            int reach = -1;
            Cell enemy = (self == Cell.Maru ? Cell.Batu : Cell.Maru);
            //自分のリーチを検索
            reach = getReach(brd, self);
            if (reach != -1) {
                return reach;   //勝ちに行く
            }

            //相手のリーチを検索
            reach = getReach(brd, enemy);
            if (reach != -1) {
                return reach;   //防ぐ
            }

            if (self == Cell.Maru) {
                //自分の二重リーチを探す(先攻)
                reach = getDoubleReach(brd, self);
                if (reach != -1) {
                    return reach;   //ゲット!
                }
            } else {
                //対角ダブダブチェック
                if (brd[4] == self
                    && ((brd[0] == enemy && brd[8] == enemy)
                         || (brd[2] == enemy && brd[6] == enemy))) {
                    //辺をとる
                    foreach (int cell in new int[] { 1, 3, 5, 7 }) {
                        if (brd[cell] == Cell.Empty) {
                            return cell;
                        }
                    }
                }

                //相手の二重リーチを探す(後攻)
                reach = getDoubleReach(brd, enemy);
                if (reach != -1) {
                    return reach;   //させねぇ!
                }
            }

            foreach (int cell in Priority) {
                if (brd[cell] == Cell.Empty) {
                    return cell;
                }
            }

            throw new ApplicationException();   //ここまで来ない
        }
        int getDoubleReach(Board brd, Cell target) {
            int reach = -1;
            for (int i = 0; i < 9 && reach == -1; i++) {
                if (brd[i] != Cell.Empty)
                    continue;
                brd[i] = target;  //仮置き
                int reach1 = getReach(brd, target);
                if (reach1 != -1) {
                    brd[reach1] = Cell.Draw;    //リーチをつぶす
                    int reach2 = getReach(brd, target);
                    if (reach2 != -1) {
                        reach = i;
                    }
                    brd[reach1] = Cell.Empty;
                }
                brd[i] = Cell.Empty;
            }
            return reach;
        }
        int[][] lines = new int[][] {
                new int[] {0,1,2},new int[] {3,4,5},new int[] {6,7,8},    //横
                new int[] {0,3,6},new int[] {1,4,7},new int[] {2,5,8},    //縦
                new int[] {0,4,8},new int[] {2,4,6}                       //斜め
            };
        int getReach(Board brd, Cell target) {
            int[] cellCount = new int[3];   //自分、相手、空き
            foreach (int[] line in lines) {
                int reach = checkReach(brd, target, line);
                if (reach != -1) {
                    return reach;
                }
            }

            return -1;
        }
        int checkReach(Board brd, Cell target, int[] cells) {
            int targetCount = 0, emptyCount = 0;
            int empty = -1;
            foreach (int cell in cells) {
                if (brd[cell] == target) {
                    targetCount++;
                } else if (brd[cell] == Cell.Empty) {
                    emptyCount++;
                    empty = cell;
                }
            }
            if (targetCount == 2
                && emptyCount == 1) {
                return empty;
            } else {
                return -1;
            }
        }
        public virtual string Name {
            get { return "賢いプレイヤー"; }
            set { }
        }
    }
    //人間プレイヤー
    class HumanPlayer : IPlayer
    {
        public int GetNext(Board brd) {
            Console.WriteLine("");
            Console.WriteLine(brd);
            while (true) {
                Console.Write("次の手を選んでください:");
                String input = Console.ReadLine();
                int cell = -1;
                try {
                    cell = int.Parse(input) - 1;
                } catch {
                }
                if (cell < 0 || 8 < cell) {
                    continue;
                } else if (brd[cell] != Cell.Empty) {
                    Console.WriteLine("そのマスは空いてません");
                    continue;
                } else {
                    return cell;
                }
            }
        }
        public string Name {
            get { return "あなた"; }
            set { }
        }
    }
    //1試合
    class Game
    {
        Board board;
        IPlayer[] players;
        int gameCount;
        const int Win = 0;
        const int Lose = 1;
        const int Draw = 2;
        int[,] score;

        public Game(IPlayer p1, IPlayer p2) {
            board = new Board();
            players = new IPlayer[2] { p1, p2 };
            score = new int[2, 3];
            gameCount = 0;
        }
        public string Result {
            get {
                String ret = String.Format("{0}試合の結果\n", gameCount);
                for (int i = 0; i < 2; i++) {
                    ret += String.Format(
                        "{0:30} {1}勝{2}敗{3}分\n",
                        players[i].Name,
                        score[i, Win], score[i, Lose], score[i, Draw]);
                }
                return ret;
            }
        }
        public void Play(bool showResult) {
            int turn = 0;
            gameCount++;
            board.Clear();

            Cell winner;
            while ((winner = board.Winner) == Cell.Empty) {
                int next = players[turn].GetNext(board);
                board[next] = (turn % 2) == 0 ? Cell.Maru : Cell.Batu;
                turn = (turn + 1) % 2;
            }
            switch (winner) {
                case Cell.Draw:
                    score[0, Draw]++;
                    score[1, Draw]++;
                    break;
                case Cell.Maru:
                    score[0, Win]++;
                    score[1, Lose]++;
                    break;
                case Cell.Batu:
                    score[0, Lose]++;
                    score[1, Win]++;
                    break;
            }

            if (showResult) {
                Console.WriteLine(board);
                Console.WriteLine(Result);
            }
        }
    }
    class Program
    {
        static void Main(string[] args) {
            //Game game = new Game(new RandomPlayer(), new RandomPlayer());
            //            Game game = new Game(new WisePlayer(Cell.Maru), new HumanPlayer());
            //            Game game = new Game(new RandomPlayer(), new HumanPlayer());
                        Game game = new Game(new RandomPlayer(), new WisePlayer(Cell.Batu));
            //            Game game = new Game(new WisePlayer(Cell.Maru), new RandomPlayer());
            //            Game game = new Game(new WisePlayer(Cell.Maru), new WisePlayer(Cell.Batu));
            for (int i = 0; i < 100000; i++) {
                //                game.Play(true);
                game.Play(false);
            }
            Console.WriteLine(game.Result);
            Console.ReadLine();
        }
    }
}

評価方法を以下のようにすると先行の勝率が98%台に上がりました。
orderby pMin, pCnt descending, oCnt, oMin descending

後手無配までは行ってませんが...

  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
module Main where

import Char
import Control.Monad
import Control.Monad.State
import Data.Array.IArray
import Data.List
import Data.Maybe
import Data.Function
import System.Random

type Summary = Array Int Int
type Board = Array Int Int
type Idx = Int
type Token = Int
tkX = 1 :: Token
tkO = 2 :: Token

doIf :: Bool -> (a -> a) -> a -> a
doIf True f a = f a
doIf False _ a = a

mapArray array f idxs = array // ([(x, f (array ! x)) | x <- idxs])

idxSumIdx = [[0, 3, 6], [1, 3], 
    [2, 3, 7], [0, 4], [1, 4, 6, 7], 
    [2, 4], [0, 5, 7], [1, 5], [2, 5, 6]] 

idxToSumIdx idx = idxSumIdx!!idx

type TTT = ((Summary, Summary), Board, Int, Token)

turn :: TTT -> Idx -> TTT
turn (sum@(xSummary, oSummary), board, i, tk) idx
    | tk == tkX = ((sumMe', sumOpp), board', i + 1, tkO)
    | otherwise = ((sumOpp, sumMe'), board', i + 1, tkX)
    where
        sumMe' = mapArray sumMe (+ 1) (idxToSumIdx idx)
        (sumMe, sumOpp) = doIf (tk == tkO) (swap) sum
        board' = board // [(idx, tk)]
        swap (a, b) = (b, a)
        
won :: TTT -> Maybe Token
won ((xSummary, oSummary), _, _, _)
    | elem 3 (elems xSummary) = Just tkX
    | elem 3 (elems oSummary) = Just tkO
    | otherwise = Nothing

availableMoves :: TTT -> [Idx]
availableMoves (_, board, _, _) = map (fst) $ filter ((==0).snd) $ assocs board

lineScore :: (Summary, Summary) -> Int -> Int
lineScore (sumSelf, sumEn) iLine = check (sumSelf!iLine) (sumEn!iLine)
    where
        check 2 0 = 10000 -- can win in 1 attempts (2 self & no enemy)
        check 0 2 = 1000 -- can lose in 1 attempts (2 enemy & no self)
        check 0 1 = 100 -- can lose in 2 attempts (1 enemy & no self)
        check 1 0 = 10 -- can win in 2 attempts (1 self & no enemy)
        check 0 0 = 1 -- can win in 3 attempts (empty)
        check _ _ = 0 -- can't win nor lose (!0 enemy & !0 self)

scoreCell :: (Summary, Summary) -> Idx -> Int
scoreCell summaries idx = sum $ map (lineScore summaries) $ idxToSumIdx idx

type Player = TTT -> IO TTT

smartPlayer :: Player
smartPlayer ttt@(sum, _, _, tk) = return $ turn ttt bestMove
    where
        bestMove = snd $ maximumBy (compare `on` fst) $ zip (map (scoreCell sum) avm) avm
        avm = availableMoves ttt

randomPlayer :: Player
randomPlayer ttt = do
        idx <- bestMove
        return $ turn ttt idx
    where
        bestMove = randomChoice $ availableMoves ttt
        randomChoice xs = do
            idx <- getStdRandom $ randomR (0, (length xs) - 1)
            return $ xs!!idx

type STTT = StateT TTT IO ()

playTurn :: Player -> STTT
playTurn p = do
    ttt@(_, _, _, tk) <- get
    ttt' <- liftIO (p ttt)
    put ttt'
    liftIO (evaluate ttt')
    where
        evaluate :: TTT -> IO ()
        evaluate ttt''
            | isJust $ won ttt'' = fail (show $ fromJust $ won ttt'')
            | otherwise = return ()

play :: [Player] -> IO Int
play players =  do
    catch doGame catcher 
    where
        initialTTT     = ((initialSummary, initialSummary), initialBoard, 0, tkX)
        initialSummary = listArray (0, 7) $ repeat 0
        initialBoard   = listArray (0, 8) $ repeat 0

        
        doGame = do
            evalStateT (mapM playTurn players) initialTTT
            return 0

        catcher :: IOError -> IO Int
        catcher e
            | e == (userError "1") = return 1
            | e == (userError "2") = return 2
            | otherwise = return 0

main = do
    putStrLn "[draw, 1st win, 2nd win]"
    tries <- replicateM 10000 (play players)
    print $ elems $ foldl (\rg idx -> mapArray rg (+1) [idx]) rgSum tries
    where
        rgSum :: Array Int Int
        rgSum = listArray (0, 2) $ repeat 0
--        players = take 9 $ cycle [smartPlayer, smartPlayer]
        players = take 9 $ cycle [randomPlayer, smartPlayer]
--        players = take 9 $ cycle [smartPlayer, randomPlayer]
--        players = take 9 $ cycle [randomPlayer, randomPlayer]

無配→無敗...後から修正できないんでしたっけ...


 Wikipediaの完勝手順を参考に,以下の形で実装してみました。

1. 3マス揃う場合には揃える
2. 敵方にリーチが掛かっている場合には阻止する
3. ダブルリーチが掛けられる場合には掛ける
4. 敵方がダブルリーチを掛けられる場合には,以下の方法で阻止する
4-1. 敵方のダブルリーチを阻止できる形でリーチを掛けられる場合にはリーチを掛ける
4-2. 4-1以外の場合は,直接的にダブルリーチを阻止する
5. 中央が開いていれば中央に置く
6. 敵方の角の反対が空いていれば,その角に置く
7. 角が空いていれば角に置く
8. 1~7のいずれにも該当しない場合には,空いているマスに置く

 以下実行結果です。

1> c(tic_tac_toe).
{ok,tic_tac_toe}
2> tic_tac_toe:start().
first:0,second:8762,draw:1238
ok
3> tic_tac_toe:start({fun tic_tac_toe:clever_choice/2,fun tic_tac_toe:random_choice/2}).
first:9573,second:0,draw:427
ok
4> tic_tac_toe:start({fun tic_tac_toe:clever_choice/2,fun tic_tac_toe:clever_choice/2}).
first:0,second:0,draw:10000
ok
  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
-module(tic_tac_toe).
-import(io).
-import(lists).
-import(random).
-export([start/0,start/1,random_choice/2,clever_choice/2]).

create_board() -> lists:map(fun(_) -> 0 end,lists:seq(1,9,1)).

enemy(P) -> P rem 2 + 1.

move(B,1,{C,_}) -> move(B,1,C);
move(B,2,{_,C}) -> move(B,2,C);
move(B,P,C) ->
    PS = C(B,P),
    lists:sublist(B,PS - 1) ++ [P|lists:sublist(B,PS + 1,length(B) - PS)].

check_pattern() ->
    lists:map(fun(X) -> lists:seq(X,X+6,3) end, lists:seq(1,3,1)) ++
    lists:map(fun(X) -> lists:seq(X,X+2,1) end, lists:seq(1,7,3)) ++
    [lists:seq(1,9,4),lists:seq(3,7,2)].

check(B,P) ->
    lists:any(
        fun(PT) ->
            lists:all(
                fun(ST) -> ST == P end,
                lists:map(fun(X) -> lists:nth(X,B) end, PT)
            )
        end,
        check_pattern()
    ).

process(B,P,C) ->
    BN = move(B,P,C),
    R = check(BN,P),
    D = lists:all(fun(ST) -> ST /= 0 end, BN),
    if
        R -> P;
        D -> 0;
        true -> process(BN, enemy(P), C)
    end.

process(C) -> process(create_board(),1,C).

random_choice(B,_) ->
    S = lists:map(fun({PS,_}) -> PS end, lists:filter(fun({_,X}) -> X == 0 end, lists:zip(lists:seq(1,length(B),1),B))),
    lists:nth(random:uniform(length(S)),S).

will_complete(B,P,PL) ->
    lists:filter(
        fun(SL) ->
            (length(lists:filter(fun({_,S}) -> S == P end, SL)) == 2) and
            (length(lists:filter(fun({_,S}) -> S == 0 end, SL)) == 1)
        end,
        lists:map(
            fun(PP) -> lists:map(fun(PS) -> {PS,lists:nth(PS,B)} end, PP) end,
            PL
        )
    ).

proposed_complete(B,P,PL) ->
    lists:map(
        fun(SL) ->
            {PS,_} = lists:nth(1, lists:filter(fun({_,S}) -> S == 0 end, SL)),
            PS
        end,
        will_complete(B,P,PL)
    ).

check_fork(B,P) -> length(will_complete(B,P,check_pattern())) >= 2.

lookahead(F,B,P) ->
    lists:filter(
        F,
        lists:map(
            fun({PT,_}) ->{PT,lists:sublist(B,PT - 1)++[P|lists:sublist(B,PT + 1,length(B) - PT)]} end,
            lists:filter(fun({_,S}) -> S == 0 end, lists:zip(lists:seq(1,9,1),B))
        )
    ).

proposed_fork(B,P,_) ->
    lists:map(
        fun({PS,_}) -> PS end,
        lookahead(fun({_,BP}) -> check_fork(BP,P) end,B,P)
    ).

proposed_block_fork(B,P,PL) ->
    FL = proposed_fork(B,enemy(P),PL),
    F = length(FL),
    if
        F == 0 -> [];
        true ->
            lists:map(
                fun({PS,_}) -> PS end,
                lookahead(
                    fun({_,BP}) ->
                        (length(lists:subtract(proposed_complete(BP,P,check_pattern()),FL)) > 0) or
                        (length(proposed_fork(BP,enemy(P),[])) == 0)
                    end,
                    B,
                    P
                )
            )
    end.

proposed_opposite(B,P,PL) ->
    lists:filter(
        fun(PS) -> lists:nth(PS,B) == 0 end,
        lists:map(
            fun({EP,_}) ->
                {_,OP} =
                    lists:nth(1,
                        lists:filter(
                            fun({CP,_}) -> CP == EP end,
                            lists:zip(PL,lists:map(fun(X) -> 10 -X end, PL))
                        )
                    ),
                OP
            end,
            lists:filter(
                fun({_,S}) -> S == enemy(P) end,
                lists:zip(PL,lists:map(fun(PT) -> lists:nth(PT,B) end, PL))
            )
        )
    ).

proposed_space(B,_,PL) -> lists:filter(fun(PS) -> lists:nth(PS,B) == 0 end, PL).

clever_choice(B,P) ->
    lists:nth(
        1,
        lists:append(
            lists:map(
                fun({F,PP,PL}) -> F(B,PP,PL) end,
                [    {fun proposed_complete/3,P,check_pattern()},
                    {fun proposed_complete/3,enemy(P),check_pattern()},
                    {fun proposed_fork/3,P,[]},
                    {fun proposed_block_fork/3,P,[]},
                    {fun proposed_space/3,0,[5]},
                    {fun proposed_opposite/3,P,[1,3,7,9]},
                    {fun proposed_space/3,0,[1,3,7,9]},
                    {fun proposed_space/3,0,[2,4,6,8]}
                ]
            )
        )
    ).

start(C) ->
    R = lists:map(fun(_) -> process(C) end,lists:seq(1,10000,1)),
    io:format("first:~w,second:~w,draw:~w~n",lists:map(fun(P) -> length(lists:filter(fun(X) -> X == P end, R)) end,[1,2,0])).

start() -> start({fun random_choice/2,fun clever_choice/2}).

 Wikipediaの完勝手順を参考に,以下の形で実装してみました。

1. 3マス揃う場合には揃える
2. 敵方にリーチが掛かっている場合には阻止する
3. ダブルリーチが掛けられる場合には掛ける
4. 敵方がダブルリーチを掛けられる場合には,以下の方法で阻止する
4-1. 敵方のダブルリーチを阻止できる形でリーチを掛けられる場合にはリーチを掛ける
4-2. 4-1以外の場合は,直接的にダブルリーチを阻止する
5. 中央が開いていれば中央に置く
6. 敵方の角の反対が空いていれば,その角に置く
7. 角が空いていれば角に置く
8. 1~7のいずれにも該当しない場合には,空いているマスに置く

 以下実行結果です。

1> c(tic_tac_toe).
{ok,tic_tac_toe}
2> tic_tac_toe:start().
first:0,second:8762,draw:1238
ok
3> tic_tac_toe:start({fun tic_tac_toe:clever_choice/2,fun tic_tac_toe:random_choice/2}).
first:9573,second:0,draw:427
ok
4> tic_tac_toe:start({fun tic_tac_toe:clever_choice/2,fun tic_tac_toe:clever_choice/2}).
first:0,second:0,draw:10000
ok
  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
-module(tic_tac_toe).
-import(io).
-import(lists).
-import(random).
-export([start/0,start/1,random_choice/2,clever_choice/2]).

create_board() -> lists:map(fun(_) -> 0 end,lists:seq(1,9,1)).

enemy(P) -> P rem 2 + 1.

move(B,1,{C,_}) -> move(B,1,C);
move(B,2,{_,C}) -> move(B,2,C);
move(B,P,C) ->
    PS = C(B,P),
    lists:sublist(B,PS - 1) ++ [P|lists:sublist(B,PS + 1,length(B) - PS)].

check_pattern() ->
    lists:map(fun(X) -> lists:seq(X,X+6,3) end, lists:seq(1,3,1)) ++
    lists:map(fun(X) -> lists:seq(X,X+2,1) end, lists:seq(1,7,3)) ++
    [lists:seq(1,9,4),lists:seq(3,7,2)].

check(B,P) ->
    lists:any(
        fun(PT) ->
            lists:all(
                fun(ST) -> ST == P end,
                lists:map(fun(X) -> lists:nth(X,B) end, PT)
            )
        end,
        check_pattern()
    ).

process(B,P,C) ->
    BN = move(B,P,C),
    R = check(BN,P),
    D = lists:all(fun(ST) -> ST /= 0 end, BN),
    if
        R -> P;
        D -> 0;
        true -> process(BN, enemy(P), C)
    end.

process(C) -> process(create_board(),1,C).

random_choice(B,_) ->
    S = lists:map(fun({PS,_}) -> PS end, lists:filter(fun({_,X}) -> X == 0 end, lists:zip(lists:seq(1,length(B),1),B))),
    lists:nth(random:uniform(length(S)),S).

will_complete(B,P,PL) ->
    lists:filter(
        fun(SL) ->
            (length(lists:filter(fun({_,S}) -> S == P end, SL)) == 2) and
            (length(lists:filter(fun({_,S}) -> S == 0 end, SL)) == 1)
        end,
        lists:map(
            fun(PP) -> lists:map(fun(PS) -> {PS,lists:nth(PS,B)} end, PP) end,
            PL
        )
    ).

proposed_complete(B,P,PL) ->
    lists:map(
        fun(SL) ->
            {PS,_} = lists:nth(1, lists:filter(fun({_,S}) -> S == 0 end, SL)),
            PS
        end,
        will_complete(B,P,PL)
    ).

check_fork(B,P) -> length(will_complete(B,P,check_pattern())) >= 2.

lookahead(F,B,P) ->
    lists:filter(
        F,
        lists:map(
            fun({PT,_}) ->{PT,lists:sublist(B,PT - 1)++[P|lists:sublist(B,PT + 1,length(B) - PT)]} end,
            lists:filter(fun({_,S}) -> S == 0 end, lists:zip(lists:seq(1,9,1),B))
        )
    ).

proposed_fork(B,P,_) ->
    lists:map(
        fun({PS,_}) -> PS end,
        lookahead(fun({_,BP}) -> check_fork(BP,P) end,B,P)
    ).

proposed_block_fork(B,P,PL) ->
    FL = proposed_fork(B,enemy(P),PL),
    F = length(FL),
    if
        F == 0 -> [];
        true ->
            lists:map(
                fun({PS,_}) -> PS end,
                lookahead(
                    fun({_,BP}) ->
                        (length(lists:subtract(proposed_complete(BP,P,check_pattern()),FL)) > 0) or
                        (length(proposed_fork(BP,enemy(P),[])) == 0)
                    end,
                    B,
                    P
                )
            )
    end.

proposed_opposite(B,P,PL) ->
    lists:filter(
        fun(PS) -> lists:nth(PS,B) == 0 end,
        lists:map(
            fun({EP,_}) ->
                {_,OP} =
                    lists:nth(1,
                        lists:filter(
                            fun({CP,_}) -> CP == EP end,
                            lists:zip(PL,lists:map(fun(X) -> 10 -X end, PL))
                        )
                    ),
                OP
            end,
            lists:filter(
                fun({_,S}) -> S == enemy(P) end,
                lists:zip(PL,lists:map(fun(PT) -> lists:nth(PT,B) end, PL))
            )
        )
    ).

proposed_space(B,_,PL) -> lists:filter(fun(PS) -> lists:nth(PS,B) == 0 end, PL).

clever_choice(B,P) ->
    lists:nth(
        1,
        lists:append(
            lists:map(
                fun({F,PP,PL}) -> F(B,PP,PL) end,
                [    {fun proposed_complete/3,P,check_pattern()},
                    {fun proposed_complete/3,enemy(P),check_pattern()},
                    {fun proposed_fork/3,P,[]},
                    {fun proposed_block_fork/3,P,[]},
                    {fun proposed_space/3,0,[5]},
                    {fun proposed_opposite/3,P,[1,3,7,9]},
                    {fun proposed_space/3,0,[1,3,7,9]},
                    {fun proposed_space/3,0,[2,4,6,8]}
                ]
            )
        )
    ).

start(C) ->
    R = lists:map(fun(_) -> process(C) end,lists:seq(1,10000,1)),
    io:format("first:~w,second:~w,draw:~w~n",lists:map(fun(P) -> length(lists:filter(fun(X) -> X == P end, R)) end,[1,2,0])).

start() -> start({fun random_choice/2,fun clever_choice/2}).

 間違えてFORTRANを選択してしまいました...。

先攻の場合は、リーチされてなければ、できるだけ角を取ってダブルリーチを狙う戦略です。
後攻の場合は、相手の初手に合わせて戦略を変えています。
思った以上の勝率でちょっとビックリしました。

実行結果:
arc> (nplay-ox 10000 smart-player)
smart-player win: 9919
random-player win: 0
draw: 81
nil

arc> (nplay-ox 10000 random-player)
smart-player win: 8428
random-player win: 0
draw: 1572
nil
  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
(= lines '((1 2 3) (1 4 7) (1 5 9) (2 5 8) (3 5 7) (3 6 9) (4 5 6) (7 8 9)))

(def lsets<= (s1 s2) (all [mem _ s2] s1))

(def reach? (line mark pool)
  (let marked (map [if (mem _ mark) t nil] line)
    (if (and (is (count nil marked) 1) (mem (line (pos nil marked)) pool))
          (line (pos nil marked))
        nil)))

(def random-player (smark rmark pool)
  (if (is pool nil) 'd
      (withs (picked (random-elt pool) rm (cons picked rmark) rp (rem picked pool))
        (if (some [lsets<= _ rm] lines) 'r
            (smart-player smark rm rp)))))

(def smart-player (smark rmark pool)
  (if (is pool nil) 'd
      (let rr (rem nil (map [reach? _ rmark pool] lines))
        (if (isnt nil (rem nil (map [reach? _ smark pool] lines))) 's
            (isnt nil rr) (random-player (cons (car rr) smark) rmark (rem (car rr) pool))
            (odd (len pool)) (senkou smark rmark pool)
            (koukou smark rmark pool)))))

(def senkou (smark rmark pool)
  (if (is (len pool) 9) (random-player (cons 1 smark) rmark (rem 1 pool))
      (is (len pool) 7)
        (let m (if (lsets<= '(2 3) pool) 3 7)
          (random-player (cons m smark) rmark (rem m pool)))
      (is (len pool) 1) 'd
      (let m (if (lsets<= '(4 7) pool) 7 9)
        (random-player (cons m smark) rmark (rem m pool)))))

(def koukou (smark rmark pool)
  (let rf (last rmark)
    (if (mem rf '(1 3 7 9))
          (pat1379 smark rmark pool)
        (mem rf '(2 4))
          (pat24 smark rmark pool)
        (mem rf '(6 8))
          (pat68 smark rmark pool)
        (pat5 smark rmark pool))))

(def pat1379 (smark rmark pool)
  (if (is (len pool) 8) 
        (random-player (cons 5 smark) rmark (rem 5 pool))
      (is (len pool) 6)
        (let m (if (some [mem _ rmark] '(2 6)) 3
                   (some [mem _ rmark] '(4 8)) 7 2)
          (random-player (cons m smark) rmark (rem m pool)))
      (is (len pool) 4)
        (let m (if (some [mem _ rmark] '(2 8)) 4 2)
          (random-player (cons m smark) rmark (rem m pool)))
      (let picked (random-elt pool)
        (random-player (cons picked smark) rmark (rem picked pool)))))

(def pat24 (smark rmark pool)
  (if (is (len pool) 8)
        (random-player (cons 1 smark) rmark (rem 1 pool))
      (is (len pool) 6)
        (let m (if (lsets<= '(2 9) rmark) 7
                   (lsets<= '(4 9) rmark) 3 5)
          (random-player (cons m smark) rmark (rem m pool)))
      (is (len pool) 4)
        (let m (if (lsets<= '(2 4 9) rmark) (if (mem 5 pool) 5 (mem 3 pool) 3 7)
                   (lsets<= '(2 5 9) rmark) 7
                   (lsets<= '(5 4 9) rmark) 3)
          (random-player (cons m smark) rmark (rem m pool)))
      (let picked (random-elt pool)
        (random-player (cons picked smark) rmark (rem picked pool))))))

(def pat68 (smark rmark pool)
  (if (is (len pool) 8)
        (random-player (cons 9 smark) rmark (rem 9 pool))
      (is (len pool) 6)
        (let m (if (lsets<= '(1 6) rmark) 7
                   (lsets<= '(1 8) rmark) 3 5)
          (random-player (cons m smark) rmark (rem m pool)))
      (is (len pool) 4)
        (let m (if (lsets<= '(1 6 8) rmark) (if (mem 5 pool) 5 (mem 3 pool) 3 7)
                   (lsets<= '(1 5 8) rmark) 3
                   (lsets<= '(1 5 6) rmark) 7)
          (random-player (cons m smark) rmark (rem m pool)))
      (let picked (random-elt pool)
        (random-player (cons picked smark) rmark (rem picked pool))))))

(def pat5 (smark rmark pool)
  (if (is (len pool) 8) 
        (random-player (cons 1 smark) rmark (rem 1 pool))
      (is (len pool) 6)
        (random-player (cons 3 smark) rmark (rem 3 pool))
      (let picked (random-elt pool)
        (random-player (cons picked smark) rmark (rem picked pool)))))

(def nplay-ox (n sente)
  (let wl (map (fn (_) (sente nil nil (range 1 9))) (range 1 n))
    (prn "smart-player win: " (count 's wl))
    (prn "random-player win: " (count 'r wl))
    (prn "draw: " (count 'd wl))
    nil))

4つの戦略(どのように石を置くか)を作りました:
  1. put_stone_random ... ランダムに置く。
  2. ps_prevent_losing ... リーチをかけられてるなら、防ぐ。さもなくば1.の戦略をとる。
  3. ps_grasp_chance ...リーチをかけてるなら、そこにおいてゲームに勝つ。さもなくば2.の戦略をとる。
  4. ps_smart ...
    リーチをかけてるなら、そこにおいてゲームに勝つ。
    リーチをかけられてるなら、防ぐ。
    さもなくば、可能な限り、ダブルリーチを仕掛けに行く。

ps_smart を書くために、マルバツゲームを手で解きました。
各盤面に対する最善手を %ptn_pos_h に押し込めました。
蛇足:%ptn_pos_h を調整することで、 ps_smart の強さを調整できます。

実行結果: perl marubatsu.pl
***** ps_smart vs put_stone_random *****
game 1..10000
D=>115 o=>9885 
***** put_stone_random vs ps_smart *****
game 10001..20000
D=>2373 x=>7627 
***** ps_smart vs ps_smart *****
game 20001..20100
D=>100 
  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
$board = [map {[map {'-'} 0..2]} 0..2];

sub game {
    clear($board);
    game_loop(@_);
}
sub game_loop {
    my ($player1, $player2) = @_;
    my $w;
    $player1->{put_stone}($player1->{stone});
    if ($w=check($board)) { return $w; }
    game_loop($player2,$player1);
}

sub put_stone_random {
    my $stone = shift;
    while (1) {
    my($r,$c) = (int rand @$board, int rand @$board);
    if (0<=$r and $r<@$board and
        0<=$c and $c<@$board and
        $board->[$r][$c] eq '-') {
        $board->[$r][$c] = $stone;
        last;
    }
    }
}
sub ps_prevent_losing { # ps :abbrev: put_stone
    my $stone = shift;
    my($r,$c) = pos_oppreach($board,$stone);
    if (defined($r) and defined($c)) {
    $board->[$r][$c] = $stone;
    } else {
    put_stone_random($stone);
    }
}
sub ps_grasp_chance {
    my $stone = shift;
    my($r,$c) = pos_oppreach($board,oppstone($stone));
    if (defined($r) and defined($c)) {
    $board->[$r][$c] = $stone;
    } else {
    ps_prevent_losing($stone);
    }
}
sub ps_smart {
    my $stone = shift;
    # ps_grasp_chance
    my($r,$c) = pos_oppreach($board,oppstone($stone));
    if (defined($r) and defined($c)) {
    $board->[$r][$c] = $stone;
    return;
    }
    # ps_prevent_losing
    ($r,$c) = pos_oppreach($board,$stone);
    if (defined($r) and defined($c)) {
    ps_prevent_losing($stone);
    return;
    }
    # attack dreach # dreach :abbrev: double reach
    ($r,$c) = pos_smart($board,$stone);
    if (defined($r) and defined($c)) {
    $board->[$r][$c] = $stone;
    return;
    }
    put_stone_random($stone);
}

sub pos_oppreach {
    my($board,$stone) = @_;
    my($r,$c);
    ($r,$c) = pos_oppreach_row($board,$stone);
    if (defined($r) and defined($c)) { return ($r,$c); }
    ($r,$c) = pos_oppreach_column($board,$stone);
    if (defined($r) and defined($c)) { return ($r,$c); }
    ($r,$c) = pos_oppreach_crossline($board,$stone);
    if (defined($r) and defined($c)) { return ($r,$c); }
    (undef, undef)
}
sub pos_oppreach_row {
    my($board,$stone) = @_;
    my @board_strs = join0s($board);
    for (0..(@$board-1)) {
    my $i = index_oppreach($board_strs[$_], $stone);
    if (defined($i)) {
        return ($_, $i);
    }
    }
    (undef, undef);
}
sub pos_oppreach_column {
    my($board,$stone) = @_;
    my @board_strs = ($board->[0][0].$board->[1][0].$board->[2][0],
              $board->[0][1].$board->[1][1].$board->[2][1],
              $board->[0][2].$board->[1][2].$board->[2][2]);
    for (0..(@$board-1)) {
    my $i = index_oppreach($board_strs[$_], $stone);
    if (defined($i)) {
        return ($i, $_);
    }
    }
    (undef, undef);
}
sub pos_oppreach_crossline {
    my($board,$stone) = @_;
    my @board_strs = get_crosslines($board);
    my $i = index_oppreach($board_strs[0], $stone);
    if (defined($i)) {
    return ($i,$i);
    }
    $i = index_oppreach($board_strs[1], $stone);
    if (defined($i)) {
    return (@$board-1-$i,$i);
    }
    (undef, undef);
}
sub index_oppreach { # test: index_oppreach('o-o', 'x') == 1
    my $s = $_[0];
    my $o = oppstone($_[1]);
    if ($o eq 'o') {
        if ($s eq '-oo') { return 0; }
        if ($s eq 'o-o') { return 1; }
        if ($s eq 'oo-') { return 2; }
    } else { # $o eq 'o'
        if ($s eq '-xx') { return 0; }
        if ($s eq 'x-x') { return 1; }
        if ($s eq 'xx-') { return 2; }
    }
    undef;
}
sub oppstone {
    $_[0] eq 'o' ? 'x' : $_[0] eq 'x' ? 'o' : undef;
}

my %ptn_pos_h;
{
    my $ptn_pos_href = {
    # play first
    '--- --- ---' => [0,0],
    'ox- --- ---' => [1,1], # [2,0] is also ok : [2,0] [1,0] [2,2]
    'ox- -o- --x' => [1,0], # dreach
    'o-x --- ---' => [2,0],
    'o-x x-- o--' => [2,2], # dreach
    'o-- --x ---' => [2,0], # dreach by gc
    'o-- --- --x' => [2,0],
    'o-- x-- o-x' => [0,2], # dreach ... same as 'o-x x-- o--'
    'o-- -x- ---' => [2,2],
    'o-x -x- --o' => [2,0], # dreach
    
       # play second / first ps pos == (0 0)
    'o-- --- ---' => [1,1],
    'o-- -x- --o' => [2,1], # draw by gc
    'o-- -x- -o-' => [2,2], # dreach by gc 1/5 , draw by gc 4/5
       # play second / first ps pos == (1 1)    
    '--- -o- ---' => [0,0],
    'x-- -o- --o' => [0,2], # draw by gc
       # play second / first ps pos == (0 1)
    '-o- --- ---' => [0,0],
    'xoo --- ---' => [2,0],
    'xoo o-- x--' => [2,2], # dreach
    'xo- --o ---' => [2,0], # dreach by gc
    
    'xo- --- o--' => [1,1], # draw by gc
    
    'xo- o-- ---' => [2,1],
    'xoo o-- -x-' => [2,2], # dreach
    'xo- o-- ox-' => [0,2], # draw by gc
    'xo- o-- -xo' => [0,2], # draw by gc
    
    'xo- --- --o' => [1,1], # dreach by gc 1/5 , draw by gc 4/5
    };
    %ptn_pos_h = %$ptn_pos_href;
}
sub pos_smart { # assume: play first => 'o', play second => 'x', marubatsuptn
    my($board,$stone) = @_;
    for my $m (0..1) { # means: nflip
    for my $n (0..3) { # means: nrot
        my $ptn = match_board(brott($n,bflipt($m,$board)));
        if (defined $ptn) {
        #print "$ptn => @{$ptn_pos_h{$ptn}} : $m $n : debugwrite";
        return to_a(pflipt($m,prott(-$n,$ptn_pos_h{$ptn})));
        }
    }
    }
    (undef, undef);
}
sub brott {
    my($n, $board) = @_;
    dotimes($n % 4, $board, \&brot);
}
sub bflipt {
    my($n, $board) = @_;
    dotimes($n % 2, $board, \&bflip);
}
sub pflipt {
    my($n, $pos) = @_;
    dotimes($n % 2, $pos, \&pflip);
}
sub prott {
    my($n, $pos) = @_;
    dotimes($n % 4, $pos, \&prot);
}
sub dotimes {
    my($n, $obj, $coderef) = @_;
    $n==0 ? $obj : dotimes($n-1, $coderef->($obj), $coderef);
}
sub brot {
    trans(bflip($_[0]));
}
sub bflip {
    [map {[reverse @$_];} @{$_[0]}];
}
sub pflip {
    my @b = @{$_[0]};
    $b[1] = 2 - $b[1]; # pos flip
    \@b;
}
sub prot {
    my @b = @{$_[0]};
    $b[0]-=1; $b[1]-=1;
    my @c = (-$b[1], $b[0]); # pos rot ... 90 degree
    $c[0]+=1; $c[1]+=1;
    \@c;
}
sub match_board {
  my $board_str = join(' ', join0s(shift));
  my @mp = grep { $board_str eq $_; } keys %ptn_pos_h;
  (scalar @mp) ? $mp[0] : undef;
}
sub to_a {
    @{$_[0]};
}

sub check {
    my @b = @{$_[0]};
    my $w;
    # check rows
    for my $r (0..2) {
    my $l = $b[$r]->[0]; # abbrev: left of board
    if ($l ne'-' and $l eq$b[$r]->[1] and $l eq$b[$r]->[2]) { return $l; }
    }
    # check columns
    for my $c (0..2) {
    my $t = $b[0]->[$c]; # abbrev: top of board
    if ($t ne'-' and $t eq$b[1]->[$c] and $t eq$b[2]->[$c]) { return $t; }
    }
    # check crosslines
    my $p = $b[0]->[0]; # abbrev: pos
    if ($p ne'-' and $p eq$b[1]->[1] and $p eq$b[2]->[2]) { return $p; }
    $p = $b[2]->[0];
    if ($p ne'-' and $p eq$b[1]->[1] and $p eq$b[0]->[2]) { return $p; }
    # check draw
    if (filledp(\@b)) { return 'D'; } # means: draw
    undef;
}

sub join0s {
    my @b = @{$_[0]};
    my @a;
    $a[0] = join '', @{$b[0]};
    $a[1] = join '', @{$b[1]};
    $a[2] = join '', @{$b[2]};
    @a;
    # map {join '', @$_} @{$_[0]};
}
sub trans {
    my $m = shift;
    my $n = [];
    for my $r (0..2) {
    for my $c (0..2) {
        $n->[$c][$r] = $m->[$r][$c];
    }
    }
    $n;
}
sub get_crosslines {
    my $b = shift;
    join0s [[map {$b->[      $_][$_]} 0..(@$b-1)],
        [map {$b->[@$b-1-$_][$_]} 0..(@$b-1)]];
}
sub filledp {
    my $b = shift;
    for my $r (0..(@$b-1)) {
    for my $c (0..(@{$b->[$r]}-1)) {
        if ($b->[$r][$c] eq '-') { return 0; }
    }
    }
    1;
}

# utilities
sub clear {
    my $b = shift;
    for my $r (0..(@$b-1)) {
    for my $c (0..(@{$b->[$r]}-1)) {
        $b->[$r][$c] = '-';
    }
    }
}

################### run game ###################

$gc = 0; # abbrev: game count

sub game_times {
    my($player1,$player2,$ngame) = @_;
    my %wc;
    print "***** $player1 vs $player2 *****\n";
    print "game ", $gc+1, "..", $gc+$ngame, "\n";
    $gc += $ngame;
    for (1..$ngame) {
    my $w = game({put_stone=>\&$player1, stone=>'o'},
             {put_stone=>\&$player2, stone=>'x'});
    $wc{$w}++;
    }
    while (my($k,$v) = each(%wc)) {
    print "$k=>$v ";
    }
    print "\n";    
}

$ngame = 10000;
game_times('ps_smart', 'put_stone_random', $ngame);
game_times('put_stone_random', 'ps_smart', $ngame);
game_times('ps_smart', 'ps_smart', 100);

先手、後手でも負けることはありません シンプルな実装にしました

・自分の駒が二個並んでいるときはそのまま勝つ ・相手の駒が二個並んでいて勝たれてしまうときは防ぐ ・相手のダブルリーチを防ぐ

を戦略として、先手の場合一手目、二手目だけ打つ方法を指定しています

random won: 0 , think won: 860 draw: 140 think won: 985 , random won: 0 draw: 15

  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
import random
random.seed()

class Mark:
    def __init__(self, name):
        self.name = name

MARK_E = Mark(" ")
MARK_X = Mark("X")
MARK_O = Mark("O")

class Marubatsu:
    lines = []
    for a in range(3):
        lines.append([(a, b) for b in range(3) ])
        lines.append([(b, a) for b in range(3) ])
    lines.append([(a, a) for a in range(3) ])
    lines.append([(2 - a, a) for a in range(3) ])

    def __init__(self, p1_logic, p2_logic):
        self.fields = {}
        self.seq = []
        for x in range(3):
            for y in range(3):
                self.fields[(x, y)] = MARK_E
        self.logic = (p1_logic, p2_logic)
        self.turn = 0

    def now_player(self):
        return 0 if self.turn % 2 == 0 else 1

    def mark(self):
        return MARK_O if self.now_player() == 0 else MARK_X
    
    def play(self):
        for self.turn in range(9):
            logic = self.logic[self.now_player()]
            pos = logic(self)
            if self.at(pos) != MARK_E:
                raise "Err"
            self.fields[pos] = self.mark()
            self.seq.append((self.mark(), pos))

            mark = self.end_check()
            if mark:
                return mark
        return None

    def at(self, pos):
        return self.fields[pos]

    def __str__(self):
        str = ""
        for x in range(3):
            str += "".join([self.at((x, y)).name for y in range(3)])
            str += "\n"
        str += " ".join(["%s: %s" % (mark.name, pos) for mark, pos in self.seq])
        str += "\n"
        return str

    def count_at_line(self, line):
        ret = {MARK_E: 0 ,MARK_O: 0, MARK_X: 0}
        for pos in line:
            ret[self.fields[pos]] += 1
        return ret
    
    def end_check(self):
        for line in Marubatsu.lines:
            counts = self.count_at_line(line)
            if counts[MARK_O] == 3:
                return MARK_O
            elif counts[MARK_X] == 3:
                return MARK_X
        return None

    def can_puts(self):
        return [pos for pos, mark in self.fields.items()
               if mark == MARK_E]
    
def think_put(game):
    if game.at((1, 1)) == MARK_E:
        return (1, 1)

    me = game.mark()
    op = MARK_O if me == MARK_X else MARK_X

    # OO_
    for line in Marubatsu.lines:
        counts = game.count_at_line(line)
        if (counts[me] == 2 and counts[MARK_E] == 1):
             return [pos for pos in line if game.at(pos) == MARK_E][0]

    # XX_
    for line in Marubatsu.lines:
        counts = game.count_at_line(line)
        if (counts[op] == 2 and counts[MARK_E] == 1):
            return [pos for pos in line if game.at(pos) == MARK_E][0]

    if game.turn == 3:
        op_corners = [a for a in \
                          [game.at((0, 0)), game.at((0, 2)),
                           game.at((2, 0)), game.at((2, 2))]
                      if a == op]
        if len(op_corners) == 2:
            return (1, 0)
                
    point_map = {}
    for line in Marubatsu.lines:
        counts = game.count_at_line(line)
        if (counts[op] == 1 and counts[MARK_E] == 2):
            for pos in line:
                if point_map.has_key(pos):
                    point_map[pos] += 1
                else:
                    point_map[pos] = 1

    if len(point_map) > 0:
        point_pos = max(point_map, key=point_map.__getitem__)
        if game.at(point_pos) == MARK_E:
            return point_pos

    # O__
    for line in Marubatsu.lines:
        counts = game.count_at_line(line)
        if (counts[me] == 1 and counts[MARK_E] == 2):
            return [pos for pos in line if game.at(pos) == MARK_E][-1]

    for pos in [(0, 0), (2, 2), (2, 0), (0, 2)]:
        if game.at(pos) == MARK_E:
            return pos

    return random_put(game)

def random_put(game):
    puts = game.can_puts()
    return puts[random.randrange(len(puts))]

def play(p1_name, p1_logic, p2_name, p2_logic, count):
    results = [0, 0, 0]
    player_idx = {MARK_O: 0, MARK_X: 1, None: 2}
    for round in range(count):
        game = Marubatsu(p1_logic, p2_logic)
        winner = player_idx[game.play()]
        results[winner] += 1

        if (winner == 0 and p2_name == "tnk") or \
                (winner == 1 and p1_name == "tnk"):
            print game

    print p1_name , "won:", results[0], ",", \
        p2_name, "won:", results[1], "draw:", results[2]

if __name__ == '__main__':
    play("random", random_put, "think", think_put, 1000)
    play("think", think_put, "random", random_put, 1000)

low uric diet <a href=http://rxdrugs24x7.com/product/claritin.html>Order Claritin</a> heart failure due to hypertension http://rxdrugs24x7.com/product/avandia.html central lines and blood draws http://rxdrugs24x7.com/product/gestanin.html veterinary health certificate <a href=http://rxdrugs24x7.com/product/prevacid.html>Order Prevacid</a> drugs in high schools <a href=http://rxdrugs24x7.com/product/herbal-viagra.html>stop smoking poster</a>


the art of reading smoke <a href=http://rxdrugs24x7.com/product/tenormin.html>Order Tenormin</a> how do i apply for physical medicine rehabilitation residency http://rxdrugs24x7.com/product/effexor.html washington county fl health department http://rxdrugs24x7.com/product/evista.html village medical houston texas <a href=http://rxdrugs24x7.com/product/hyzaar.html>Order Hyzaar</a> ocean view health club malibu <a href=http://rxdrugs24x7.com/product/casodex.html>mouth ulcers as only indication of hiv infection</a>


calcium monophosphate <a href=http://rxdrugs24x7.com/product/benzac-5.html>Order Benzac 5%</a> bubblicious gum http://rxdrugs24x7.com/product/persantine.html akans diet http://rxdrugs24x7.com/product/dilantin.html vitamin deficiency psoriasis symptoms <a href=http://rxdrugs24x7.com/category/pain-relief.html>Order pain relief</a> genital sores from bacterial infection <a href=http://rxdrugs24x7.com/product/provera.html>depression las veags</a>


japanese music history <a href=http://royalmp3.net/artist28318/sitar---ravi-shankar--yehudi-menuhin-discography/>Sitar - Ravi Shankar, Yehudi Menuhin</a> download albanian sjota music http://royalmp3.net/artist419/macbeth-discography/ monkey music converter http://royalmp3.net/artist4361/rage-against-the-machine-discography/ music farm <a href=http://royalmp3.net/artist19120/axess-denied-discography/>Axess Denied</a> music programs for infants <a href=http://royalmp3.net/artist3448/pig-destroyer-discography/>limited brands music</a> music gangster soul harmony vol1 <a href=http://royalmp3.net/artist9822/iio-discography/>Iio</a> digital music instruments <a href=http://royalmp3.net/artist3674/thunder-discography/>music notation editor</a>


solace irish music <a href=http://royalmp3.net/artist20842/geddy-lee-discography/>Geddy Lee</a> landers music orange http://royalmp3.net/artist1155/tri-atma-discography/ your body music http://royalmp3.net/artist1838/the-beloved-discography/ the golden compass movie http://moviestrawberry.com/hqmoviesbyyear/year_2004_high-quality-movies/?page=2 hired hand movie <a href=http://moviestrawberry.com/films/film_stop_loss/>rapidshare movie b movie</a> amstad movie questions <a href=http://moviestrawberry.com/films/film_the_abominable_dr_phibes/>the abominable dr phibes</a> keyboard sheet music <a href=http://royalmp3.net/artist13835/carl-marx-discography/>Carl Marx</a> spooky halloween music codes <a href=http://royalmp3.net/artist291/lacuna-coil-discography/>tampa bay spanish christian music station</a> bella movie http://moviestrawberry.com/hqmoviesbyyear/year_2001_high-quality-movies/?page=6 how to get a major studio to fund your movie <a href=http://moviestrawberry.com/films/film_day_of_the_dead_70/>pink lightning movie trans am</a> shattered glass movie <a href=http://moviestrawberry.com/films/film_the_fast_and_the_furious/>the fast and the furious</a> midi music downloads <a href=http://royalmp3.net/artist13871/dave-angel-discography/>Dave Angel</a> free country music song lyrics by hank williams jr <a href=http://royalmp3.net/artist1985/capercaillie-discography/>how to speed up music</a> princess bride movie poster http://rusfilms.com/page/2/ celebrity movie archive carrrie fisher <a href=http://rusfilms.com/page/3/>accepted movie from hollywood</a>


music santa clarita valley <a href=http://royalmp3.net/artist10291/pedrito-altamiranda-discography/>Pedrito Altamiranda</a> rapidshare music hole http://royalmp3.net/artist3845/balanescu-quartet-discography/ giannetis music store in scranton http://royalmp3.net/artist1939/gala-discography/ reasons movie http://moviestrawberry.com/films/film_d_war/ ratatouille movie cast <a href=http://moviestrawberry.com/films/film_borderline/>playgirl movie reviews</a> american anime movie list <a href=http://moviestrawberry.com/films/film_moby_dick/>moby dick</a> karoke machines and music <a href=http://royalmp3.net/artist1180/patrick-bernhardt-discography/>Patrick Bernhardt</a> free world christmas music <a href=http://royalmp3.net/artist2103/alexey-obraztsoff-discography/>background music for home movies</a> number one movie last weekend august 25 26 http://moviestrawberry.com/films/film_the_wager/ adult movie downloads with paypal <a href=http://moviestrawberry.com/films/film_roxanne/>balls of fury movie online</a> harry potter 5 new movie release date <a href=http://moviestrawberry.com/films/film_little_man/>little man</a> palmentto music <a href=http://royalmp3.net/artist1335/satanic-slaughter-discography/>Satanic Slaughter</a> elevator music wavs <a href=http://royalmp3.net/artist3827/al-kindi-ensemble-discography/>nba starting five list of music</a> hiding out movie clip http://rusfilms.com/page/3/ bruce lee movie <a href=http://rusfilms.com/page/2/>cars movie coloring pages</a>


how classical music effects the brain <a href=http://royalmp3.net/artist15095/junior-watson-discography/>Junior Watson</a> mtv music award 1990 to 2007 http://royalmp3.net/artist524/aube--msbr-and-koji-marutani-discography/ first amendment and music http://royalmp3.net/artist445/vicious-crusade-discography/ french movie best friend http://moviestrawberry.com/films/film_must_love_dogs/ teen movie links <a href=http://moviestrawberry.com/films/film_maradona_by_kusturica/>running man movie trivia</a> dear john the movie <a href=http://moviestrawberry.com/films/film_raging_bull/>raging bull</a> sheet music sunset mountain <a href=http://royalmp3.net/artist3491/venetian-snares-discography/>Venetian Snares</a> goosebumps music notes <a href=http://royalmp3.net/artist4271/bad-religion-discography/>nys teacher licence music examation</a> christmas visions movie http://moviestrawberry.com/hqmoviesbygenres/download-genre_sport-movies/?page=6 new movie war <a href=http://moviestrawberry.com/films/film_superman_ii/>good morning sheet music movie</a> random encounter 10098 movie <a href=http://moviestrawberry.com/films/film_the_killing_of_john_lennon/>the killing of john lennon</a> download all hellsing music <a href=http://royalmp3.net/artist9969/juicy-lucy-discography/>Juicy Lucy</a> coupon coder rent ron comcast pol music ripken <a href=http://royalmp3.net/artist1330/mindless-self-indulgence-discography/>the american dollar music torrent</a> free akira fubuki movie http://rusfilms.com/page/3/ movie making unionville pa <a href=http://rusfilms.com/page/3/>movie line wakey wakey eggs and bacy</a>


loose stools music web site <a href=http://royalmp3.net/artist5712/ken-martin-discography/>Ken Martin</a> music new recording studio york http://royalmp3.net/artist957/underworld-discography/ ryushi yanagisawa music http://royalmp3.net/artist873/rimsky-korsakov-discography/ cable movie tc grid http://moviestrawberry.com/films/film_in_the_time_of_the_butterflies/ songs from the movie unfaithful <a href=http://moviestrawberry.com/films/film_my_fair_lady/>erotic hardcore couples movie</a> atlanta georgia movie theatre <a href=http://moviestrawberry.com/films/film_5_card_stud/>5 card stud</a> online free music trivia with audio <a href=http://royalmp3.net/artist1510/chroming-rose-discography/>Chroming Rose</a> sexy hip hop music <a href=http://royalmp3.net/artist547/jan-garbarek-and-trilok-gurtu-discography/>indian music download</a> speed movie review http://moviestrawberry.com/films/film_brain_story/ movie theater lowell massachusetts <a href=http://moviestrawberry.com/films/film_carnival_boat/>harry potter 5 movie pictures</a> steve mc queen movie actor <a href=http://moviestrawberry.com/films/film_alive/>alive</a> free music downloads for soaring away eagle <a href=http://royalmp3.net/artist8730/celso-fonseca-discography/>Celso Fonseca</a> music mastering <a href=http://royalmp3.net/artist2790/black-wood-discography/>music santa clarita</a> movie sound bites waiting http://rusfilms.com/page/4/ download spiderman 3 the movie <a href=http://rusfilms.com/page/2/>isabel glaser pure country movie</a>


history of music video production <a href=http://royalmp3.net/artist39184/tommy-castro--jimmy-hall--lloyd-jones-discography/>Tommy Castro, Jimmy Hall, Lloyd Jones</a> gospel music for classical guitar http://royalmp3.net/artist3880/enertopia-discography/ music education college university conservatory ratings http://royalmp3.net/artist3772/bondage-fruit-discography/ free copyable movie files http://moviestrawberry.com/films/film_carry_on_cowboy/ songs from united 93 and twin towers movie <a href=http://moviestrawberry.com/films/film_bachelor_party_2_the_last_temptation/>download free vcd movie</a> bimbo gay movie review <a href=http://moviestrawberry.com/films/film_hollow_man/>hollow man</a> music instruments used in ancient rome <a href=http://royalmp3.net/artist19449/miss-kittin-and-the-hacker-discography/>Miss Kittin and The Hacker</a> ffxi music download <a href=http://royalmp3.net/artist4441/nebelnest-discography/>natalie cole sheet music</a> movie auditions nj http://moviestrawberry.com/films/film_vice/ wizard of oz movie picturess <a href=http://moviestrawberry.com/films/film_the_game_70/>free amature fresh pussy movie dump</a> gay movie house new york fair theatre <a href=http://moviestrawberry.com/films/film_backwoods/>backwoods</a> music creator 3 <a href=http://royalmp3.net/artist5736/koda-kumi-discography/>Koda Kumi</a> business music plan school <a href=http://royalmp3.net/artist4453/blancmange-discography/>arabic music codes</a> sybian movie clips http://rusfilms.com/page/2/ skinwalkers movie download free <a href=http://rusfilms.com/>management movie</a>


music folder with pencil holder <a href=http://royalmp3.net/artist37004/big-daddy-weave-and-barlow-girl-discography/>Big Daddy Weave and Barlow Girl</a> oregon music teachers association http://royalmp3.net/artist3777/dub-trees-discography/ vivaldi cello concerto sheet music http://royalmp3.net/artist1178/tony-o-connor-discography/ swarnakamalam telugu movie http://moviestrawberry.com/films/film_murder_my_sweet/ free big porn movie <a href=http://moviestrawberry.com/films/film_hard_candy/>adult movie directory</a> all lf my life movie <a href=http://moviestrawberry.com/films/film_driven/>driven</a> sheet music for la boheme <a href=http://royalmp3.net/artist4112/alabina-and-ishtar-and-los-ni--discography/>Alabina and Ishtar and Los Niс</a> london music london <a href=http://royalmp3.net/artist1394/ancient-drive-discography/>arab pop music torrent</a> rick graziani fiber optics movie http://moviestrawberry.com/films/film_tupac_live_at_the_house_of_blues/ movie raleigh nc listing <a href=http://moviestrawberry.com/films/film_blonde_ambition/>xxx multiracial gang bang movie</a> making a movie <a href=http://moviestrawberry.com/films/film_cruel_intentions_3/>cruel intentions 3</a> country music billboard charts <a href=http://royalmp3.net/artist15002/newcleus-discography/>Newcleus</a> music to play on the trumpet <a href=http://royalmp3.net/artist4003/cypher-discography/>craft using sheet music</a> pickup game ending movie http://rusfilms.com/page/2/ october movie releases <a href=http://rusfilms.com/page/4/>charmed movie</a>


rap music lyrics for soulja bo