【Java】【HitAndBlow】組み合わせ爆発？？使用数字の桁数と実行時間の関係

以前ヒットアンドブローというゲームをJavaで書きました。
初めてクラス図書いてみた
そこそこ戦略的に動くAIつくった！

あれからコードの手直しして定数を置いておくクラスを作りました。

package play;

/**
 * @author waterlow
 * 定数を宣言するクラス
 */
public class Rules {

	/**
	 * CHAR_USED_IN_THIS_GAMEの文字を1回ずつ使ってゲームに使う文字列を作る
	 */
	public static final String[] CHAR_USED_IN_THIS_GAME = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
	/**
	 * HitAndBlow.makeOneRandomCodeがCODE_LENGTHの値をもとに文字列の長さを決める
	 */
	public final static int CODE_LENGTH = 4;	// 0 <= CODE_LENGTH <= CHAR_USED_IN_THIS_GAME.length
	/**
	 * Aiが最初に宣言する"012..."という文字列を作っておく
	 */
	public static String firstCall = "";
	static {
		for(int i = 0; i < CODE_LENGTH ; i++){
			firstCall += CHAR_USED_IN_THIS_GAME[i % CODE_LENGTH];
		}
	}

	/**
	 * 他のクラスからインスタンスを生成できないよう
	 * 何もしないプライベートコンストラクタを用意しておく
	 */
	private Rules() {
	}
}

CODE_LENGTHを書き換えることで自由にゲームで使う数字の桁数を変えられるようになりました。
AIを使って答えを勝手に出すことも可能です。

ただこのゲーム、今のところ10個の数字を使って数字を作ります。そのため使える全パターンを考えると
　1桁の時：10通り
　2桁の時：10×9 = 90通り
　3桁の時：10×9×8 = 720 通り
　4桁の時：10×9×8×7 = 5,040通り
　5桁の時：10×9×8×7×6　= 30,240通り
　...
　10桁の時：10×9×…×2×1 = 3,628,800通り

…AIの実行時間ベースで見ていますが3桁だと1秒以下、4桁で20～30秒、5桁で約30分かかります。
試しに今朝10ケタで流していますが、1手目を宣言してから動かなくなりました^^;
どこで時間がかかっているのか探る必要がありそうです。
ソースを改善すればもっと早く動くようになるかもしれないので、今後取り組んでいきます。

(作ったソースは以下になります)

package play.ai;

import static play.HitBlowResult.*;
import static play.Rules.*;
import globalfunction.Permutation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import play.HitBlowResult;
import play.Player;

public class Ai extends Player {
	private static ArrayList<String> remainCodeForAnswer;
	private static final Permutation P = new Permutation(CHAR_USED_IN_THIS_GAME, CODE_LENGTH);
	static {
		P.startPermutation();
		remainCodeForAnswer = new ArrayList<>(P.result);
	}


	// １つの結果を入れると残りの手を求める(戻り値:ArrayList<String>)
	private static ArrayList<String> renewRemainCode(ArrayList<String> remainCodeForAnswer, HitBlowResult result) {
		ArrayList<String> returnList = new ArrayList<>();
		for (String s : remainCodeForAnswer) {
			HitBlowResult resultTmp = answerHitBlowResult(s, result.getCode());
			if (result.equals(resultTmp)) returnList.add(s);
		}
		return returnList;
	}

	// １つの結果を入れると残りの手を求める(戻り値:int)
	private static int renewRemainCodeInt(ArrayList<String> remainCodeForAnswer, HitBlowResult result) {
		int returnInt = 0;
		for (String s : remainCodeForAnswer) {
			HitBlowResult resultTmp = answerHitBlowResult(s, result.getCode());
			if (result.equals(resultTmp)) returnInt++;
		}
		return returnInt;
	}


