KotlinでAndroidアプリ#31

コンピュータ対戦
再帰処理
実装
実行

コンピュータ対戦

人対人の対戦では面白くない。そこでコンピュータと対戦できるようにする。

思考ロジックは、コンピュータ、人が交互に手を打ったと仮定し全パターン走査していく。途中コンピュータの勝ちならプラス10、人の勝ちならマイナス10などの評価値を設定し、それ以上深いレベル走査は行わないようにする。そして最終的にコンピュータにとって有利な(評価値が高い)手を決定するのだ。この方法はミニマック法と呼ばれている。

評価値は走査しているレベルで除算し算定するようにした。これはレベルが深いところのプラス10より、レベルの浅いプラス10が価値ある手だからだ。

再帰処理

レベルが深くなるにつれ、仮定で打った座標、手番、評価値など管理する情報が複雑になってしまう。さらに走査がどこで終了するか、走査していかないとわからない。これをプログラムするのはやっかいだ。そんな時は再帰処理で行う。

再帰処理は自分自信を呼び出す処理だ。呼び出すことにより新たに処理がメモリーに展開されるので、管理情報も引き渡していけばよい。

再帰処理の例として階乗計算プログラムを掲載する。

    fun  facto(n:Int):Int{  //階乗再帰処理
        Log.d("MainActivity","受取った:"+n)
        if( n ==   1){
            Log.d("MainActivity","返す:$n")
            return  n
        }
        var n2 = facto(n-1)//自分自身を呼び出す
        var n3 = n *  n2
        Log.d("MainActivity","返す:$n×$n2=$n3")
        return n3
    }
    fun test(){
        facto(5)
    }

fun facto(n:Int):Int{ //階乗再帰処理

Log.d("MainActivity","受取った:"+n)

if( n == 1){

Log.d("MainActivity","返す:$n")

return n

}

var n2 = facto(n-1)//自分自身を呼び出す

var n3 = n * n2

Log.d("MainActivity","返す:$n×$n2=$n3")

return n3

}

fun test(){

facto(5)

}

D/MainActivity: 受取った:5
D/MainActivity: 受取った:4
D/MainActivity: 受取った:3
D/MainActivity: 受取った:2
D/MainActivity: 受取った:1
D/MainActivity: 返す:1
D/MainActivity: 返す:2×1=2
D/MainActivity: 返す:3×2=6
D/MainActivity: 返す:4×6=24
D/MainActivity: 返す:5×24=120

D/MainActivity: 受取った:5

D/MainActivity: 受取った:4

D/MainActivity: 受取った:3

D/MainActivity: 受取った:2

D/MainActivity: 受取った:1

D/MainActivity: 返す:1

D/MainActivity: 返す:2×1=2

D/MainActivity: 返す:3×2=6

D/MainActivity: 返す:4×6=24

D/MainActivity: 返す:5×24=120

今回は次のレベルを探索する際に自分自信の関数を呼び出すことにする。

実装

クラスSquaresに関数stgを作成する。コンピュータ手番時にこの関数を呼び出すと全マス目を走査し最善手を返すようにした。

