読者です 読者をやめる 読者になる 読者になる

kivantium活動日記

プログラムを使っていろいろやります

遺伝的アルゴリズムで棒倒しシミュレーション

後輩が棒倒しを話題にしているのを見てなんとなく棒倒しのシミュレーションのようなものを作ってみたくなりました。以前から遺伝的アルゴリズムで何かをやってみたいと思っていたので、遺伝的アルゴリズムを絡めて少し遊んでみました。

棒倒しとは

2チームが互いに相手チームの棒を倒し合い、先に倒した方が勝ちというゲームです。各チームは攻撃と守備にメンバーを分け、攻撃は相手の棒を倒すことを、守備は相手の攻撃から棒を倒すことを目標とします。
http://www.geocities.jp/my_seawinds/image/04.11bodai_kaikosai38.jpg

ルール説明

人間がやるような棒倒しを再現するのは大変なので、遺伝的アルゴリズムが使えるようにルールを簡略化しました。

初期配置

f:id:kivantium:20150302204158p:plain:w400

  • 赤組の5人が攻撃、白組の6人が守備を担当します。白組の6人のうち1人は棒の近くの守備を担当します。
  • 試合時間は20秒で、攻撃側が棒領域内(左の大きな円)に入れば得点となります。
  • 守備側が攻撃側にタッチすると、タッチされた攻撃側の選手は4秒間行動不能になります。
  • 白組側には防衛プログラムを入れてあります。
    • 直線上に並んだ5人は一番近くの行動不能でない赤組の選手に向けて移動してタッチを狙います
    • 棒近くの1人(青っぽい選手)は棒に触れていない中で最も棒に近い赤組の選手に向けて移動してタッチを狙います。
  • 赤組の攻撃パターンは遺伝的アルゴリズムで進化させていきます。
    • 攻撃パターンは20個の整数で記述され、各整数は移動方向を表します。1秒ごとに攻撃パターンに基づいて移動方向が変化します。
    • 各整数は9で割った余りによって「現在の移動方向を維持」あるいは「8方向のいずれかに移動方向を変更」という意味を持ちます。
  • 選手によって速度は異なります。速い選手は真ん中に、遅い選手は端に配置してあります。棒の近くの守備が最も速いです。

遺伝的アルゴリズム

赤組の5人の行動パターンを合わせた100個の整数の組を「個体」と呼ぶことにします。各世代は5個体から構成されます。世代交代は次のように行いました。

  • 第0世代の個体0の行動パターンは全て「現在の移動方向を維持」とする
  • 第0世代の個体1〜4の行動パターンは個体0の行動パターンから1つの整数をランダムに変えて作る
  • 各世代の全固体についてシミュレーション結果を求め、ゲーム終了時点で各選手と棒までの距離の和が最も少ない個体を最優秀個体とする
  • n世代目で最優秀個体をn+1世代目の個体0とし、個体1〜4の行動パターンは個体0の行動パターンから1つの整数をランダムに変えて作る

これを何世代も繰り返します。

プログラム

この記事のプログラムを元に作りました。

ライフゲーム - 人工知能に関する断創録

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import pygame
from pygame.locals import *
import random
import sys
import math
import copy

SCR_RECT = Rect(0, 0, 800, 600)  # スクリーンサイズ
LEFT, MIDDLE, RIGHT = -1, 0, 1  #左右移動方向
UP, MIDDLE, DOWN = -1, 0, 1  #上下移動方向

#赤組選手クラス
class RedMan:
    def __init__(self, speed):
        self.speed = speed
        self.x = 0
        self.y = 0
        self.x_direction = MIDDLE 
        self.y_direction = MIDDLE 
        self.life = 0
        self.command = []
#白組選手クラス
class WhiteMan:
    def __init__(self, speed):
        self.x = 0
        self.y = 0
        self.speed = speed