	// ある文字列を宣言したときに考えられる結果と正解の可能性のある文字列を返却する(戻り値:ArrayList<ArrayList<String>>)
	private static HashMap<String, ArrayList<Integer>> getAllRemainNum(ArrayList<String> remainCodeForAnswer) {

		HashMap<String, ArrayList<Integer>> bbbbb = new HashMap<>();

		for (String s : P.result) {
			// sに対応する各場合の残りの可能性
			ArrayList<Integer> tmpLists = new ArrayList<>();
			// hitCountは0から4を動く
			for (int hitCount = 0; hitCount <= CODE_LENGTH; hitCount++) {
				// blowCountは0から4-hitCountを動く
				for (int blowCount = 0; blowCount + hitCount <= CODE_LENGTH; blowCount++) {
					// 3hit1blowははじく
					if (hitCount == CODE_LENGTH - 1 && blowCount == 1) continue;
					// 結果のインスタンスを作る
					HitBlowResult hbresult = new HitBlowResult(s, hitCount, blowCount);
					tmpLists.add(renewRemainCodeInt(remainCodeForAnswer, hbresult));
				}
			}
			bbbbb.put(s, tmpLists);
		}
		return bbbbb;
	}

	// 期待値を求める
	private static HashMap<String, Double> getAllKitaichi(ArrayList<String> remainCodeForAnswer) {
		HashMap<String, ArrayList<Integer>> map = getAllRemainNum(remainCodeForAnswer);
		HashMap<String, Double> returnMap = new HashMap<>();
		for (String key : map.keySet()) {
			int sum = 0;
			int Denominator = 0;
			for (int size : map.get(key) /* ←ArrayList<Integer> */) {
				sum += size * size;
				Denominator += size;
			}
			if (Denominator > 0) {
				double ave = (double) sum / Denominator;
				returnMap.put(key, ave);
			}
		}
		return returnMap;
	}

	// 期待値最少の文字列を求める
	private static ArrayList<String> getMinumumKitaichi(ArrayList<String> remainCodeForAnswer) {
		HashMap<String, Double> tmpMap = getAllKitaichi(remainCodeForAnswer);
		List<Map.Entry<String, Double>> entries = new ArrayList<Map.Entry<String, Double>>(tmpMap.entrySet());
		Collections.sort(entries, new Comparator<Map.Entry<String, Double>>() {
			@Override
			public int compare(Entry<String, Double> entry1, Entry<String, Double> entry2) {
				return ((Double) entry1.getValue()).compareTo((Double) entry2.getValue());
			}
		});
		ArrayList<String> returnList = new ArrayList<>();
		double previousValue = 0;
		double currentValue = 0;
		for (Map.Entry<String, Double> entry : entries) {
			returnList.add(entry.getKey());
			previousValue = currentValue;
			currentValue = entry.getValue();
			if(previousValue != 0 && currentValue != previousValue) break;
		}
		return returnList;
	}

	/**
	 * @Override
	 * @return String
	 * 1手目には必ず"0123..."を、2手目以降は宣言したときに一番残りの手を絞れる可能性の
	 * 高いものを宣言する。
	 */
	public String input() {
		// 1手目には必ず"01234…"を宣言する。
		if (resultLog.isEmpty()) return firstCall;
		// 2手目以降はそれまでの結果から次に宣言する手を決める。
		else{
			// 前回の結果を得て正解の可能性のある文字列のリストを更新する。
			remainCodeForAnswer = renewRemainCode(remainCodeForAnswer, resultLog.pop());
			// 期待値(宣言したときのremainCodeForAnswer.size())が最小になる文字列をすべて集める。
			ArrayList<String> tmp = new ArrayList<>(getMinumumKitaichi(remainCodeForAnswer));
			// 期待値最少かつ正解の可能性のある文字列を格納するためのArrayListを作成
			ArrayList<String> tmp2 = new ArrayList<>();
			for (String s : remainCodeForAnswer){
				// 全ての残り文字列に対して期待値が最小であればtmp2に入れる
				if(tmp.contains(s)) tmp2.add(s);
			}
			// 期待値最少かつ正解の可能性のある文字列が無ければ期待値最少のものを宣言する。
			if(tmp2.isEmpty()) return tmp.get(0);
			else return tmp2.get(0);
		}
	}
}

package play;

import java.util.LinkedList;

/**
 * @author waterlow
 * HitAndBlowゲーム内で数を当てる側の動作を定義するクラス
 */
public abstract class Player {
	/**
	 * 宣言した数字と結果を格納
	 */
	protected static LinkedList<HitBlowResult> resultLog = new LinkedList<>();