fun stg(next:Boolean=false,level:Double,ban:Int,narabe:Int): SerchResult? {
    val list: MutableList<SerchResult> = mutableListOf()
    for(idx1 in 0 until ban) {                              //全てのマス目を走査する
        for (idx2 in 0 until ban) {
            if(square[idx1][idx2].state != Const.KUHAKU){   //打てないなら処理しない
                continue
            }
            var score = search(idx1,idx2,next,ban,narabe)   //仮に手を打ち、評価する
            score = score / level                           //評価値をレベルに合わせ調整
            var serchresult:SerchResult?
            serchresult = SerchResult(idx2, idx1, score, next)
            if(score == 0.0 ) {                             //勝ち負けがつかないなら、深いレベルを走査
                var serchresult2 = stg(!next, level + 1, ban, narabe) //再帰処理
                if (serchresult2 != null) {
                    serchresult.score = serchresult2!!.score
                }
            }
            list.add(serchresult)                           //評価情報を格納する
            square[idx1][idx2].state = Const.KUHAKU         //仮に打った手を空白に戻す
        }
    }
    list.sortWith(Comparator {                              //評価情報をソートする
            a,b ->  a.score.compareTo(b.score)
    })

    if( list.isEmpty()){
        return   null
    }else {
        //相手番なら一番低い評価、コンピュータ番なら高い評価を選択
        var ret = if (next) list.get(0) else list.get(list.size - 1)
        //評価値が全て同じなら、ランダムに手を決定する。
        if(list.get(0).score == list.get(list.size - 1).score){
            var r = (0..list.size-1).random()
            return list.get(r)
        }else{
            return ret
        }
    }
}
//仮に手を打ち、評価する
fun search(x:Int,y:Int,next:Boolean,ban:Int,narabe:Int):Double{
    square[x][y].state= if (next) Const.BATU else Const.MARU

    var ret = jug(ban,narabe)
    if(ret != Const.KUHAKU && ret != Const.DRAW){
        //勝ちが決定なら、相手番なら-100、コンピュータ番なら100
        return if(next) -100.0 else 100.0
    }
    return 0.0
}

fun stg(next:Boolean=false,level:Double,ban:Int,narabe:Int): SerchResult? {

val list: MutableList<SerchResult> = mutableListOf()

for(idx1 in 0 until ban) { //全てのマス目を走査する

for (idx2 in 0 until ban) {

if(square[idx1][idx2].state != Const.KUHAKU){ //打てないなら処理しない

continue

}

var score = search(idx1,idx2,next,ban,narabe) //仮に手を打ち、評価する

score = score / level //評価値をレベルに合わせ調整

var serchresult:SerchResult?

serchresult = SerchResult(idx2, idx1, score, next)

if(score == 0.0 ) { //勝ち負けがつかないなら、深いレベルを走査

var serchresult2 = stg(!next, level + 1, ban, narabe) //再帰処理

if (serchresult2 != null) {

serchresult.score = serchresult2!!.score

}

list.add(serchresult) //評価情報を格納する

square[idx1][idx2].state = Const.KUHAKU //仮に打った手を空白に戻す

}

list.sortWith(Comparator { //評価情報をソートする

a,b -> a.score.compareTo(b.score)

})

if( list.isEmpty()){

return null

}else {

//相手番なら一番低い評価、コンピュータ番なら高い評価を選択

var ret = if (next) list.get(0) else list.get(list.size - 1)

//評価値が全て同じなら、ランダムに手を決定する。

if(list.get(0).score == list.get(list.size - 1).score){

var r = (0..list.size-1).random()

return list.get(r)

}else{

return ret

}

//仮に手を打ち、評価する

fun search(x:Int,y:Int,next:Boolean,ban:Int,narabe:Int):Double{

square[x][y].state= if (next) Const.BATU else Const.MARU

var ret = jug(ban,narabe)

if(ret != Const.KUHAKU && ret != Const.DRAW){

//勝ちが決定なら、相手番なら-100、コンピュータ番なら100

return if(next) -100.0 else 100.0

}

return 0.0

}

座標、評価値を格納するためのクラスSerchResutlを作成している。

package com.example.myapplication

class SerchResult(
    var x:Int = 0,
    var y:Int = 0,
    var score:Double = 0.0,
    var next:Boolean=false){
}

package com.example.myapplication

class SerchResult(

var x:Int = 0,

var y:Int = 0,

var score:Double = 0.0,

var next:Boolean=false){

}

実行

三目並べでは軽快に動いた。うゎーいパチパチパチ。でも、この後マス目を4×4にすると反応がない？？

もしかしてと思い、電卓を叩く。3×3だと9マス。えーと、相手が先番なので、残り8マス。走査対象のマス目は・・・8の階乗？、40,320。すごい数だ。計算合ってるか？

4×4のマス目だと、16-1の15の階乗。なんと、1,307,674,368,000。計算合ってるか・・・。これじゃ全マス目を走査するのは無理だ。反応が無いハズだ…

前へ＜ーーー＞つづく