DouKaku?beta

challenge マルバツゲーム

マルバツゲームは３×３の格子に交互に○と×を書き込み、先に縦・横・斜めに記号をそろえたほうが勝ちというおなじみのゲームです。

「毎ターン乱数を使って手を決めるランダムプレイヤー同士を対戦させる」というのが今回のお題です。 １万回対戦させ、勝ち・負け・引き分けの数を表示してください。 そして先手が有利であることを確かめてください。

良い手を思考するプレイヤーについては別のお題にしようと思っています。 プレイヤーを簡単に差し換えることができる設計を目指してください。

post comment

Posted feedbacks - Nested

Flatten Hidden

お昼休みにさくっとやってみました。

Playerクラスを継承したクラスをつくることでPlayerを差し替えることができます。

10000回を3回ほどやってみて 

player1 won:    5190
player2 won:    2410
draw :  2400

player1 won:    5190
player2 won:    2411
draw :  2399

player1 won:    5152
player2 won:    2383
draw :  2465

というかんじでした。 

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

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

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

  override def toString = {
    val sep = List.make(size*4+1, "-").mkString("\n", "", "\n")
    field.map{_.mkString("| ", " | ", " |")}.mkString(sep,sep,sep)
  }

  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(len).find {player => 
      val p = player.put(this)
      if(!available_?(p)) error("Oops!")
      field(p._1)(p._2) = player.mark
      judge
    }
  }

  def judge = lines.exists(l => l.forall(!available_?(_)) && 
                    l.forall(v => field(l(0)._1)(l(0)._2) == field(v._1)(v._2)))

  def available_?(pos:Pair[int,int]) = field(pos._1)(pos._2) equals ' '
}

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
  }
}

object Main extends Application{
  val ttt = new TicTacToe(3, List(new RandomPlayer('○', "1"), new RandomPlayer('×', "2")))
  val result = Array.make(3,0)
  (1 to 10000) foreach { i => 
    ttt.start match {
      case Some(p) if p.name equals "1" => result(0) += 1
      case Some(p) if p.name equals "2" => result(1) += 1
      case _ => result(2) += 1
    }
  }
  println("player1 won:\t"+result(0)+"\n"+"player2 won:\t"+result(1)+"\n"+"draw :\t"+result(2))
}

1行ミスってました。コピペはいけませんね･･･。あらためて 

player1 won:    5826
player2 won:    2857
draw :  1317

という感じです。 

1
2
3
4
5
6
7
8
9
@@ -4,7 +4,7 @@
   protected val field = new Array[Array[char]](size,size)
   val len = size*size
   val lines = _stline((v,v2) => (v,v2))++_stline((v,v2) => (v2,v))++
-              List(((size-1).until(-1,-1)).map(v=>(v,v))) ++
+              List(((size-1).until(-1,-1)).map(v=> (v,(size-1-v)))) ++
               List((0 until size).map(v=>(v,v)))

   def _stline(f:(int,int) => Pair[int,int]) =

出題者です。統計的には試行回数が多いほど誤差が小さくなるので、試しに１００万×５回ほどやってみました。

その結果、

先攻勝ち：先攻負け：引き分け　≒ 58.5：28.8：12.7

と出ました。 そこらへんの数字の人は正解と思われます。

乱数は素直につかえば問題ないのですが、変なロジックをとおした結果、かたよりが出たりすると怖いです。 処理系によって乱数の癖が見れたりしたら面白かったかも？？

全局面を探索したところ、
先攻：51.4%、後攻：30.4%、引き分け18.1%
が正解のようですね。
syatさんの結果でいいのではないでしょうか。

全局面の意味がよくわかりませんが、
途中で終わったりもするので、
すべての局面が等確率で出現するわけではありません。
結果の検証用に打ち筋をすべてたどってみました。
先攻勝ち：131184(51.4%)
後攻勝ち：77904(30.5%)
引き分け：46080(18.1%)
の255168通りでした。

乱数で勝負させたものは確かにsyatさんの数字に近くなったんですが･･･。
 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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int data;
    int turn;
} CELL;
/*
  [0][1][2]
  [3][4][5]
  [6][7][8]

cell
 data cellの内容
  0:空白
  1:o
  2:x
 turn 打たれたターン数
*/


