Hi.
First I apologies for any mistake i could make as i’m not fluent in english.
I found myself kinda stuck as my A.I. get itself looping a while after beginning acting good.
But before i’ll explain my project so you can fully understand the issue.
I started few weeks ago a personal project that I though 2 year ago. In the same time I choose to do it with Unity that i didn’t know before.
The project is to remake a game i used to play in my childhood on my father’s Atari ST : HEX
So i created a board of a given size*size of Hexagon prefab stocked in an array.
This give me a rectangular board of hexagon.
Then i create function to test if on “square” is inside or outside an Hexagonal board to match the one presented in the original game. I make the outsider “square” transparent.
This give me an hexagonal board of hexagon.
Then i created 2+ pawns from a prefab. One for the player one for the enemy(ies).
Then i created several algorithm to make the gameplay underneath working :
To be brief :
- each hexagon which share color and “frontier” form what i called a “region”.
- each hexagon can be pushed as being moved into.
- When a pawn move to a valid hexagon he push this hexagon
- if all hexagon of a given region are pushed then depush all those and switch the color of the region to the next one. Finally recompute the regions on the board as the board has change.
- each pawn can move to his neighbors square and on its current hexagon (it can stay where it is) excpet on those given neighbor square if they are currently occupied by another pawn.
- each hexagon have 6 neighbors as it has 6 “frontiers”
- the hexagon switch color from green->blue->violet->red->green and so on.
- the goal for the player is to convert all hexagon to green, and for the enemy(ies) to red.
- all hexagon have a value given their color and pushed state
- the board have a value as the sum of all his hexagons value
So i made all this working as i play alone without enemy driven by A.I. using the mouve to clic on hexagon on the board and moving my pawn around as
Now i go for implementing my A.I.
To begin with i chose a deep search approach (if I’m correct not sure on the IT vocabulary here).
The idea is to recursively move my enemy pawn from pawn starting location to neighbor hexagon and so on as i go further in recursivity. :
I first save the board (the color and pushed state of each hexagon, the pawn location)
Then I move the enemy pawn to each valid possible hexagon the pawn can go (all neighbor hexagon + own location - occupied neighbor hexagon).
I store the maximum board value in a referenced (ref) int variable corresponding to the current maximum board value maxBoardValue.
I use another int variable to store the last maximum board lastMaxBoardValue value as i want to test it against the maxBoardValue. This is not a referenced variable so it serve only on a given recursive level to test the deep recursive call of the function have found a greater maxBoardValue than lastMaxBoardValue .
Each time i move my enemy pawn I test if the new board value is greater than the maxBoardValue.
If so I update the maxBoardValue to the new maximum (the current board value).
After ward I test if the maxBoardValue greater than lastMaxBoardValue.
If so then the current hexagon I moved my enemy pawn into lead to a greater board value, so i store this hexagon to the one to be returned by my function.
After moving and testing and before do it again on the next valid move possible I restore the board save i made prior all this.
So to be brief :
- enemy pawn is on a given board location
- I move the pawn on all given possible move he can made
- each time i move the pawn i calculate the board value
- if the board value is greater than all the previous one then i chose this move
- and to go deep I do it recursively again on each new pawn location until a given “deepness” of search have been reach.
This give me the next hexagon my enemy pawn will move into.
here is the code :
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class IADeepSearch : IAInterface {
// la profondeur de la recherche
public int m_deep;
public IADeepSearch(int d, GameObject pawn) : base(pawn)
{
m_deep = d;
}
public override GameObject NextMove()
{
GameManager.reflectChange = false;
int mBValue = int.MinValue;
GameObject nextHex = RecursiveSearch(1, ref mBValue);
GameManager.reflectChange = true;
return nextHex;
}
GameObject RecursiveSearch(int currentDeep, ref int maxBoardValue)
{
/*
* PROBLEME LORSQUE UN CHEMIN VERS UN PLUS GRAND MAXBOARDVALUE ALTERNE ENTRE 2 HEXGONE VOISIN
* L IA PEUT BOUCLER INDEFINIMENT SUR CES 2 POSITIONS VOISINES QUI SONT LES 2 DEPARTS POSSIBLE
* ON BOUCLE QUAND UN CHEMIN FINIT SUR LA MÊME VALEUR DE PLATEAU QU'UN AUTRE CHEMIN QUI DEMARRE
* SUR UNE CASE VOISINE.
*/
SaveState savedBoard = m_pawn.GetComponent<Pawn>().board.Save();
List<GameObject> validHex = m_pawn.GetComponent<Pawn>().board.ValidHex(m_pawn);
Pawn scriptPawn = m_pawn.GetComponent<Pawn>();
// Si la case ou se situe actuellement le pion (ainsi que sa dernière position) sont déjà "poussées" on l'enlève des cases possible
// pour éviter de rester coincé sur la case.
//if (scriptPawn.board.m_board[scriptPawn.positionx, scriptPawn.positiony].GetComponent<Case>().isPushed)
//validHex.Remove(scriptPawn.board.m_board[scriptPawn.positionx, scriptPawn.positiony]);
//if (scriptPawn.board.m_board[scriptPawn.lastPositionx, scriptPawn.lastPositiony].GetComponent<Case>().isPushed)
//validHex.Remove(scriptPawn.board.m_board[scriptPawn.lastPositionx, scriptPawn.lastPositiony]);
// la case ou se situe actuellement le pion
GameObject hexToMoveIn = m_pawn.GetComponent<Pawn>().board.m_board[m_pawn.GetComponent<Pawn>().positionx, m_pawn.GetComponent<Pawn>().positiony];
int lastMaxBoardValue = maxBoardValue;
foreach (GameObject go in validHex)
{
go.GetComponent<Case>().Click(m_pawn);
if (m_pawn.GetComponent<Pawn>().board.BoardValue() > maxBoardValue)
{
lastMaxBoardValue = maxBoardValue;
maxBoardValue = m_pawn.GetComponent<Pawn>().board.BoardValue();
}
if (currentDeep < m_deep)
RecursiveSearch(currentDeep + 1, ref maxBoardValue);
if (maxBoardValue > lastMaxBoardValue)
{
lastMaxBoardValue = maxBoardValue;
hexToMoveIn = go;
}
m_pawn.GetComponent<Pawn>().board.Load(savedBoard);
}
m_pawn.GetComponent<Pawn>().board.Load(savedBoard);
return hexToMoveIn;
}
}
Now the ISSUE :
As a result my enemy pawn move around and choose well to push hexagon in order to make the board full red.
BUT at a given point my A.I. start looping between 2 neighbor location.
What i GUESS and it is only a guess I’m not sure is that for a given deepness of search A.I. found a path to go to a greater maxBoardValue so he move into the next hexagon along this path. but THEN the A.I. found another path an equal (or superior?) maxBoardValue backward. So he move back… and THEN The A.I. found the first path again and so on …
Here is a screenshot of my board when the A.I. is looping :
I have set my deepness to 3.
Here are my arbitrary value of my hexes depending on their color and pushed status :
public static int[] hexValue = {/*green*/0,
/*green pushed*/ 2,
/*blue*/ 3,
/*blue pushed*/ 4,
/*violet*/ 5,
/*violet pushed*/ 6,
/*red*/ 7,
/*red pushed*/ 7,
/*transparent*/ 0,
/*transparent pushed*/ 0};
Here is the order of my List of neighbor hex :
And the resulting order of my List of valid hex to move in :
The gray circle represent the Enemy pawn driven by A.I., and the yellow one the player pawn.