#メインの動作
class PoleDown:
    def __init__(self):
        #学習中にウィンドウ表示があると処理が遅くなるため
        #ウィンドウの有無を選択できるようにする
        self.windowmode=True
        if self.windowmode:
        # ウィンドウ設定など
            pygame.init()
            screen = pygame.display.set_mode(SCR_RECT.size)
            pygame.display.set_caption("棒倒しシミュレーション")
            self.font = pygame.font.SysFont(None, 20)
        # 各変数の初期化
        self.generation = 1000
        self.gene = 0
        self.framenum = 0
        self.command = 0
        self.score = [0,0,0,0,0]
        # 遺伝子の初期設定
        # もうちょいうまく書く方法がありそうなものだが……
        self.redgene = \
        [[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]],
         [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]],
         [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]],
         [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]],
         [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]]

        # 第一世代の変異
        for i in range(4):
            self.redgene[i][random.randrange(5)][random.randrange(20)] = random.randrange(9)
        
        #赤組選手5人の作成
        self.red =[RedMan(1.0),
                   RedMan(1.5),
                   RedMan(2.0),
                   RedMan(1.5),
                   RedMan(1.0)]

        #白組選手6人の作成
        self.white=[WhiteMan(1.0),
                    WhiteMan(1.5),
                    WhiteMan(2.0),
                    WhiteMan(1.5),
                    WhiteMan(1.0),
                    WhiteMan(2.5)]
        # 位置等の初期化
        self.initialize(self.gene)

        # メインループ
        if self.windowmode:
            clock = pygame.time.Clock()
        while True:
           self.update()           #各選手の位置を更新
           if self.windowmode:
               clock.tick(1)         #ディレイの設定
               self.draw(screen)       #情報の描画
               pygame.display.update() #描画の反映
                #終了処理
               for event in pygame.event.get():
                   if event.type == QUIT:
                       pygame.quit()
                       sys.exit()
                   elif event.type == KEYDOWN:
                       if event.key == K_ESCAPE:
                           pygame.quit()
                           sys.exit()
   
    #初期化
    def initialize(self, gene):
        #状態の初期化
        self.framenum = 0
        self.command = 0
        #各選手の位置・命令セットを初期化
        for i in range(5):
            self.red[i].x = 600.0
            self.red[i].y = 100.0 + 100.0*i
            self.red[i].x_direction = MIDDLE
            self.red[i].y_direction = MIDDLE
            self.red[i].life = 0
            self.white[i].x = 200.0
            self.white[i].y = 100.0 + 100.0*i
            self.red[i].command = self.redgene[gene][i]
        self.white[5].x = 150.0
        self.white[5].y = 300.0
    
    #距離を求める関数
    def distance(self, x, y):
        return math.sqrt(x**2+y**2)

    #選手の位置を更新
    def update(self):
        #20秒経過した時の処理
        if self.framenum == 999:
            self.evaluate(self.gene)    #点数計算
            #1世代が終わった時
            if self.gene == 4:
                #その世代で最高得点(棒中心までの距離が最小)を調べる
                bestgene = self.score.index(min(self.score))
                bestscore = copy.deepcopy(self.redgene[bestgene])
                #次の世代の5個体に最良の遺伝子を渡す
                for i in range(5):
                    self.redgene[i] = copy.deepcopy(bestscore)
                    self.score[i] = 0.0
                #4個体には変異を起こす
                for i in range(4):
                    self.redgene[i][random.randrange(5)][random.randrange(20)] = random.randrange(9)
                #世代を変える
                self.generation += 1
                self.gene = 0
                #20世代ごとに保存
                if self.generation % 50 == 0:
                    print "generetion", self.generation
                    print bestscore
            #世代交代でなければ次の個体を試す
            else:
                self.gene += 1
            self.initialize(self.gene)
        #赤組の向き更新
        if self.framenum % 50 == 0:
            #1sごとに命令セットを見て移動する向きを変更
            self.command += 1
            for i in range(5):
                #移動停止時間のカウント
                if self.red[i].life > 0:
                    self.red[i].life -= 1;
                #向きの変更
                if self.red[i].command[self.command] % 9 == 1:
                    self.red[i].x_direction = LEFT
                    self.red[i].y_direction = MIDDLE
                if self.red[i].command[self.command] % 9 == 2:
                    self.red[i].x_direction = LEFT
                    self.red[i].y_direction = UP
                if self.red[i].command[self.command] % 9 == 3:
                    self.red[i].x_direction = MIDDLE
                    self.red[i].y_direction = UP
                if self.red[i].command[self.command] % 9 == 4:
                    self.red[i].x_direction = RIGHT
                    self.red[i].y_direction = UP
                if self.red[i].command[self.command] % 9 == 5:
                    self.red[i].x_direction = RIGHT
                    self.red[i].y_direction = MIDDLE
                if self.red[i].command[self.command] % 9 == 6:
                    self.red[i].x_direction = RIGHT
                    self.red[i].y_direction = DOWN
                if self.red[i].command[self.command] % 9 == 7:
                    self.red[i].x_direction = MIDDLE
                    self.red[i].y_direction = DOWN
                if self.red[i].command[self.command] % 9 == 8:
                    self.red[i].x_direction = LEFT
                    self.red[i].y_direction = DOWN

        #赤組の位置更新
        #生きていたら現在の移動向きに移動
        for i in range(5):
            if self.red[i].life == 0:
                if self.red[i].x < 800 and self.red[i].x > 0:
                    self.red[i].x += self.red[i].x_direction*self.red[i].speed
                if self.red[i].y < 600 and self.red[i].y > 0:
                    self.red[i].y += self.red[i].y_direction*self.red[i].speed

        #白組の位置更新
        #5人は最も近い生きている白組に向けて移動
        for i in range(5):
            distance = sys.maxint
            target = 6
            for j in range(5):
                if self.red[j].life == 0:
                    tmp = self.distance((self.white[i].x - self.red[j].x),(self.white[i].y - self.red[j].y))
                    if tmp < distance:
                        distance = tmp
                        target = j
            if target != 6:
                if self.white[i].x > self.red[target].x:
                    self.white[i].x -= self.white[i].speed
                if self.white[i].x < self.red[target].x:
                    self.white[i].x += self.white[i].speed
                if self.white[i].y > self.red[target].y:
                    self.white[i].y -= self.white[i].speed
                if self.white[i].y < self.red[target].y:
                    self.white[i].y += self.white[i].speed

        #白組のうち一人は棒に触れていないなかで最も棒に近い選手に近づく
        distance = sys.maxint
        target = 6
        for j in range(5):
            tmp = self.distance((100.0 - self.red[j].x),(300.0 - self.red[j].y))
            if tmp > 30 and tmp < 120 and tmp < distance:
                distance = tmp
                target = j
        if target < 5:
            if self.white[5].x > self.red[target].x:
                self.white[5].x -= self.white[5].speed
            if self.white[5].x < self.red[target].x:
                self.white[5].x += self.white[5].speed
            if self.white[5].y > self.red[target].y:
                self.white[5].y -= self.white[5].speed
            if self.white[5].y < self.red[target].y:
                self.white[5].y += self.white[5].speed
        
        #赤組選手の生死判定
        #白組選手のいずれかにタッチされていたら約5s移動が止まる
        for i in range(5):
            for j in range(6):
                if self.distance((self.red[i].x-self.white[j].x),(self.red[i].y-self.white[j].y)) < 2.0:
                    self.red[i].life = 4 
            #棒の中心近くに触れても止まる
            if self.distance((self.red[i].x-100.0),(self.red[i].y-300.0)) < 20.0:
                self.red[i].life = 4
        #フレーム番号の更新
        self.framenum += 1

    #点数計算
    #棒中心までの距離の和。小さいほどよい
    def evaluate(self, gene):
        score = 0
        for i in range(5):
            score += self.distance((100.0 - self.red[i].x),(300.0 - self.red[i].y))
        self.score[gene] = score
            
    #棒と選手の描画
    def draw(self, screen):
        #背景(黒)の描画
        pygame.draw.rect(screen, (0,0,0), Rect(0,0,800,600))
        #棒の描画
        pygame.draw.circle(screen, (200,200,200), (100, 300), 30)
        #赤組選手の描画
        for i in range(5):
            if self.red[i].life == 0:
                pygame.draw.circle(screen, (255,0,0), (int(self.red[i].x),int(self.red[i].y)),6)
            else:
                pygame.draw.circle(screen, (100,0,0), (int(self.red[i].x),int(self.red[i].y)),6)
        #白組選手5人の描画
        for i in range(5):
            pygame.draw.circle(screen, (255,255,255), (int(self.white[i].x),int(self.white[i].y)),6)
        #白組マーカーの描画
        pygame.draw.circle(screen, (150,150,255), (int(self.white[5].x),int(self.white[5].y)),6)
        #世代と遺伝子の描画
        info = self.font.render("generation "+str(self.generation)+" gene "+str(self.gene), True, (255,255,255))
        screen.blit(info, (0,0))

#実行
if __name__ == "__main__":
    PoleDown()

結果

3000世代まで学習した結果の動画がこちら

遺伝的アルゴリズムで棒倒しシミュレーション ‐ ニコニコ動画:GINZA