이 글은 Retty inc. Advent Calendar의 13일째 글입니다.
어제는 Ryosuke Murai씨@RyosukeMurai의Retty에서 자주 사용하는 베일스 필터(채식 필터 아님)였습니다.
안녕하세요.Retty inc.의 sakata. Retty Advent calendar 3편(샘플 코드에 사용된 것 제외)의 Kotlin 기사입니다. Retty 회사 내에 Kotlin 격추 세력이 있다는 것을 알아차릴 수 있을 것 같습니다. 여러분 Kotlin이 썼습니까?귀엽다.
항간에는 DeepLearning이 유행하고 있습니다. Retty도 점차 제품에 적용되고 있습니다. DeepLearning은 프로그램 라이브러리의 관계에서 Python과 C++를 많이 사용합니다.Kotlin은 귀엽기 때문에 AI도 쉽게 걸린다. 그래서 이 글에서 우리는 Kotlin으로 바둑판 게임 AI를 쓴다. (그러나 DeepLearning은 아니다)

장르를 결정하다

우선 AI가 해결해야 할 문제는 다음과 같은 조건(마감)을 충족하면 된다.

간단한 설치

판면의 좋고 나쁨을 수치화하기 쉽다

게임의 진행 패턴이 엄격하다

그래서 이번에는 양면(오셀로)으로 하고 싶어요. 이번과 같은 구조로 체스, 장기, 바둑이든 오리지널 바둑판이든 할 수 있어요.

게임 구현

gradle 프로젝트를 만들고 kotlin으로 명령행 프로그램을 만듭니다. Kotlin이 귀엽기 때문에 명령행 프로그램을 만드는 것도 간단합니다.
build.gradle (발췌)

apply plugin: 'kotlin'
apply plugin: 'application'

mainClassName = "io.github.yusaka39.reversi.commandline.main.MainKt"

dependencies {
    compile "org.jetbrains.kotlin:kotlin-stdlib:$kotlin_version"
    compile project(':game')
}

run {
    standardInput = System.in
}

일부 발췌문입니다. 대체로 평소와 같습니다. 안드로이드 앱을 언제 만들고 싶으십니까? 게임 처리만 담당하는 서브모듈game을 만들겠습니다.

게임 구현

이후 다양한 유형의 유저(인간이 입력한 유저, 이번에 설치된 AI, 인터넷을 통해 조작할 수 있는 유저 등)각종 출력 인터페이스를 실현할 가능성을 고려하여 게임 중의 정보 디스플레이와 유저 정의 인터페이스를 AbstractFactory 모드로 재편성한다.루트 모듈에서 이를 사용하여 CUI 반전을 설치합니다.

Pluggable로 만들기

가까스로 모듈을 끊었는데,실행 시 외부에 설치된 game 모듈에 포함된 인터페이스의 설치를 조립하고 다양한 설치 유저와 승부를 겨룰 수 있다면 즐겁다. 따라서 간단한 플러그인 구조를 만든다. 매개 변수에 전달되는 path에서jar를 찾아서 game의 하위 클래스를 찾아라.
Main.kt(발췌)

private fun getPlayerFactoryClasses(args: Array<out String>):
        List<Class<out AbstractPlayerFactory>> {
    val urls = args.getOrNull(0)?.let {
        File(it).listFiles { f, name -> name.matches(Regex(""".*\.jar$""")) }
                .filterNotNull()
                .map { it.toURI().toURL() }
    } ?: emptyList()

    return ClassPath.from(URLClassLoader.newInstance(urls.toTypedArray())).topLevelClasses
            .map { try { it.load() } catch (e: NoClassDefFoundError) { null } }
            .filter {
                it?.let {
                    it != AbstractPlayerFactory::class.java &&
                            AbstractPlayerFactory::class.java.isAssignableFrom(it)
                } ?: false
            }
            .map { it as Class<out AbstractPlayerFactory> }
}

이번에는 학급 통행증을 찾기 위해 guice를 이용했다.
그런 다음 입력에서 PlayerFactory를 선택할 수 있습니다.

랜덤에 있는 플레이어를 한번 해보도록 하겠습니다.

동작을 확인하기 위해 랜덤에 설치한 플레이어(앞으로 랜덤 군)를 사용해 보자. 유효한 타자 중 랜덤으로 하나를 선택해보자.

가동하다

여기 오면 좀 놀 수 있어요.

$ ./gradlew distTar
$ cd build/distributions/
$ tar -xf reversi-1.0-SNAPSHOT.tar
$ ./reversi-1.0-SNAPSHOT/bin/reversi

일

이동
랜드 군을 몇 번 같이 싸우게 해 봐.

$ for i in $(seq 0 200); do ./reversi-1.0-SNAPSHOT/bin/reversi << EOF | grep 'WIN' >> log; done   
1
1
EOF
$ sort log | uniq -c
  91 CPU[BLACK] WIN
 105 CPU[WHITE] WIN

무승부는 계산되지 않았다. 단순한 바둑판 게임의 경우 선방이 유리한 경우가 많지만 반전도 그렇지 않은 것 같다. 시행 횟수를 늘리면 결과가 바뀔 수 있다.

AI 설치

이곳에 도착하면 AI를 설치할 수 있다. 이번 AI는 자신의 손을 선택할 때 사용하는 알고리즘을 알파베타법을 이용한다.

min-max법

