Project

Screen Shot


概要

オセロで、手を入力するとコンピュータが手を返すプログラム。先手か後手か、またコンピューターが読む手の数を設定できる。また、わざと負けるような手を打つこともできる。

技術的な説明

プログラミング言語はc++を使用している。AIは主に評価と探索に分かれる。

評価

ある盤面を、有利または不利と呼ばれている石の状態を探索することで評価する。このAIでは下記のような基準が使われている。

  • ・開放度 ある石の周りの空きマスの数。これが多いとのちにその石が返される可能性が高いために不利となる。
  • ・着手可能手数 自分が打てる手の数が多ければ、良い手が置くなり、悪い手を避けることができるので、有利となる。
  • ・確定石 絶対に返されることのない石のことで、これが多いほど有利となる。
  • ・辺の状態 オセロに置いて盤の一番外側の部分は重要であり、その部分で有利な形や不利な形がありそれを探索する。
  • ・X打ちやC打ち 隅の隣のマスに打つC打ちや隅のななめ内側のマスに打つX打ちは、隅を取られてしまう可能性が高くなり不利になるという理論。
探索

あらゆる手を評価してその中から一番良い手を探索する方法としてこのAIは、序盤ではNegaMax法というものを使っている。この方法では、相手が一番良い手を打つはずだと考え、それに対して一番評価の高い盤面になるように手を打つようになっている。また、本格的に手を読む前に、あらかじめ浅い読みで手を評価して、その評価値が手から読むようにしている。このことで、良い手を早めに察知して、読む必要がない悪い手を読みから外しやすくなり、計算量を減らすことができる。終盤になると、考え得る手が少なくなっていき、より深く読むことができるため、最終局面までの全ての手を読むようになる。