石取りゲームで遺伝的アルゴリズムの実験 その2
北本です。
前回は、実験やプログラムの概要を説明しました。
今回からはその実装について取り上げていきたいと思います。
プログラムの作成に当たって書いたすべてのコードは紹介しきれませんので、要点となる箇所を部分的に取り上げていく感じになります。
今回は、石取りゲーム部分のコードを紹介します。
Visual StudioでダイアログベースのMFCアプリケーションのプロジェクトを作成して自動生成された
MFCダイアログクラスCIshitoriGADlg内にコードを作成します。
以下のExecGame関数は、石取りゲーム一試合をプレイヤー(遺伝的アルゴリズムで生成した個体)とランダムに決定した個数の石を取る相手とで対戦させ、前者が勝てば1、負ければ0を返します。試合数が奇数の場合プレイヤーが先手、偶数の場合は後手となります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | int CIshitoriGADlg::ExecGame() { memset(m_StoneHolder, 0, sizeof(m_StoneHolder)); BYTE opponentPattern[NUMBER_OF_STONES] = { 0 }; // 相手の石取得パターン。取得済み石数が(添数)個の時にターンが回ってきた場合、石を何個を取るか。 SetActPattern(opponentPattern); // 相手の石取得パターンをランダムに設定 int takenStonesCount = 0; // 取得済みの石の数 int turn = 0; BOOL playerTurn; // プレイヤーのターンであるか while (takenStonesCount < NUMBER_OF_STONES) { playerTurn = !(turn % 2 == m_GameCnt % 2); int numberOfTakingStones; // ターンに取る石の数 if (playerTurn) { // プレイヤーのターン numberOfTakingStones = m_CurrentGenerationData.data[m_IndividualCnt].genes[takenStonesCount]; // 取得する石の数として個体の遺伝子情報を参照 } else { // 相手のターン numberOfTakingStones = opponentPattern[takenStonesCount]; } for (int i = 0; i < numberOfTakingStones; i++) { m_StoneHolder[takenStonesCount + i] = playerTurn ? 1 : 2; } takenStonesCount += numberOfTakingStones; turn++; } return playerTurn ? 0 : 1; // プレイヤーのターンで取得済み石数が総数に達していたら負け、そうでなければ勝ち } |
コードの中にクラスのメンバ変数、自作の関数、定数などがいろいろ出てきてしまっているので概要を説明します。
●定数
- const int NUMBER_OF_STONES = 21
石の総数。
●メンバー変数
- int m_StoneHolder[NUMBER_OF_STONES]
(添数 + 1)番目の石を取ったのは誰か。UI表示用に使っています。
0:未取得、1:プレイヤー、2:相手 - int m_GameCnt
現在の第何試合か。 - int m_IndividualCnt
現在の何個目(ゼロオリジン)の個体の試合をしているか。 - GENERATION_DATA m_CurrentGenerationData
現世代100個体の遺伝子情報や勝数が記憶されている。
GENERATION_DATA構造体については後述。
●関数
- void SetActPattern(BYTE* array)
取得済み石数が(添数)個の時にターンが回ってきたら何個石を取るかの情報をランダムでarrayに設定します。ここでは、相手の行動パターンの生成に使っていますが、第1世代の個体の遺伝子情報をランダム設定するのにも使っています。詳細は次回に取り上げます。
GENERATION_DATA構造体とその中で使われているINIDIVIDUAL_DATA構造体は以下のように定義しています。
1 2 3 4 5 6 7 8 9 10 | struct INDIVIDUAL_DATA { BYTE genes[NUMBER_OF_STONES]; // 個体の遺伝子情報。取得済み石数が(添数)個でターンが回ってきた場合、取る石の数。 int numberOfWins; // 個体の勝数(試合が未完了の時は-1) }; struct GENERATION_DATA { INDIVIDUAL_DATA data[NUMBER_OF_INDIVIDUALS]; }; |
NUMBER_OF_INDIVIDUALSは一世代あたりの個体数です(100で定義)。
また、ExecGame関数はDoGame関数を介して呼ばれるようになっており、UI上のボタン(前回参照)が押された場合はこのDoGeme関数を実行します。
一個体の全試合が終われば次の個体へ、一世代の全試合が終われば新たな世代を生成して世代交代するようになっています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | void CIshitoriGADlg::DoGame() { m_GameCnt++; m_WinCnt += ExecGame(); UpdateStatusStrings(); // UIのテキスト更新 Invalidate(); if (m_GameCnt >= NUMBER_OF_GAMES) { // 個体の全試合が終了 m_CurrentGenerationData.data[m_IndividualCnt].numberOfWins = m_WinCnt; // 勝数を記憶 m_WinCnt = 0; m_GameCnt = 0; m_IndividualCnt++; if (m_IndividualCnt >= NUMBER_OF_INDIVIDUALS) { // 現世代の全個体の試合が終了 WriteGeneData(&m_CurrentGenerationData, m_GenerationCnt); // 現世代の遺伝子情報と勝ち数を記録 m_IndividualCnt = 0; m_GenerationCnt++; GENERATION_DATA nextGenerationData; GetNextGeneration(m_CurrentGenerationData, &nextGenerationData); // 現世代を元に次世代を生成 m_CurrentGenerationData = nextGenerationData; // 世代交代 for (int i = 0; i < NUMBER_OF_INDIVIDUALS; i++) { m_CurrentGenerationData.data[i].numberOfWins = -1; } } } } |
ここでもメンバ変数や自作の関数、定数が出てきているので説明します。
●定数
- const int NUMBER_OF_GAMES = 100
1個体が行う試合の数
●メンバー変数
- int m_WinCnt
現在の個体の勝数
●関数
- void UpdateStatusStrings()
UIのテキスト表示の更新 - BOOL WriteGeneData(const GENERATION_DATA* data, int generation)
世代の情報をファイルに書き出し。次回に詳細を取り上げます。 - void GetNextGeneration(GENERATION_DATA currentGeneration, GENERATION_DATA* nextGeneration)
currentGenerationを元に、次世代を生成してnextGenerationに渡す。次々回に詳細を説明します。
次回は今回のコードの中で呼ばれていた関数のうちSetActPattern、WriteGeneDataを紹介します。
そして、次々回には本実験の肝要となるGetNextGenerationについて取り上げたいと思います。