//勝敗チェック
// 0    :決着まだ
// not 0:勝負あり
int check(CELL a[],int w){
    int i;
    //縦横
    for(i=0;i<3;i++){
        if((a[i*3].data==w)&&(a[i*3+1].data==w)&&(a[i*3+2].data==w)||
           (a[i].data==w)&&(a[i+3].data==w)&&(a[i+6].data==w)) return -1;
    }
    //斜め
    if((a[0].data==w)&&(a[4].data==w)&&(a[8].data==w)||
       (a[2].data==w)&&(a[4].data==w)&&(a[6].data==w)) return -1;
    return 0;
}

int result[3];

int analyze(CELL a[],int t,int turn){
    int i;

    if(turn==10){
    //引き分け
        result[0]++;
        return -1;
    }
    
    //進行
    for(i=0;i<9;i++){
        if(a[i].data==0){
            //置けるなら置く
            a[i].data=t;
            a[i].turn=turn;
            //勝負判定
            if(check(a,t)){
                //決着
                result[t]++;
            }else{
                //続行
                analyze(a,3-t,turn+1);
            }
            //一手戻す
            a[i].data=0;
            a[i].turn=0;
        }
    }
    return 0;
}

int main(){
    int i;
    CELL a[9];

    //盤面初期化
    for(i=0;i<9;i++){
        a[i].data=0;
        a[i].turn=0;
    }
    for(i=0;i<3;i++){
        result[i]=0;
    }
    
    analyze(a,1,1);
    i=result[0]+result[1]+result[2];
    printf("o win:%d(%2.1f%%) x win:%d(%2.1f%%) draw:%d(%2.1f%%)\n",
        result[1],100.0*result[1]/i,
        result[2],100.0*result[2]/i,
        result[0],100.0*result[0]/i);

    return 0;
}

ちと違うみたいです。

58行目、 
result[t]+=weight(9-turn);
に直して下記コードを追加
で、
o win:212256(58.5%) x win:104544(28.8%) draw:46080(12.7%)

だと思います。


1
2
3
4
int weight(int i) {
  if (i<=1) return 1;
  return i*weight(i-1);
}

なるほど・・・
ようやく理解しました。
IPlayerBaseインターフェースを実装していればプレーヤーになれます。
勝敗判定の部分をもっとエレガントに書きたいですね。

結果
○ WIN : 5837
× WIN : 2846
  DRAW : 1317

○ WIN : 5863
× WIN : 2924
  DRAW : 1213

○ WIN : 5811
× WIN : 2895
  DRAW : 1294 
  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
using System;
using System.Collections.Generic;
using System.Linq;

namespace どう書く_org_マルバツゲーム {
    class Program {
        static void Main(string[] args) {
            int maruWin = 0;
            int batuWin = 0;
            int draw = 0;
            IPlayerBase maru = new Player() { Name = "○" };
            IPlayerBase batu = new Player() { Name = "×" };

            for(int i = 0; i < 10000; i++) {
                Game game = new Game(maru, batu);
                switch(game.Start()) {
                case "○":
                    maruWin++;
                    break;
                case "×":
                    batuWin++;
                    break;
                case "draw":
                    draw++;
                    break;
                }
            }

            Console.WriteLine("○ WIN : " + maruWin.ToString());
            Console.WriteLine("× WIN : " + batuWin.ToString());
            Console.WriteLine("  DRAW : " + draw.ToString());

            Console.ReadLine();
        }
    }

    class Game {
        private IPlayerBase _maru;
        private IPlayerBase _batu;

        public string[] Board = new string[] {
            "□□□",
            "□□□",
            "□□□" };

        public Game(IPlayerBase maru, IPlayerBase batu) {
            _maru = maru;
            _maru.Game = this;
            _batu = batu;
            _batu.Game = this;
        }

        public string Start() {
            string jadge = "";
            while(true) {
                _maru.Play();
                jadge = Judge(_maru.Name);
                if(jadge != "") {
                    break;
                }
                _batu.Play();
                jadge = Judge(_batu.Name);
                if(jadge != "") {
                    break;
                }
            }

            return jadge;
        }

