○×

×│○│×
─┼─┼─
○│○│×
─┼─┼─
○│×│○

突然ですが、上記のような３×３のマスの3目並べについて。
このゲームは、実は最初の2手で結論が決まってしまうんですね。いまさらですが、id:nowokay:20050816#1124180870 を考えていて判明しました。そんな訳でRubyでそのアルゴリズムを実装してみたところです。結論に間違いはないかな？誰か問題があったら指摘してください。
○が勝利する条件

1. 最初に真ん中に置く
2. ×が4角以外の場所に置く(つまり、真ん中から上下左右の位置)

逆に×が4角に置いた場合は引き分け

以下が実装したRubyのソースです。長いのでたたみます。

class Marubatu
  E = :'　'
  O = :'○'
  X = :'×'

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

  def self.display(marks)
    if win?(marks, O) then
      print "#{O} is win!\n"
    elsif win?(marks, X) then
      print "#{X} is win!\n"
    end
    
    board = Array.new(9, E)
    i = 0
    marks.each do |m|
      board[m.to_i] = mark(i)
      i+=1
    end
    
    print_board(board)
  end

  def self.print_board(board)
    print "#{board[0]}│#{board[1]}│#{board[2]}\n"
    print "─┼─┼─\n"
    print "#{board[3]}│#{board[4]}│#{board[5]}\n"
    print "─┼─┼─\n"
    print "#{board[6]}│#{board[7]}│#{board[8]}\n"
  end

  def self.mark(index)
    (index % 2 == 0)? O: X
  end

  def self.opponent(mark)
    if mark == O then return X
    elsif mark == X then return O
    end
    E
  end

  def self.win?(marks, mark)
    count_max_mark(marks, mark) == 3
  end

  def self.count_max_mark(marks, mark)
    max = -1
    ROWS.each do |row|
      count = count_mark(marks, row, mark)
      if max < count then max = count end
    end
    max
  end

  def self.count_mark(marks, row, mark)
    count = 0
    row.each do |i|
      index = marks.index(i)
      if index && mark(index) == mark then
        count += 1
      end
    end
    count
  end


  def initialize(marks)
    @marks = marks
  end
  
  def addstep(step)
    @marks.push step
  end
  
  def nextstep(mark)
    return nil if @marks.length == 9  # 空いているマスがない場合は nilを返す
    return 4 if @marks.length == 0    # 最初は中心
    if @marks.length == 1 then        # 次は左上の角
      return 4 if @marks[0] != 4
      return 0
    end
    if @marks.length == 2 then        # ○の2手目
      if @marks[0] == 4 && @marks[1] % 2 == 0 then  # ×が角を取った場合はその対角線の位置に置く
        return {0=>8, 2=>6, 6=>2, 8=>0}[@marks[1]]
      else                            # 角が空いていれば角を取る
        return 0
      end
    end
    
    # 残りのマスが一つならばそこを返す
    if @marks.length == (9 - 1) then
      (0..8).each do |i|
        return i unless @marks.index(i)
      end
    end
    
    # 勝てる状況ならそれで終わる
    points = win_point(@marks, mark)
    if points.length > 0 then
      return points[0]
    end
    
    # 相手があと一歩で勝つ場合はそこに置く
    points = win_point(@marks, Marubatu.opponent(mark))
    if points.length > 0 then
      return points[0]
    end
    
    # 2箇所当りの場所があればそこに置く
    # 1手目は中心、2手目は角のはず
    if @marks.length >= 4 then
      arr = @marks.clone
      (0..8).each do |i|
        unless @marks.index(i) then
          arr.push i
          points = win_point(arr, mark)
          if points.length > 1 then
            print "2 attack point found.\n" if $DEBUG
            return i
          end
          arr.pop
        end
      end
    end
    
    # 相手に2箇所当りの場所があればそこに置く
    arr = @marks.clone
    (0..8).each do |i|
      unless @marks.index(i) then
        arr.push 4, i
        points = win_point(arr, Marubatu.opponent(mark))
        if points.length > 1 then
            print "opponent 2 attack point found.\n" if $DEBUG
          return i
        end
        arr.pop
        arr.pop
      end
    end
    
    # 残っているマスを埋める
    (0..8).each do |i|
      unless @marks.index(i) then
        print "rest point." if $DEBUG
        return i
      end
    end
  end
  
  private
  def win_point(marks, mark)
    points = Array.new
    ROWS.each do |row|
      count = Marubatu.count_mark(marks, row, mark)
      if count == 2 then
        row.each do |i|
          index = marks.index(i)
          unless index
            points.push(i)
            break
          end
        end
      end
    end
    points
  end
end


marks = (ARGV.length == 0)? []: ARGV[0].split(',').map! {|s| s.to_i}
mark = Marubatu.mark(marks.length)

ox = Marubatu.new(marks)
step = ox.nextstep(mark)
print "#{mark}:#{step}\n"

marks.push step
Marubatu.display(marks)