DouKaku?

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

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 { }
        }
    }
    //１試合
    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();
        }
    }
}