        //勝者を判定
        private string Judge(string name) {
            string name3 = name + name + name;
            //横
            foreach(string str in Board) {
                if(str == name3) {
                    return name;
                }
            }

            //縦
            for(int x = 0; x < 3; x++) {
                string str = "";
                for(int y = 0; y < 3; y++) {
                    str += Board[y][x];
                }
                if(str == name3) {
                    return name;
                }
            }

            //斜め
            string tmp = Board[0][0].ToString() + Board[1][1].ToString() + Board[2][2].ToString();
            if(tmp == name3) {
                return name;
            }
            tmp = Board[0][2].ToString() + Board[1][1].ToString() + Board[2][0].ToString();
            if(tmp == name3) {
                return name;
            }

            //引き分け
            if(!(Board[0] + Board[1] + Board[2]).Contains('□')) {
                return "draw";
            }
            return "";
        }
    }

    class Player :IPlayerBase {
        #region IPlayerBase メンバ

        public Game Game { get; set; } //参加しているゲーム

        public string Name { get; set; } //○か×か

        private Random Rnd = new Random();
        //一手打つ
        public void Play() {
            List<Location> cells = new List<Location>(); //置けるマス

            //置けるマスを列挙
            for(int y = 0; y < 3; y++) {
                for(int x = 0; x < 3; x++) {
                    if(Game.Board[y][x] == '□') {
                        Location location = new Location();
                        location.x = x;
                        location.y = y;

                        cells.Add(location);
                    }
                }
            }

            //置けるマスが無ければ何もしない
            if(cells.Count == 0) return;

            //乱数で置くマスを決定
            int index = Rnd.Next(cells.Count);
            Location cell = cells[index];

            //石を置く
            Game.Board[cell.y] = Game.Board[cell.y].Remove(cell.x, 1).Insert(cell.x, Name);
        }
        #endregion
    }

    //マスの位置
    struct Location {
        public int x;
        public int y;
    }

    //プレーヤーが実装するインターフェース
    //これを実装したプレーヤーに差し替え可
    interface IPlayerBase {
        Game Game { set; get; }
        string Name { set; get; }
        void Play();
    }
}

Playerを実装すれば、実装を置き換えられます。
しかし、Scalaと比べてだいぶ長くなっちゃいました。
とりあえず、3回実行してみた結果です。

Result:
Player1 won: 5214
Player2 won: 2355
draw game  : 2431

Result:
Player1 won: 5211
Player2 won: 2444
draw game  : 2345