이것은 알파베타법의 기초 알고리즘입니다. 트리 구조로 게임의 전개를 나타내는 지점에서 자신에게 유리한 전개를 선택하는 데 사용됩니다.
앞을 보고 어떤 국면이 얼마나 유리한지 평가해야 한다는 생각은 다음과 같다.
1. 보고 싶은 바둑판이 상대방에게 돌아간다면 상대방은 이 바둑판 이후에 나타난 모든 바둑판 중 최악(불리), 즉 상대방에게 가장 유리한 (평가 가치가 가장 적은) 손을 내밀어야 한다.따라서 다음에 나타나는 모든 국면의 평가치의 최소치를 국면의 평가치로 설정하면 된다.
2. 읽고 싶은 바둑판이 자신에게 돌아오면 그 바둑판 뒤에 나오는 모든 바둑판에서 가장 좋은 평가(가치 평가)를 할 수 있다.따라서 앞으로 나타날 모든 국면의 평가치의 최대치를 국면의 평가치로 설정하면 된다.
참조

alpha-beta법

min-max법의 탐색에 가지치기 구조를 추가했다.wikipedia 이해하기 쉬운 도해가 있다.
min-max의 설명을 통해 알 수 있듯이 이번에 제작된 AI의 강도는 평가 판면의 함수의 좋고 나쁨과 게임 트리의 몇 손을 단말기 노드로 평가 판면(i.e.몇 손을 읽음)에 의해 결정된다. 가지치기 효율이 높은 손의 수가 증가하고 검색 속도도 빨라졌다고 볼 수 있다.

실시

새로운gradle 프로젝트를 만들고libs 디렉터리를 만들며 방금 만든 주체dist의lib복제AbstractPlayerFactory모듈의jar를 마음대로 설치합니다.
AlphaBetaPlayer.kt

    override fun handleTurn(board: Board, validMoves: List<Grid>): Grid {
        val threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors())
        val treeToScore = ConcurrentHashMap<Node, Int>()
        validMoves.forEach {
            threadPool.execute {
                val tree = Node(this.side, it, board.clone().apply {
                    this.put(this@AlphaBetaPlayer.side, it)
                })
                treeToScore[tree] = evaluateScore(tree)
            }
        }
        threadPool.shutdown()
        threadPool.awaitTermination(1, TimeUnit.MINUTES)
        return treeToScore.maxBy { it.value }!!.key.move
    }

이번에는 이런 느낌으로 설치되었습니다. game에서alpha-beta법 평가 트리를 사용합니다. 평가 함수는 잠시

自分の石の数 - 相手の石の数

요즘은 싱글 코어 CPU를 거의 보지 않기 때문에 처음 지점을 기준으로 병렬 탐색을 합니다. 1분만 기다리지 않고 끝내면 당시 가장 높은 평가를 받았던 손으로 돌아갑니다. 인터럽트 구조를 쓰는 것이 번거롭기 때문에 나머지 임무는 시간의 흐름에 맡깁니다.(거의 1분을 넘지 않았다)

랜드가 너랑 싸우래.

AI가 구축된 프로젝트로 만든jar를 적당한 곳에 삽입합니다. 이번에는 distTar를 압축하는 과정에서players 디렉터리를 만들고 설정했습니다.

$ ./bin/reversi $(pwd)/players/

이 웹 페이지
jar 파일을 잘 읽었습니다!

이겼다!몇 번 싸우라고.

$ for i in $(seq 0 20); do ./bin/reversi $(pwd)/players << EOF | grep 'WIN' >> log; done
0
2
EOF
$ sort log | uniq -c
  17 ALPHA_BETA[BLACK] WIN
   4 CPU[WHITE] WIN

생각보다 결과가 좋았어요.

개선 사례

평가 함수 개선

이번에는 단순히 돌의 수량 차이를 평가치로 사용하지만 반전된 돌은 가치가 떨어진다. 예를 들어 자신이 취한 각과 인접한 변에 있는 자신의 돌은 적의 돌이 되지 않기 때문에 가치가 높다고 할 수 있다. 혹은,반전에서 다음 라운드에서 상대방이 놓을 수 있는 곳을 줄이는 것이 효과적인 전법이기 때문에 상대방의 그것도 평가 함수에 편입할 수 있다. 예를 들어 다음과 같은 내용을 고려할 수 있다.

\boldsymbol{x} := [自分の石の数, 相手の石の数, 相手が置ける手の数...] \\
\boldsymbol{w} := [それぞれのパラメータにかかるウェイト...] \\
score = \sum_{i=0}^{パラメータの数}\boldsymbol{w}_i\boldsymbol{x}_i

평가 함수 조정

위의 예를 사용합니다. 이런 상황에서 평가 함수의 좋고 나쁨은 권중의 값에 의해 결정됩니다. 예를 들어 자신에게 유리한 매개 변수에 마이너스 권중을 가하면 전력으로 지는 AI가 됩니다. 하지만 권중을 하나하나 조정하여 강한지 확인하고,뭐 공부 해요?조정해보는 건 어떨까요? 잘 모르겠지만 가능성을 많이 느꼈기 때문에 좋아합니다. 무게를 유전자로 해서 많은 유저를 만들어서 싸우게 하세요. 승률이 높은 걸 살려주세요. 강한 조합의 무게가 생길 거예요.나는 정말 여기까지 하고 싶지만, 시간이 부족하다.

원래 다른 수단으로 손을 선택했어요.

딥러닝은 어때요? 강해질 거예요.

인도물

AI를 천천히 설치하려는 사람들에게 유용할 수 있기 때문에 이번 기사를 위해 만든 것을 MIT 라이선스로 공개했다.

reversi 바디

alpha-beta의 AIPlayer유전 알고리즘

Kotlin은 매력이 많지만 말하자면 길어지고 다른 기사도 많기 때문에 이 기사에서 Kotlin의 매력은 모두'귀엽다'github를 통해