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