Result:
Player1 won: 5174
Player2 won: 2404
draw game  : 2422

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

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

    private final Mark[][] fields_ = new Mark[SIZE][SIZE];
    private final Pair[][] lines_ = new Pair[][] {
            {new Pair(0,0), new Pair(0,1), new Pair(0,2)},
            {new Pair(1,0), new Pair(1,1), new Pair(1,2)},
            {new Pair(2,0), new Pair(2,1), new Pair(2,2)},
            {new Pair(0,0), new Pair(1,0), new Pair(2,0)},
            {new Pair(0,1), new Pair(1,1), new Pair(2,1)},
            {new Pair(0,2), new Pair(1,2), new Pair(2,2)},
            {new Pair(0,0), new Pair(1,1), new Pair(2,2)},
            {new Pair(2,2), new Pair(1,1), new Pair(0,0)},
    };


    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;
    }


    public static void main(String[] args) {
        Player player1 = new RandomPlayer(Mark.O, "Player1");
        Player player2 = new RandomPlayer(Mark.X, "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;

    public Pair(int x, int y) {
        this.x = x;
        this.y = 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) {
        for (;;) {
            Pair pair = getNextPair();
            boolean res = game.nextStep(pair, mark);
            if (res) break;
        }
    }
    private Pair getNextPair() {
        return new Pair(random_.nextInt(TicTacToe.SIZE), random_.nextInt(TicTacToe.SIZE));
    }
}

終了判定にバグ発見してしまいました。
ここを直して、100万回実行した結果以下のようになりました。
これでほぼ合っていそうです。

Result:
Player1 won: 582337
Player2 won: 290884
draw game  : 126779

1
2
3
4
15c15
<                       {new Pair(2,2), new Pair(1,1), new Pair(0,0)},
---
>                       {new Pair(0,2), new Pair(1,1), new Pair(2,0)},

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
| マス目群 勝敗カウンタ 勝ち判定 |
マス目群 := OrderedCollection new.
(1 to: 3) asDigitsToPower: 2 do: [:座標 | マス目群 add: 座標 copy].

勝敗カウンタ := Bag new.

1e4 timesRepeat: [
    | 残りのマス目群 先手 後手 打ち手順 手番 結果 |
    残りのマス目群 := マス目群 copy shuffled.
    先手 := OrderedCollection new. 後手 := 先手 copy.
    打ち手順 := {先手. 後手}.
    手番 := 0.
    結果 := nil.
    勝ち判定 := [:取得済み |
        (#(first second) anySatisfy: [:セレクタ |
            (取得済み
                groupBy: [:各々 | 各々 perform: セレクタ]
                having: [:括り | 括り size = 3]) notEmpty]) or: [
        {[:各々 | 各々 first = 各々 second]. [:各々 | 各々 sum = 4]}
            anySatisfy: [:条件 | (取得済み count: 条件) = 3]]].

    [残りのマス目群
        ifEmpty: [結果 := #引き分け]
        ifNotEmpty: [
            | 取得マス目群 |
            (取得マス目群 := 打ち手順 atWrap: (手番 := 手番 + 1))
                add: 残りのマス目群 removeFirst.
            (勝ち判定 value: 取得マス目群) ifTrue: [
                結果 := 手番 odd
                    ifTrue: [#先手勝ち]
                    ifFalse: [#後手勝ち]]].
    結果 isNil] whileTrue.

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

^勝敗カウンタ sortedCounts asArray

"=> {5895->#先手勝ち. 2796->#後手勝ち. 1309->#引き分け} "

勝敗判定が分かりづらかったので変えてみました。

 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
| マス目群 ライン群 勝敗カウンタ |
マス目群 := OrderedCollection new.
(1 to: 3) asDigitsToPower: 2 do: [:座標 | マス目群 add: 座標 copy].

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

勝敗カウンタ := Bag new.

1e4 timesRepeat: [
    | 残りのマス目群 先手 後手 打ち手順 手番 結果 |
    残りのマス目群 := マス目群 copy shuffled.
    先手 := OrderedCollection new. 後手 := 先手 copy.
    打ち手順 := {先手. 後手}.
    手番 := 0.
    結果 := nil.

    [残りのマス目群
        ifEmpty: [結果 := #引き分け]
        ifNotEmpty: [
            | 取得マス目群 |
            (取得マス目群 := 打ち手順 atWrap: (手番 := 手番 + 1))
                add: 残りのマス目群 removeFirst.
            (ライン群 anySatisfy: [:必須マス群 |
                    取得マス目群 includesAllOf: 必須マス群])
                ifTrue: [結果 := 手番 odd
                    ifTrue: [#先手勝ち] ifFalse: [#後手勝ち]]].
    結果 isNil] whileTrue.

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

^勝敗カウンタ sortedCounts asArray

ちょっと力業でしょうか。

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

(random-source-randomize! default-random-source)

;; board: (0 1 0 0 0 0 0 0 0)
;; board -> board
(define (player-random board self)
  (define (okeru)
    (length (filter zero? board)))

  (let loop ((board board)
         (next  (random-integer (okeru))))
    (if (null? board)
    ()
    (cons (if (= next 0)
          self
          (car board))
          (loop (cdr board)
            (if (= (car board) 0)
            (- next 1)
            next
            ))))))

(define (play p1 p2)
  (define (finish? board)
    (or (> (judge board) 0)
    (not (find zero? board))))

  (let loop ((board (make-list 9 0))
         (phase 1))
    (if (finish? board)
    board
    (if (= phase 1)
        (loop (p1 board 1) 2)
        (loop (p2 board 2) 1)))))

(define (judge board)
  (define line-points-list
    '((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 (judge-4-player n)
    (find (lambda (line-points)
        (every (lambda (j)
             (= (ref board j) n))
           line-points))
      line-points-list))

  (cond ((judge-4-player 1) 1)
    ((judge-4-player 2) 2)
    (else 0)))

(define (marubatsu p1 p2)
  (define (one-play)
    (judge (play p1 p2)))

  (define hash (make-hash-table))
  (dotimes (counter 10000)
    (hash-table-update! hash (one-play) (cut + 1 <>) 0))

  (write (hash-table->alist hash)))

ちょっと力業でしょうか。

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

(random-source-randomize! default-random-source)

;; board: (0 1 0 0 0 0 0 0 0)
;; board -> board
(define (player-random board self)
  (define (okeru)
    (length (filter zero? board)))

  (let loop ((board board)
         (next  (random-integer (okeru))))
    (if (null? board)
    ()
    (cons (if (= next 0)
          self
          (car board))
          (loop (cdr board)
            (if (= (car board) 0)
            (- next 1)
            next
            ))))))

(define (play p1 p2)
  (define (finish? board)
    (or (> (judge board) 0)
    (not (find zero? board))))

  (let loop ((board (make-list 9 0))
         (phase 1))
    (if (finish? board)
    board
    (if (= phase 1)
        (loop (p1 board 1) 2)
        (loop (p2 board 2) 1)))))

(define (judge board)
  (define line-points-list
    '((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 (judge-4-player n)
    (find (lambda (line-points)
        (every (lambda (j)
             (= (ref board j) n))
           line-points))
      line-points-list))

  (cond ((judge-4-player 1) 1)
    ((judge-4-player 2) 2)
    (else 0)))

(define (marubatsu p1 p2)
  (define (one-play)
    (judge (play p1 p2)))

  (define hash (make-hash-table))
  (dotimes (counter 10000)
    (hash-table-update! hash (one-play) (cut + 1 <>) 0))

  (write (hash-table->alist hash)))

プレイヤーを単純な関数として実装しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from random import choice

def p(d, x):
  return choice([i for i, j in enumerate(d) if j == 0])

def w(d, i):
  f = lambda l: [i] * 3 == l
  return (f(d[:3]) or f(d[3:6]) or f(d[6:]) or
          f(d[::3]) or f(d[1::3]) or f(d[2::3]) or
          f(d[::4]) or f(d[2:7:2]))

def m(*p):
  d = [0] * 9
  for i in range(9):
    x = i % 2 + 1
    d[p[i%2](d, x)] = x
    if i > 3 and w(d, x):
      return x
  return 0

r = [0] * 3
for i in range(10000):
  r[m(p, p)] += 1
print 'draw: %d\n1st:  %d\n2nd:  %d' % tuple(r)

○×ゲームなのに視覚的なものはほとんど考慮してないので恐縮ですが...

ちなみに、100万回勝負させたら

player 1 won : 3595448(0.359545)
player 2 won : 2882753(0.288275)
draw : 3521799(0.35218)

だそうです。
  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
#include <algorithm>
#include <iostream>
#include <map>
#include <ctime>

class board
{
  int cell[3*3];

  public:
  board() { reset(); }
  void reset() { std::fill_n(cell, 3*3, 0); }

  int& operator()(int x, int y)
  { return cell[x+3*y]; }
  const int& operator()(int x, int y) const
  { return cell[x+3*y]; }
};
std::ostream& operator<<(std::ostream& os, const board& b)
{
  for ( int y = 0; y < 3; ++y ) {
    y != 0 && os << "-+-+-\n";
    os << b(0,y) << "|" << b(1,y) << "|" << b(2,y) << "\n";
  }
  return os;
}


class player
{
  static int player_id_;
  int id_;

  protected:
  player() : id_(++player_id_) {}
  virtual ~player();

  public:
  int id()const { return id_; }

  void operator()(board& b) const
  { next(b); }


  private:
  virtual void
    next(board& b)
  const = 0;
};
int player::player_id_ = 0;
player::~player() {}