Implementasi Metode Simple Hill Climbing Pada Game Sederhana Puzzle 8 Blok

Game Puzzle 8 Blok adalah permainan sederhana yang terdiri dari susunan 9 buah kotak/persegi yang mana 8 kotak diantaranya berisikan angka dari 1 hingga 8, 1 kotak sisanya kosong. Kotak kosong ini digunakan untuk memindahkan 8 kotak atau blok-blok hingga mencapai urutan angka yang diinginkan. Mungkin untuk lebih jelasnya silahkan lihat gambar dibawah ini, gambar berikut ini adalah visualisasi permainan tersebut :

Ya seperti itulah, jadi teringat permainan itu di masa lalu ya?? 🙂 Saat ini saya akan coba membuatnya dalam sebuah permainan komputer sederhana, kenapa sederhana, karena untuk bagian pertama ini saya ingin share dulu game versi text nya, atau versi DOS (Command Prompt). Untuk versi GUI nya akan menyusul di posting selanjutnya :).

Disini agar proses pencarian solusi optimal, saya menggunakan algoritma Simple Hill Climbing yang didukung dengan metode Manhattan Distance untuk mengetahui jumlah atau jarak paling minimum dari persoalan menuju posisi blok yang diinginkan. Untuk lebih jelasnya mengenai Manhattan Distance atau Simple Hill Climbing bisa dicari lebih lanjut di website lainnya :mrgreen:. Untuk hasil contoh jalannya program ini adalah sebagai berikut :

Yap, kira – kira seperti itu, dengan posisi awal dimana urutan angkanya tidak berurutan dan tujuan akhirnya adalah diharapkan angka berurutan menjadi 1,2,3,4,5,6,7 dan 8. Disana terdapat angka 0, itu dimaksudkan atau diibaratkan blok atau kotak yang kosong tadi. Oke, untuk source codenya, bisa dilihat dibawah ini :

