Autor Wątek: [C] Szachy - problem z przekazaniem wartości w algorytmie alphabeta  (Przeczytany 939 razy)

Offline kamilbrzezinski

  • Użytkownik

# Maj 24, 2010, 17:51:09
Cześć,
Piszę właśnie szachy i natrafiłem na problem z algorytmem alpha-beta. O ile wartość jaką zwraca wydaje się być w porządku, to nie wiem w jaki sposób poinformować mój program o tym, jakie ruchy po kolei wykonać. W którym miejscu i w jaki sposób powinienem je zwrócić? W kodzie zobaczycie kilkanaście zakomentowanych linijek, w których próbowałem to zrobić, ale żadna nie wydaje się być właściwa.
Czy sam algorytm jest ok? Bo tutaj też mogłem popełnić błąd. Będę bardzo wdzięczny za wszelką pomoc.

Kod: (c) [Zaznacz]
#include <stdio.h>
#include "alpha.h"
#include "move.h"
#include "static.h"
#include <math.h>

#define countof(a) (sizeof(a)/ sizeof(a[0]))

int alpha_beta(piece_entry *board[128], piece_entry *pieces_w[16], piece_entry *pieces_b[16], int side, int depth, int alpha, int beta)
{
  int best_score = -1000000;
  //int move_score = 0;
  int possible_moves[128][2];
  int i;
  int old_field=-1;
  int new_field=-1;
  int old_pos=-1;
  int new_pos=-1;
  int told_field=0;
  int tnew_field=0;
  int tmp_type_o;
  int tmp_type_n;
 
  piece_entry * tmp_ptro;
  piece_entry * tmp_ptrn;
  tmp_ptro = NULL;
  tmp_ptrn = NULL;
 
  for(i=0; i<128; i++)
  {
    possible_moves[i][0] = -1;
    possible_moves[i][1] = -1;
  }
  generate_moves(board, pieces_w, pieces_b, possible_moves, side);

  for(i=0;;i++) {
    if(possible_moves[i][0] == -1 || possible_moves[i][1] == -1) break;
   
    old_field = possible_moves[i][0];
    new_field = possible_moves[i][1];
    told_field=old_field;
    tnew_field=new_field;
    tmp_ptro = board[old_field];
    tmp_ptrn = board[new_field];
    tmp_type_o = tmp_ptro->type;
   // tmp_type_n = tmp_ptrn->type;
    //printf("o %d n %d",old_field,new_field);
    if(board[new_field] != NULL) board[new_field]->captured=1;
    board[new_field] = NULL;
    board[new_field] = board[old_field];
    //printf("pos %d type %d",board[old_field]->position,board[old_field]->type);
    board[new_field] -> position = new_field;
    if(board[new_field] -> position>111 && board[new_field] -> type ==1) board[new_field] -> type=6;
    if(board[new_field] -> position<8 && board[new_field] -> type ==7) board[new_field] -> type=12;
    board[old_field] = NULL;
    move_num++;

    if(depth==0 )
    {
      move_score = static_evaluation(board,pieces_w,pieces_b,side);
   
    }else {move_score = -alpha_beta(board, pieces_w, pieces_b, -side, depth-1, -beta, -alpha);}
   
   
      //undo_move_here();
     
    board[told_field] = tmp_ptro;

    board[told_field] -> position = told_field;
    board[told_field]->type=tmp_type_o;
   
    board[tnew_field] = tmp_ptrn;
    if(board[tnew_field] != NULL)
    {
      board[tnew_field]->position=new_field;
      board[tnew_field]->captured = 0;
    }
      move_num--;
   
    if(move_score > best_score)
    {
      best_score = move_score;
      /*old_pos=old_field;
      new_pos=new_field;*/
      /*old_position = old_field;
      new_position = new_field;*/

    }
    if(best_score > alpha) {
     
      alpha = best_score;
      /*old_position = old_field;
      new_position = new_field;*/
    }
    if(alpha >= beta )
   
    {
      /*old_position = old_pos;
      new_position = new_pos;*/
      /*old_position = old_field;
      new_position = new_field;*/
      return alpha;
    }
   
  }

  /*old_position = old_pos;
  new_position = new_pos;*/
  /*old_position = old_field;
  new_position = new_field;*/
 
  return best_score;
}

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline counterClockWise

  • Użytkownik

# Maj 24, 2010, 17:58:29
Potrzebujesz tylko wykonać jeden ruch - dla aktywnego gracza sterowanego przez AI, czy nie?

Offline Kos

  • Użytkownik
    • kos.gd

# Maj 24, 2010, 18:10:27
[off] Ten Kamil Brzeziński z IFE PŁ? :) [/off]

Offline kamilbrzezinski

  • Użytkownik

# Maj 24, 2010, 18:16:41
Potrzebujesz tylko wykonać jeden ruch - dla aktywnego gracza sterowanego przez AI, czy nie?
Tak, uruchamiam program, wykonuję swój ruch, a potem dla gracza sterowanego przez AI wywołuję funkcję alpha_beta, która powinna mi zwrócić najlepszy możliwy według AI ruch.

Cytat: Kos
[off] Ten Kamil Brzeziński z IFE PŁ?  [/off]
Tak, to ja ;d Z Rafałem mamy ten projekt i piszemy właśnie.

Offline counterClockWise

  • Użytkownik

# Maj 24, 2010, 20:51:48
Tak, uruchamiam program, wykonuję swój ruch, a potem dla gracza sterowanego przez AI wywołuję funkcję alpha_beta, która powinna mi zwrócić najlepszy możliwy według AI ruch.

No to jaki problem? Idziesz pewną ścieżką dla której masz obliczoną heurystykę. Możesz zapamiętać dla niej listę węzłów lub tylko pierwszy ruch = bezpośredni dzieciak korzenia z najlepszym wynikiem.
Dziwi mnie to bardzo, bo jeśli umiesz zaimplementować min-max + alfa-beta na drzewie ruchów szachowych, to nie powinieneś mieć żadnych problemów z zapamiętaniem pierwszego, najlepszego węzła.
« Ostatnia zmiana: Maj 24, 2010, 20:54:18 wysłana przez counterClockWise »