RandomAIPlayer は、石を打てる場所の中からランダムに手を選びます。
具体的には、次の手順で手を選びます。
- 全てのマスを順に調べて石を打てる場所をピックアップし、1 から順に番号を振る。
- 打てる場所がひとつも無い場合はパスを宣言する。
- 打てる場所が n 箇所あったとすると、1～n のサイコロを振り、該当するマスを選択する。
思考ロジック部分のソースコードは次の通りです。
@Override
public Point decide(Board board, Color color, long givenMillisPerTurn, long remainingMillisInGame) {
Point[] availables = Point.stream()
.filter(p -> Rule.canPutAt(board, color, p))
.toArray(Point[]::new);
return availables.length == 0
? null
: availables[random.nextInt(availables.length)];
}
Java 8 で導入された Stream やラムダ式を使わないように書き換えると、次のようになります。
@Override
public Point decide(Board board, Color color, long givenMillisPerTurn, long remainingMillisInGame) {
List<Point> availables = new ArrayList<>();
for (Point p : Point.values()) {
if (Rule.canPutAt(board, color, p)) {
availables.add(p);
}
}
return availables.isEmpty()
? null
: availables.get(random.nextInt(availables.size()));
}
※上記ソースコードの中で利用している “random” は予め用意した変数です。ソースコード全体は こちら を参照してください。
このソースコードのアルゴリズムには、次のような特徴があります。
- 定数時間で終わること
リバーシ盤がどのような状態であっても、64のマスを一通り調べ上げ、サイコロを 1 回だけ振ります。そのため、石を打てるマスの数などに処理時間が左右されず、一定の時間で処理が完了します。 - 手に偏りが出ないこと
java.util.Random#nextInt(int) が一様分布の疑似乱数値を返してくれる性質を利用しているため、どの手も偏りなく選択されます。
これらは当たり前のことと感じられるかもしれませんが、必ずしもそうではありません。注意を払わずに実装を行うと、上記とは異なる、好ましくない性質を持ったアルゴリズムになってしまうことがあります。
具体例をふたつほど見てみましょう。
良くない例１：処理が定数時間内に終わらない
次のコードは、まず適当なマスをランダムに選び、そこに石を打てるのであればそこを選択し、石を打てないのであれば選択しなおすというアルゴリズムを採用しています。
@Override
public Point decide(Board board, Color color, long givenMillisPerTurn, long remainingMillisInGame) {
// 打てる場所がない場合はパスを宣言する。
if (!Rule.canPut(board, color)) {
return null;
}
Point[] allPoints = Point.values();
Point selected;
do {
// 適当なマスを選び、打てる場所が見つかるまで再選択を繰り返す。
selected = allPoints[random.nextInt(Point.HEIGHT * Point.WIDTH)];
} while (!Rule.canPutAt(board, color, selected);
return selected;
}
このようなコードを書いてはいけません！アルゴリズムの性質が劣っています！
上記のソースコードでは、石を打てる場所を選ぶために、かなりの回数、試行錯誤を繰り返す必要があります。リバーシ盤の状態によって必要な処理時間がマチマチになり、ゲームの終盤ほど多くの処理時間が必要となります。
ワンランク上のプログラマを目指すのであれば、単に正しい結果が得られるかどうかだけでなく、アルゴリズムの性質にも目を向けるようにしましょう。
※ 必ずしも「良くない例１」の処理時間が正規のソースコードの処理時間よりも長くなる訳ではありません。あるマスに打てるか否かを調べるコストと疑似乱数値を取得するコストの比によっては、「良くない例１」の期待処理時間の方が短くなることもあり得ます。しかし、処理時間だけを見て判断するのではなく、そのベースにあるアルゴリズムの性質に目を向けるようにしましょう。
良くない例２：手の選択が偏る
次のソースコードは、順序付けされていない並列ストリームでは処理順が保証されないことを利用して、手をランダムに選択している（つもりの）コードです。
@Override
public Point decide(Board board, Color color, long givenMillisPerTurn, long remainingMillisInGame) {
// 並列ストリームの処理順が保証されないことを利用して手を選択する。
return Point.parallelStream().unordered()
.filter(p -> Rule.canPutAt(board, color, p))
.findFirst().orElse(null);
}
同じく、次のコードは java.util.Set では反復順が保証されないことを利用して、手をランダムに選択している（つもりの）コードです。
@Override
public Point decide(Board board, Color color, long givenMillisPerTurn, long remainingMillisInGame) {
Set<Point> availables = new HashSet<>();
for (Point p : Point.values()) {
if (Rule.canPutAt(board, color, p)) {
availables.add(p);
}
}
return availables.isEmpty()
? null
: availables.iterator().next();
}
特に後者の Set を使った方法は一見ランダムに見えますが、どちらのコードも手が偏ります。
処理結果が保証されないこととランダムであることは異なります。
処理結果をランダムにしたい場合は、まずは java.util.Random を使うようにしましょう。