public class Puzzle {
	public static int initialState[] = { 1, 2, 3, 4, 8, 0, 7, 6, 5 };
	public static int goalState[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
	public static int resetValue = 0;
	public static int tempHeuristic[] = { resetValue, resetValue, resetValue, resetValue };
	public static int totalSolution = 0;

	private static int checkIndex(int state[]){
		int index = 0;
		for (int i = 0; i < 9; i++) {
	        if (state[i] == 0) {
	            index = i;
	        }
	    }
		return index;
	}

	public static void moveLeft(int state[]) {
		int index0 = checkIndex(state);
		if (index0 % 3 > 0) {
			int temp = state[index0];
			state[index0] = state[index0-1];
			state[index0-1] = temp;
		}
	}

	public static void moveRight(int state[]) {
		int index0 = checkIndex(state);
		if (index0 % 3 < 2) {
			int temp = state[index0];
			state[index0] = state[index0+1];
			state[index0+1] = temp;
		}
	}

	public static void moveUp(int state[]) {
		int index0 = checkIndex(state);
		if (index0 > 2) {
			int temp = state[index0];
			state[index0] = state[index0-3];
			state[index0-3] = temp;
		}
	}

	public static void moveDown(int state[]) {
		int index0 = checkIndex(state);
		if (index0 < 6) {
			int temp = state[index0];
			state[index0] = state[index0+3];
			state[index0+3] = temp;
		}
	}

	public static int hasSameElement(int array1[], int array2[]) {
		int temp = 1;
		for (int i = 0; i < 9; i++) {
			if (array1[i] != array2[i]) {
				temp = 0;
			}
		}
		return temp;
	}

	public static int sideHeuristic(int side, int currentState[], int goalState[]) {
		int temp = 0;
		int match = 0;
		switch (side) {
			case 1:
				match = 0;
				for (int i = 0; i < 2; i++) {
					if (currentState[i] == goalState[i] && currentState[i] != 0) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 40;
				}
			break;
			case 2:
				match = 0;
				for (int i = 2; i < 9; i=i+3) {
					if (currentState[i] == goalState[i] && currentState[i] != 0) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 40;
				}
			break;
			case 3:
				match = 0;
				for (int i = 6; i < 9; i++) {
					if (currentState[i] == goalState[i] && currentState[i] != 0) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 40;
				}
			break;
			case 4:
				match = 0;
				for (int i = 0; i < 7; i=i+3) {
					if (currentState[i] == goalState[i] && currentState[i] != 0) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 40;
				}
			break;
			case 5:
				match = 0;
				for (int i = 1; i < 8; i=i+3) {
					if (currentState[i] == goalState[i]) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 5;
				}
			break;
			case 6:
				match = 0;
				for (int i = 3; i < 6; i++) {
					if (currentState[i] == goalState[i]) {
						match++;
					}
				}
				if (match == 1) {
					temp = temp + 1;
				} else if (match == 2) {
					temp = temp + 5;
				} else if (match == 3) {
					temp = temp + 5;
				}
			break;
		}
		return temp;
	}

	public static int getCol(int val) {
		return ((val/3)+1);
	}

	public static int getRow(int val) {
	    return ((val%3)+1);
	}

	public static int stepCounter(int condition1, int condition2) {
		int temp1 = getCol(condition1)-getCol(condition2);
		if (temp1 < 0) {
			temp1 = (temp1 * -1) * 2;
		}
		int temp2 = getRow(condition1)-getRow(condition2);
		if (temp2 < 0) {
			temp2 = (temp2 * -1) * 2;
		}
	    return (((temp1 + temp2) * -1) + 4);
	}

	public static int manhattanHeuristic(int currentState[], int goalState[]) {
	    int temp = 0;
	    for (int i = 0; i < 9; i++) {
	        for (int j = 0; j < 9; j++) {
	            if (currentState[i] != 0) {
	                if (currentState[i] == goalState[j]) {
	                    temp = temp + stepCounter(i, j);
	                }
	            }
	        }
	    }
	    return temp;
	}

	public static int heuristicValue(int currentState[], int goalState[]) {
		return sideHeuristic(1, currentState, goalState) +
			sideHeuristic(2, currentState, goalState) + sideHeuristic(3, currentState, goalState) +
			sideHeuristic(4, currentState, goalState) + sideHeuristic(5, currentState, goalState) +
			sideHeuristic(6, currentState, goalState) + manhattanHeuristic(currentState, goalState);
	}

	public static void copyArray(int array1[], int array2[]) {
		for (int i = 0; i < 9; i++) {
			array2[i] = array1[i];
		}
	}

	public static int getTheBestIndex(int arrayHeuristic[]) {
		int temp = 0;
		int tempValue = arrayHeuristic[0];
		for (int i = 0; i < 4; i++) {
			if (arrayHeuristic[i] > tempValue) {
				tempValue = arrayHeuristic[i];
				temp = i;
			}
		}
		return temp;
	}

	public static void printState(int state[]) {
	    for (int i = 0; i < 9; i++) {
			if (i % 3 == 0) {
				System.out.print("\n");
			}
	        System.out.print(state[i]);
			System.out.print(" ");
	    }
		System.out.print("\n");
	}

	public static void main(String[] args) {
		int currentState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
		copyArray(initialState, currentState);
		int childState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
		while (hasSameElement(currentState, goalState) == 0) {
			printState(currentState);
			copyArray(currentState, childState);
			moveUp(childState);
			if (hasSameElement(childState, currentState) == 1) {
				tempHeuristic[0] = 0;
			} else {
				tempHeuristic[0] = heuristicValue(childState, goalState);
				moveDown(childState);
			}
			moveLeft(childState);
			if (hasSameElement(childState, currentState) == 1) {
				tempHeuristic[1] = 0;
			} else {
				tempHeuristic[1] = heuristicValue(childState, goalState);
				moveRight(childState);
			}
			moveRight(childState);
			if (hasSameElement(childState, currentState) == 1) {
				tempHeuristic[2] = 0;
			} else {
				tempHeuristic[2] = heuristicValue(childState, goalState);
				moveLeft(childState);
			}
			moveDown(childState);
			if (hasSameElement(childState, currentState) == 1) {
				tempHeuristic[3] = 0;
			} else {
				tempHeuristic[3] = heuristicValue(childState, goalState);
				moveUp(childState);
			}
			int tempIndex = getTheBestIndex(tempHeuristic);
			switch (tempIndex) {
				case 0:
					moveUp(currentState);
				break;
				case 1:
					moveLeft(currentState);
				break;
				case 2:
					moveRight(currentState);
				break;
				case 3:
					moveDown(currentState);
				break;
			}
			totalSolution++;
		}
		printState(currentState);
		System.out.print("\nSolusi Total = " + totalSolution + " langkah");
	}
}

Oh ya, hampir lupa… program ini saya buat menggunakan bahasa pemrograman Java. Terserah jika ingin pakai Netbeans, Eclipse atau jCreator untuk IDE-nya. Oke sekian, semoga bisa bermanfaat 🙂