En este post veremos como un algoritmo genético es capaz de ordenar un tablero de ajedrez. Es como si un niño de 2 años pusiera las piezas aleatoriamente en el tablero y el algoritmo se encargara de poner cada una en su sitio.
Crearemos una clase ChessPiece para cada figura de ajedrez y una clase ChessBoard que implementará la interfaz IMutable. Esto quiere decir que nuestro cromosoma es una lista de piezas de ajedrez y que el Fitness es del tipo doble.
Acto seguido, creamos el geneset o conjunto de genes que formarán el cromosoma donde incluiremos también la casilla vacía. Luego le daremos un valor a cada pieza y otro valor a cada casilla, cada vez que se acierte, el fitness se verá incrementado hasta el 100%.
class ChessBoard : IMutable {
override val geneset = mutableListOf(
ChessPiece("T",ChessPieceColor.BLACK,11),
ChessPiece("C",ChessPieceColor.BLACK,13),
ChessPiece("A",ChessPieceColor.BLACK,15),
ChessPiece("D",ChessPieceColor.BLACK,16),
ChessPiece("R",ChessPieceColor.BLACK,18),
ChessPiece("A",ChessPieceColor.BLACK,15),
ChessPiece("C",ChessPieceColor.BLACK,13),
ChessPiece("T",ChessPieceColor.BLACK,11),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("P",ChessPieceColor.BLACK,4),
ChessPiece("T",ChessPieceColor.WHITE,10),
ChessPiece("C",ChessPieceColor.WHITE,12),
ChessPiece("A",ChessPieceColor.WHITE,14),
ChessPiece("D",ChessPieceColor.WHITE,17),
ChessPiece("R",ChessPieceColor.WHITE,19),
ChessPiece("A",ChessPieceColor.WHITE,14),
ChessPiece("C",ChessPieceColor.WHITE,12),
ChessPiece("T",ChessPieceColor.WHITE,10),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5),
ChessPiece("P",ChessPieceColor.WHITE,5))
init {
geneset.addAll((1..32).map { ChessPiece("_",ChessPieceColor.EMPTY,0) })
}
override val target: Double = 64.0
override var bestParent = createParent(0)
override var bestFitness: Double = 0.0
private val values = mutableListOf(11,13,15,16,18,15,13,11,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,5,5,5,5,5,5,5,10,12,14,17,19,14,12,10)
override fun isSuccess(): Boolean = bestFitness == 1.0
var result=""
override fun start() {
bestFitness = getFitness(bestParent)
var childFitness: Double
var child: MutableList
//Display(bestParent, bestFitness)
var attemps=0
do {
do {
child = mutate(bestParent)
childFitness = getFitness(child)
} while (bestFitness > childFitness)
bestFitness = childFitness
bestParent = child
result +=toShortString() + "\n\n\n"
attemps ++
println(toShortString() + "\n")
} while (!isSuccess())
println("Nº de intentos: $attemps")
}
override fun createParent(param: Any): MutableList {
// llena el tablero con las 32 fichas piezas + 32 vacias
return geneset.shuffled().toMutableList()
}
override fun getFitness(obj: MutableList): Double = obj.mapIndexed { index, chessPiece -> if (values[index] == chessPiece.value) 1.0 else 0.0 }.sum() / target
override fun mutate(parent: MutableList): MutableList {
val parentFitness: Double = getFitness(parent)
var childFitness = 0.0
var child = mutableListOf()
do {
child.clear()
child.addAll(parent)
val startIndex = Random.nextInt(bestParent.size)
val endIndex = Random.nextInt(bestParent.size)
val start = parent[startIndex]
val end = parent[endIndex]
child[startIndex] = end
child[endIndex] = start
childFitness = getFitness(child)
}while (childFitness chessPiece.toString() + if ((index+1) % 8 ==0) "\n" else "\t" }
.joinToString("")}\nFitness: $bestFitness"
fun toShortString(): String ="${bestParent
.mapIndexed { index, chessPiece -> (if (chessPiece.value==0) " " else if (chessPiece.value == values[index]) (if (chessPiece.color==ChessPieceColor.WHITE) "○" else "●") else "#")+if ((index+1) % 8 == 0) "\n" else "" }
.joinToString("")
}\nFitness: ${"%.3f".format(bestFitness)}"
fun foo(collection: MutableList){
}
}
fun main(){
val chessBoard = ChessBoard()
chessBoard.start()
println(chessBoard.bestParent)
}
Y este es el resultado del progreso de los cromosomas para 36 intentos
TN CN AN DN RN AN CN TN
PN PN PN PN PN PN PN PN
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
PB PB PB PB PB PB PB PB
TB CB AB DB RB AB CB TB
Fitness: 1.0
Y ahora implementaremos la interfaz con mi mejor amigo, C#
public class ChessPiece
{
public ChessPiece(string name, Colors color, int value)
{
Name = name;
ChessPieceColor = color;
Value = value;
}
public string Name { get; set; }
public int Value { get; set; }
public Colors ChessPieceColor { get; set; }
public enum Colors
{
Black,
White,
Empty
}
public string ColorToString => ValueToString(ChessPieceColor);
public new string ToString => $"{Name}{ColorToString}";
private string ValueToString(Colors color)
{
switch (color)
{
case Colors.Black:
return "N";
case Colors.White:
return "B";
case Colors.Empty:
return "_";
default:
return "";
}
}
}
public class ChessBoard : IMutable
{
public ChessBoard()
{
Geneset = new List()
{
new ChessPiece("T", ChessPiece.Colors.Black, 11),
new ChessPiece("C", ChessPiece.Colors.Black, 13),
new ChessPiece("A", ChessPiece.Colors.Black, 15),
new ChessPiece("D", ChessPiece.Colors.Black, 16),
new ChessPiece("R", ChessPiece.Colors.Black, 18),
new ChessPiece("A", ChessPiece.Colors.Black, 15),
new ChessPiece("C", ChessPiece.Colors.Black, 13),
new ChessPiece("T", ChessPiece.Colors.Black, 11),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("P", ChessPiece.Colors.Black, 4),
new ChessPiece("T", ChessPiece.Colors.White, 10),
new ChessPiece("C", ChessPiece.Colors.White, 12),
new ChessPiece("A", ChessPiece.Colors.White, 14),
new ChessPiece("D", ChessPiece.Colors.White, 17),
new ChessPiece("R", ChessPiece.Colors.White, 19),
new ChessPiece("A", ChessPiece.Colors.White, 14),
new ChessPiece("C", ChessPiece.Colors.White, 12),
new ChessPiece("T", ChessPiece.Colors.White, 10),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5),
new ChessPiece("P", ChessPiece.Colors.White, 5)
};
Geneset.AddRange(Enumerable.Range(0, 32).ToList().Select(k => new ChessPiece("_", ChessPiece.Colors.Empty, 0)));
}
public List Geneset { get; set; }
public double Target { get; set; } = 64;
public List BestParent { get; set; }
public double BestFitness { get; set; }
private Random rnd = new Random();
private IList Values = new List() { 11, 13, 15, 16, 18, 15, 13, 11, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 10, 12, 14, 17, 19, 14, 12, 10 };
private string result = "";
public List CreateParent(object param) => Suffled(Geneset);
public double GetFitness(List obj) => obj
.Select((item, index) => new { Item = item, Index = index })
.Select(k => k.Item.Value == Values[k.Index] ? 1.0 : 0.0)
.Sum()/Target;
public bool IsSuccess() => BestFitness == 1.0;
public List Mutate(List parent)
{
var parentFitness = GetFitness(parent);
var childFitness = 0.0;
var child = new List();
do
{
child.Clear();
child.AddRange(parent);
var startIndex = rnd.Next(BestParent.Count());
var endIndex = rnd.Next(BestParent.Count());
var start = parent[startIndex];
var end = parent[endIndex];
child.RemoveAt(startIndex);
child.Insert(startIndex, end);
child.RemoveAt(endIndex);
child.Insert(endIndex, start);
childFitness = GetFitness(child);
//print(child);
} while (childFitness k.Value)));
}
public void Start()
{
BestParent = CreateParent(null);
BestFitness = GetFitness(BestParent);
var childFitness = 0.0;
var child = new List();
var attemps = 0;
do
{
do
{
child = Mutate(BestParent);
childFitness = GetFitness(child);
} while (BestFitness > childFitness);
BestFitness = childFitness;
BestParent = child;
result += ToShortString + "\n\n\n";
Console.WriteLine(result);
attemps++;
} while (!IsSuccess());
Console.WriteLine(ToShortString + "\n");
Console.WriteLine($"Nº intentos: {attemps}");
}
private List Suffled(List source) => source
.Select(x => new { value = x, order = rnd.Next() })
.OrderBy(x => x.order).Select(x => x.value).ToList();
public new string ToString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => k.Item.ToString + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";
public string ToShortString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => (k.Item.Value == 0 ? " " : (k.Item.Value == Values[k.Index]) ? (k.Item.ChessPieceColor == ChessPiece.Colors.White ? "O" : "■") : "#") + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";
}
class Program
{
static void Main(string[] args)
{
var chessboard = new ChessBoard();
chessboard.Start();
Console.WriteLine(chessboard.ToString);
Console.WriteLine("Press any key...");
Console.ReadKey();
}
}
Si quieres leer mi anterior post sobre la interface de algoritmos genéticos, aquí lo tienes.
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
wakicode 