Ayuda para juego de Ajedrez

[urkel]

Hola,

Estoy en un apuro del que no parece que pueda salir, tengo que implementar un algoritmo de Ajedrez y estoy totalmente encallado en una parte muy especifica. Necesitaria que alguien que se haya enfrentado antes al desarrollo de un juego de Ajedrez pudiera ayudarme. En principio, soy una persona, no una empresa, por lo que mis recursos son muy limitados, pero si encuentro a alguien con experiencia que me pueda ayudar realmente en mi problema no tengo problema en hablar de temas economicos por la ayuda.

Para contactar podeis usar: esteban@freecreationgames.net

Un Saludo.

[julen26]

Deberías leer un poco sobre el algoritmo minimax que no es muy dificil implementar, y aplicar algoritmos para reducir el número de comprobaciones (nodos) como alfa-beta. Además, dado el tamaño de nodos que tiende a generar una partida de ajedrez, se suele limitar la profundidad del árbol tambien.

[bnl]

No se exactamente que quieres hacer.
Si estas desarrollando un juego de ajedrez yo utilizaria un motor de Ajedrez. Hay bastantes y te facilitaria mucho la vida. Es complicado desarrollar un buen motor
Si lo necesitas para unas practicas o similar y tienes que desarrollar el algoritmo puedes echarle un vistazo al minimax que te comenta julen26 o a otros algoritmos-

[urkel]

Tengo implementado varios algoritmos, especificamente he eligido el AlphaBeta. Trabajo en C# para Unity3D.

Código [Seleccionar] Expand


private int AlphaBeta(ChessBoardState board, int alpha, int beta, int depth)
{
MovePiece smove;
int bestscore = -1000000000;
int score;
String info;

// REACH MAX DEPTH
if (depth >= MAX_DEPTH)
{
return Quiesce(board,alpha,beta);
}

// GENERATE
List<MovePiece> movements = board.GenerateAllPossibleMoves();
for (int i = 0; i < movements.Count; i++)
{
// CREATE A NEW STATE
smove = movements[i];
ChessBoardState newBoard = new ChessBoardState(m_initialBoard.FamilyInitial);
newBoard.Init(ChessPiece.GetOppositeFamily(board.FamilyTurn),board.Matrix,board.Totalmoves+1,board.PackageMoves(smove));
newBoard.MoveFromTo(smove.x_origin, smove.y_origin, smove.x_goal, smove.y_goal, 0);

// EVALUATE THE NEW STATE
score = -AlphaBeta(newBoard, -beta, -alpha, depth + 1);

// CUT OR CONTINUE
if (score >= beta)
{
return score; // fail-soft beta-cutoff
}
if (score > bestscore)
{
bestscore = score;
if (score > alpha)
{
alpha = score;
PushNewBestMove(newBoard, score(NO FUNCIONA PARA NADA));
}
}
}
return bestscore;
}


En principio, el algoritmo funciona, digo en principio, porque por lo que entiendo este algoritmo tan solo realiza el proceso de cortar ramas, no  de buscar la mejor solucion. http://chessprogramming.wikispaces.com/Best+Move

Por lo que trato de desencriptar de toda la exceso de información sobre el tema, se supone que cada vez que se supera alpha es que tenemos una posible buen movimiento. Mi problema radica en que entre el conjunto de soluciones encontradas no se como evaluarlas para determinar cual es la mejor posible solucion, no, no me funciona tomar el valor de "alpha" como factor para considerar su valia.

No acudo gratuitamente aquí por pereza, llevo varios dias perdiendo el tiempo tratando de buscar una solucion que se me resiste y francamente no estoy de humor para desperdiciar mi tiempo libre quedandome encallado en algo que otra persona me podria ayudar a solucionar en 5 minutos.

Si alguien me ayuda a sacar esto adelante estoy dispuesto a remunerarlo y a compartir el codigo fuente del proyecto, para que nadie tenga que perder el tiempo estupidamente tratando de descifrar un cojon de información bastante confusa.

[blau]

Que yo recuerde en el alfa-beta el quid de la cuestion es que debes de generar un valor heuristico para cada jugada... por ejemplo ...

comer una reina puede suponer 100 puntos para el jugador max si se se la come a min y  -100 puntos si es min quien se la come a Max.. (que mal suena esto....  ^_^')
o que en una disposicion del tablero max amenaza  a fichas mas importantes..  por ejemplo que un peon amenace a un reina podira representar 15 puntos...

pero claro al principio del juego no hay muchas jugadas que puedan considerarse mejores... por lo que creo que se suelen tener bases de datos con aperturas para empezar jugando de "memoria"...


no se si es eso lo que necesitas... pero espero que sirva de algo... :)

[Vicente]

Una buena heurística para el ajedrez es muy difícil de calcular. Yo empezaría con alguna cosa sencilla, por ejemplo contar las piezas de cada bando (con el valor habitual del ajedréz: peón 1, alfil 3, etc). Luego además puedes sumarle cosas como las amenazas de blau, jaques, etc.

Pero vamos, que es una movida que no veas el problema :D Nadie lo va a resolver en cinco minutos, ni vas a encontrar nada que puedas copiar y pegar creo yo. Pero seguro que hay un montón de papers al respecto que te pueden orientar un poco.

Un saludo!

Vicente

[blau]

La verdad es que san google está repletito de ayuda...

https://www.google.es/search?q=chess+engine+c%23&aq=f&oq=chess+engine+c%23

sobre todo este... ttp://www.codeproject.com/Articles/36112/Chess-Program-in-C

y por supuesto stackoverflow... http://stackoverflow.com/questions/759664/anyone-know-of-a-good-net-chess-engine

[urkel]

Gracias por los comentarios.

Tengo todo implementado, mecanismo de busqueda, mecanismo de evaluacion, incluso el "consejo" de selección del mejor movimiento. Lo tengo casí todo, pero no consigo encontrar la unica pieza que me falta, y si, es un asunto que alguien con experiencia en este tema podria ayudarme en 5 minutos. Pero supongo que encontrar un programador que se haya enfrentado a esto me va a ser imposible. En fin, seguire golpeandome la cabeza contra el muro a ver quien resiste mas. Jode mucho tener que perder el tiempo así cuando tienes millones de cosas acumulandose :(

[julen26]

En principio, el algoritmo funciona, digo en principio, porque por lo que entiendo este algoritmo tan solo realiza el proceso de cortar ramas, no  de buscar la mejor solucion. http://chessprogramming.wikispaces.com/Best+Move

Si tienes ese algoritmo implementado y funcionando no necesitas más que calcular un heuristico en cada jugada como ya te han dicho. El algoritmo alpha-beta realiza el corte de ramas al mismo tiempo que busca la mejor solución.

Quizá sea cortito, pero sigo sin entender qué es realmente lo que te falta.

comer una reina puede suponer 100 puntos para el jugador max si se se la come a min y  -100 puntos si es min quien se la come a Max.. (que mal suena esto....  ^_^')

8o