You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 

436 lines
15 KiB

#include <stdlib.h>
#include <stdio.h>
#include "arbitre.h"
#define STACK_TYPE size_t
#include "stack.h"
/* recherche dichotomique */
enum bool search(const size_t *tab, const size_t length, const size_t value) {
ssize_t first, last, middle;
first = 0;
last = length-1;
while(first <= last) {
middle = (last+first)/2;
if(tab[middle] == value)
return true;
if(tab[middle] < value)
first = middle+1;
else
last = middle-1;
}
return false;
}
/* pour associer une branche de l'étoile à un joueur */
enum hole_t star_branch(const unsigned int nb_player, const size_t index) {
return ((nb_player==4)?index+(index>=2?1:0):(6/nb_player)*index)+1;
}
/* trouver l'indice d'une case voisine */
ssize_t move_calculation(const size_t index, const enum direction_t move) {
size_t index_lines[] = {0, 1, 3, 6, 10, 23, 35, 46, 56, 65, 75, 86, 98, 111, 115, 118, 120};
size_t index_lines_block[] = {0, 10, 65, 111};
ssize_t line, offset, block;
if(/* index < 0 || */ index > 120)
return -1;
line = 0, block = 0;
while( line < 18 && index_lines[line++] <= index );
while( block < 5 && index_lines_block[block++] <= index );
line -= 2;
block -= 2;
offset = index - index_lines[line];
switch(move) {
case left:
return offset==0?-1:((ssize_t)index)-1;
case right:
return index+1==index_lines[line+1]?-1:((ssize_t)index)+1;
case up_left:
if(line==0 || ( block%2==0 && offset==0 ) || ( line == 4 && ( offset < 5 || offset > 8 ) ) )
return -1;
else
return index_lines[line-1]+offset+((block%2)-1)+(line==4?-5:0)+(line==13?4:0);
case up_right:
if(line==0 || ( block%2==0 && index+1 == index_lines[line+1]) || ( line == 4 && ( offset < 4 || offset > 7) ) )
return -1;
else
return index_lines[line-1]+offset+(block%2)+(line==4?-5:0)+(line==13?4:0);
case down_left:
if(line == 16 || (line != 8 && block%2==1 && offset==0) || (line == 12 && ( offset < 5 || offset > 8 ) ) )
return -1;
else
return index_lines[line+1]+offset-(block%2)+(line==3?4:0)+(line==8?1:0)+(line==12?-5:0);
case down_right:
if(line == 16 || (block%2==1 && index+1 == index_lines[line+1] && index != 64) || (line == 12 && ( offset < 4 || offset > 7 ) ) )
return -1;
else
return index_lines[line+1]+offset-((block%2)-1)+(line==3?4:0)+(line==8?1:0)+(line==12?-5:0);
default:
return index;
break;
}
}
/* nombre de mouvements possibles */
int nb_possible_move(const struct game_state_t game, const struct player_t player) {
int res, i,j,k;
ssize_t dest, dest2;
res = 0; i = 0; j = 0;
do {
if(game.board[i] == player.branch) {
j++;
/* on regarde si on peut faire un déplacement */
k = 0;
do {
if( (dest = move_calculation( (size_t) i, k)) != -1 ) {
if(game.board[dest] == none)
res++;
else
if(((dest2 = move_calculation(dest,k)) != -1) && (game.board[dest2] == none))
res++;
}
} while(++k < 6);
}
} while(++i < 121 && j < 10);
#ifdef debug
fprintf(stderr, "%d cases voisines atteignables pour le joueurs\n", res);
#endif
return res;
}
/* vérifie si la case à l'index est sur la branche d'un autre joueur */
enum bool pawn_on_branch(const enum hole_t player_branch, const size_t index, const size_t start_position[6][10]) {
size_t j;
/* ne pas faire les branches de départ et d'arrivée */
for(j = (((player_branch-1)%3)+1)%6; j!=((player_branch-1)%3) ; j=(j+(j==((player_branch-1)%3)+2?2:1))%6 )
if(search(start_position[j],10,index)) {
#ifdef debug
fputs("arret sur la branche d'un autre joueur\n", stderr);
#endif
return true;
}
return false;
}
#if (allow_to_block_opposite_player == 0)
/* calcule la distance jusqu'à une branche */
int distance_to_branch(const enum hole_t branch, const size_t index) {
const size_t index_lines[] = {0, 1, 3, 6, 10, 23, 35, 46, 56, 65, 75, 86, 98, 111, 115, 118, 120};
const size_t coord_branch[6][2] = {{0, 6}, {4, 12}, {12, 12}, {16, 0}, {12, 0}, {4, 6}};
const size_t offset_add[9] = {6, 5, 5, 4, 0, 0, 1, 1, 2};
size_t line, offset;
int res;
if(/* index < 0 || */ index > 120 || branch < 1 || branch > 6)
return -1;
line = 0;
while( line < 18 && index_lines[line++] <= index );
line -= 2;
offset = index - index_lines[line] + (line>8?offset_add[16-line]:offset_add[line]);
res = 0;
if(offset < coord_branch[branch-1][1])
res += (coord_branch[branch-1][1]-offset);
else
res += (offset-coord_branch[branch-1][1]);
if(line < coord_branch[branch-1][0])
res += (coord_branch[branch-1][0]-line);
else
res += (line-coord_branch[branch-1][0]);
return res;
}
/* vérifie si le joueur doit quitter sa branche car il gène le joueur d'en face */
enum bool must_move(const struct player_t player, const struct game_state_t game, const size_t start_position[6][10], size_t *res) {
ssize_t dest, dest2;
int distance, distance1;
size_t i, j, start_hole, player_pawn, hole;
enum bool tried[121], pawn_to_move[121];
struct stack_cell_t *stack;
enum bool must_move, no_pawn_in_start_zone;
for(i=0 ; i<121 ; pawn_to_move[i++]=false);
for(i=0 ; i<10 ; res[i++]=121);
must_move = true;
stack = NULL;
/* on vérifie que le joueur a au moins un pion dans sa zone de départ */
no_pawn_in_start_zone = true;
for(hole=0; hole < 10 && no_pawn_in_start_zone ; hole++)
if(game.board[start_position[player.branch-1][hole]] == player.branch)
no_pawn_in_start_zone = false;
if(no_pawn_in_start_zone) {
#ifdef debug
fputs("pas de pion dans la zone de départ\n", stderr);
#endif
return false;
}
/* on regarde sur le plateau les pions du joueur d'en face */
hole = 0;
player_pawn = 0;
do {
if(game.board[hole] == ((player.branch+2)%6)+1) {
player_pawn++;
distance = distance_to_branch(player.branch, hole);
for(i=0 ; i<121 ; tried[i++]=false);
/* on regarde là ou on peut aller en un mouvement */
j=0;
do {
if( (dest = move_calculation( (size_t) hole, j)) != -1) {
distance1 = distance_to_branch(player.branch, dest);
if(game.board[dest] == none && distance1 < distance && !pawn_on_branch(((player.branch+2)%6)+1,dest,start_position)) {
printf("coup qui progresse : %lu (%d) %lu (%d)\n", (long unsigned int)hole, distance, (long unsigned int)dest, distance1);
must_move = false; /* on a un coup qui progresse */
}
if(game.board[dest] == player.branch && search(start_position[player.branch-1],10,dest) && distance1 < distance) {
pawn_to_move[dest] = true; /* on aurait un coup qui progresse si on déplace le pion sur dest */
}
if(game.board[dest] != none) {
if((dest2 = move_calculation(dest,j)) != -1) {
distance1 = distance_to_branch(player.branch, dest2);
if(game.board[dest2] == none && distance1 < distance && !pawn_on_branch(((player.branch+2)%6)+1,dest2,start_position)) {
printf("coup qui progresse : %lu (%d) %lu (%d)\n", (long unsigned int)hole, distance, (long unsigned int)dest2, distance1);
must_move = false; /* on a un coup qui progresse */
}
else if(game.board[dest2] == player.branch && search(start_position[player.branch-1],10,dest2) && distance1 < distance)
pawn_to_move[dest] = true; /* on aurait un coup qui progresse si on déplace le pion sur dest2 */
if(game.board[dest2] == none)
stack_push(&stack, (size_t) dest2);
}
}
}
} while(++j < 6 && must_move);
tried[hole] = true;
/* pour tous les sauts, peut on en faire d'autres ? */
while(stack && must_move) {
start_hole = *(stack_pop(&stack));
if(!tried[start_hole]) {
j = 0;
do {
if( (dest = move_calculation(start_hole, j)) != -1 && game.board[dest] != none && (dest2 = move_calculation(dest,j)) != -1) {
distance1 = distance_to_branch(player.branch, dest2);
if(game.board[dest2] == none && distance1 < distance && !pawn_on_branch(((player.branch+2)%6)+1,dest2,start_position)) {
printf("coup qui progresse : %lu (%d) %lu (%d)\n", (long unsigned int)hole, distance, (long unsigned int)dest2, distance1);
must_move = false; /* on a un coup qui progresse */
}
else if(game.board[dest2] == player.branch && search(start_position[player.branch-1],10,dest2) && distance1 < distance)
pawn_to_move[dest] = true; /* on aurait un coup qui progresse si on déplace le pion sur dest2 */
if(game.board[dest2] == none)
stack_push(&stack, (size_t) dest2);
}
} while(++j < 6 && must_move);
tried[start_hole] = true;
}
}
/* on vide la pile */
if(!must_move) {
while(stack)
stack_pop(&stack);
}
}
}while(++hole < 121 && player_pawn < 10 && must_move);
/* s'il n'y a pas de joueur en face */
if(player_pawn < 10)
return false;
if(must_move) {
/* aucun coup qui progresse donc on doit sortir de sa branche */
#ifdef debug
fputs("le joueur peut déplacer les pions ", stderr);
#endif
for(hole=0, player_pawn=0;hole<121 && player_pawn < 10;hole++)
if(pawn_to_move[hole]) {
#ifdef debug
fprintf(stderr, "%lu ", (long unsigned int)hole);
#endif
res[player_pawn++]=hole; /* le tableau est trié donc on pourra faire une recherche dichotomique */
}
#ifdef debug
fputs("\n",stderr);
#endif
}
/* si aucun coup ne bloque */
if(player_pawn == 0) {
#ifdef debug
fputs("n'importe quel coup est autorisé\n", stderr);
#endif
return false;
}
#ifdef debug
else
fputs("n'importe quel coup est autorisé\n", stderr);
#endif
return must_move;
}
#endif
/* vérifie que le mouvement est valide */
enum validation_movement_t valid_move(const int start_pos_first_move, const struct move_t move, const struct move_t previous_move, const struct player_t player, const struct game_state_t game, const size_t start_position[6][10], const enum bool last_move) {
size_t j, pawn[10];
ssize_t dest, dest2;
#ifdef debug
fprintf(stderr, "=== validation de %d → %d ===\n", move.start_pos, move.end_pos);
#endif
/* si c'est le dernier mouvement et le premier, on vérifie que le joueur est bloqué */
if(last_move && previous_move.start_pos == -1 && previous_move.end_pos == -1) {
#ifdef debug
fputs("vérification si le joueur a retourné 0 pour next_move. On vérifie si il est bloqué\n", stderr);
#endif
if(nb_possible_move(game, player)==0) {
#ifdef debug
fputs("le joueur est effectivement bloqué\n", stderr);
#endif
return jump_valid;
} else {
#ifdef debug
fputs("le joueur pouvait faire un mouvement\n", stderr);
#endif
return invalid;
}
// return (nb_possible_move(game, player)==0)?jump_valid:invalid;
}
#if (allow_to_block_opposite_player == 0)
/* si c'est le premier mouvement, on vérifie qu'on ne va pas bloquer le joueur d'en face */
if(previous_move.start_pos == -1 && previous_move.end_pos == -1 && must_move(player,game, start_position, pawn)) {
#ifdef debug
fputs("le joueur peut bloquer son adversaire.\n", stderr);
#endif
for(j=0;j<10 && pawn[j]!=121;j++);
if(!search(pawn,--j, move.start_pos)) {
#ifdef debug
fputs("le joueur bloque son adversaire. Il doit déplacer un autre pion\n", stderr);
#endif
return invalid;
}
}
#endif
/* si c'est le dernier mouvement, on ne stationne pas sur une branche */
if(last_move && previous_move.start_pos != -1 && previous_move.end_pos != -1) {
#ifdef debug
fputs("vérification de ne pas stationner sur une branche\n", stderr);
#endif
return (pawn_on_branch(player.branch, previous_move.end_pos, start_position) || (start_pos_first_move == previous_move.end_pos && ! allow_returning_to_first_position_in_a_round ))?invalid:jump_valid;
}
if(move.start_pos < 0 || move.end_pos < 0 || move.start_pos > 120 || move.end_pos > 120) {
#ifdef debug
fputs("l'indice de la case n'est pas compris entre 0 et 120\n", stderr);
#endif
return invalid;
}
/* on vérifie que la case appartient au joueur */
if(game.board[move.start_pos] != player.branch ) {
#ifdef debug
fprintf(stderr, "la case %d n'appartient pas au joueur\n",move.start_pos);
#endif
return invalid;
}
/* si ce n'est pas le premier mouvement, on peut rester sur place */
if(previous_move.start_pos != -1 && previous_move.end_pos != -1 && move.start_pos == move.end_pos)
return jump;
/* on vérifie que la case de destination est libre (testé quand même dans le switch plus bas) */
/* if(game.board[move.end_pos] != none) {
#ifdef debug
fprintf(stderr, "la case %d de destination n'est pas libre\n", move.end_pos);
#endif
return invalid;
}
*/
/* on vérifie le collage si ce n'est pas le premier mouvement */
if(previous_move.start_pos != -1 && previous_move.end_pos != -1 && move.start_pos != previous_move.end_pos) {
#ifdef debug
fputs("le pion déplacé n'est pas le même qu'au mouvement précédent\n", stderr);
#endif
return invalid;
}
/* on regarde autour */
#ifdef debug
fputs("on regarde les voisins\n", stderr);
#endif
j = 0;
do {
if( (dest = move_calculation( (size_t) move.start_pos, j)) != -1 ) {
#ifdef debug
fprintf(stderr, "%d → %zu (j=%zu) ?\n", move.start_pos, dest, j);
#endif
switch(((dest == move.end_pos)?1:0)+((game.board[dest] == none)?2:0)) {
case 0: /*on veut pas y aller mais la place est occupée. peut etre qu'on veut faire le saut */
if((dest2 = move_calculation(dest,j)) != -1) {
#ifdef debug
fprintf(stderr, "%zu → %zu (j=%zu) ?\n", dest, dest2, j);
#endif
switch(((dest2 == move.end_pos)?1:0)+((game.board[dest2] == none)?2:0)) {
case 1: /* on veut y aller mais la place est occupée (déjà traité plus haut) */ return invalid;
case 3: /* on veut y aller et la place est libre */ return jump;
}
}
break;
case 1: /*on veut y aller mais la place est occupée (déjà traité plus haut) */
return invalid;
case 3: /*on veut y aller et la place est libre*/
if(previous_move.start_pos == -1 && previous_move.end_pos == -1) {
if(!pawn_on_branch(player.branch, move.end_pos, start_position)) {
if(!last_move) {
return neighbour_valid;
} else {
#ifdef debug
fputs("next_move doit etre à 1\n", stderr);
#endif
return invalid;
}
} else {
#ifdef debug
fputs("la case voisine est sur une branche de l'étoile\n", stderr);
#endif
return invalid;
}
} else {
#ifdef debug
fputs("on ne peut atteindre un voisin que sur le premier mouvement\n", stderr);
#endif
return invalid;
}
// return (previous_move.start_pos == -1 && previous_move.end_pos == -1 && !pawn_on_branch(player.branch, move.end_pos, start_position) && !last_move)?neighbour_valid:invalid;
}
}
} while(++j < 6);
#ifdef debug
fprintf(stderr, "%d ne fait pas partie des voisins\n", move.end_pos);
#endif
return invalid;
}
/* vérifie si le joueur a gagné */
enum bool winner(const struct player_t player, const size_t start_position[6][10], const struct game_state_t game) {
size_t final_branch, j;
final_branch = (player.branch+2)%6; /* décalée de 1 (pour éviter de faire +1 et ensuite -1 lors de l'accès au tableau). */
j = 0;
do
if(game.board[start_position[final_branch][j]] != player.branch )
return false;
while(++j < 10);
return true;
}