	/**
	 * @return String
	 * 文字列を宣言。
	 */
	public abstract String input();
	/**
	 * @param result
	 * 文字列宣言で得たhitやblowの結果を格納する。
	 */
	public void storeResult(HitBlowResult result){
		Player.resultLog.push(result);
	}
}

package play;

import static play.HitBlowResult.*;
import static play.Rules.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

import play.ai.Ai;


public class HitAndBlow {

	// HitAndBlowのインスタンスが生成されるたびランダムに1つ正解の文字列を作る
	private final String ANSWER_OF_THIS_GAME = makeOneRandomCode();
	// judgeGameEndの戻り値を保持する
	private boolean gameIsEnd = false;
	private Ai player = new Ai();

	// HitAndBlowのインスタンスを作りstartGameを呼び出すことで
	// Gameを開始する
	private void startGame(){
		System.out.println(ANSWER_OF_THIS_GAME);
		// hitがCODE_LENGTHに一致するまで無限にゲームを繰り返す
		while(!gameIsEnd){
			this.gameIsEnd = this.startThisTurn();
		}
	}

	// playerにコマンドラインから文字列を入力し
	// answerHitBlowResultで結果を判定
	// judgeGameEndでゲーム終了か否かを返す
	private boolean startThisTurn(){
		String inputOfThisTurn = player.input();
		HitBlowResult hitBlowResultOfThisTurn = answerHitBlowResult(ANSWER_OF_THIS_GAME, inputOfThisTurn);
		System.out.println(hitBlowResultOfThisTurn);
		player.storeResult(hitBlowResultOfThisTurn);
		return judgeGameEnd(hitBlowResultOfThisTurn);
	}

	private static boolean judgeGameEnd(HitBlowResult result){
		boolean gameIsEnd = (result.getHitCount() == CODE_LENGTH);
		return gameIsEnd;
	}

	// CHAR_USED_IN_THIS_GAMEの文字から重複を許さず長さCODE_LENGTHの文字列を作る
	private static String makeOneRandomCode(){
		ArrayList<String> char_used_in_this_game_tmp = new ArrayList<>(Arrays.asList(CHAR_USED_IN_THIS_GAME));
		String str = "";
		for (int ai = 0; ai < CODE_LENGTH; ai++){
			Random random = new Random();
			int choosing = random.nextInt(char_used_in_this_game_tmp.size());
			str += char_used_in_this_game_tmp.get(choosing);
			// 一度選んだ文字は使わない
			char_used_in_this_game_tmp.remove(choosing);
		}
		return str;
	}
}

package play;
public class HitBlowResult{

	private String code;
	private int hitCount;
	private int blowCount;

	public HitBlowResult(String code, int hitCount, int blowCount) {
		this.code = code;
		this.hitCount = hitCount;
		this.blowCount = blowCount;
	}

	public int getHitCount() {
		return hitCount;
	}

	public int getBlowCount() {
		return blowCount;
	}

	public String getCode() {
		return code;
	}

	public static HitBlowResult
	answerHitBlowResult(String code1, String code2){
		int hitCount = 0;
		int blowCount = 0;
		for (int i1 = 0; i1 < Rules.CODE_LENGTH; i1++){
			for (int i2 = 0; i2 < Rules.CODE_LENGTH; i2++){
				if(i1 == i2) {
					if(code1.charAt(i1) == code2.charAt(i2)) hitCount++;
				}else{
					if(code1.charAt(i1) == code2.charAt(i2)) blowCount++;
				}
			}
		}
		HitBlowResult r = new HitBlowResult(code2, hitCount, blowCount);
		return r;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + blowCount;
		result = prime * result + ((code == null) ? 0 : code.hashCode());
		result = prime * result + hitCount;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (getClass() != obj.getClass()) {
			return false;
		}
		HitBlowResult other = (HitBlowResult) obj;
		if (blowCount != other.blowCount) {
			return false;
		}
		if (code == null) {
			if (other.code != null) {
				return false;
			}
		} else if (!code.equals(other.code)) {
			return false;
		}
		if (hitCount != other.hitCount) {
			return false;
		}
		return true;
	}

	@Override
	public String toString() {
		return "(code, hitCount, blowCount) = (" + code + ", " + hitCount + ", " + blowCount + ")";
	}
}