Quale sarebbe il modo più veloce per archiviare o calcolare i set di mosse legali per i pezzi degli scacchi?

0

Ad esempio, se viene tentata una mossa, posso semplicemente scorrere un elenco di mosse legali e confrontare x, y, ma devo scrivere la logica per calcolarle almeno ogni volta che il pezzo viene spostato.

Oppure, posso archiviare in un array [] e quindi controllare se x e y non sono 0, quindi è una mossa legale e quindi salverò i dati come questo [0] [1] [0] [0] ecc. Ecc. Per ogni riga in cui 1 è una mossa legale, ma devo ancora popolarlo.

Mi chiedo quale sia il modo più veloce per archiviare e leggere una mossa legale su un oggetto pezzo per il calcolo.

Potrei anche usare Matrix Matrix, ma non lo so.

Fondamentalmente voglio mantenere le regole per un determinato pezzo in modo da poter assegnare a un oggetto pezzo un piccolo modello di tutte le possibili mosse, considerando che sta iniziando dalla posizione corrente , che dovrebbe essere solo una tabella dei dati. Ma è più veloce eseguire cicli o scrivere query LINQ o archiviare array e matrici?

public class Move
{
    public int x;
    public int y;
}

public class ChessPiece : Move
{    
    private List<Move> possibleMoves { get; set; }

    public bool LegalMove(int x, int y){
      foreach(var p in possibleMoves)
      {
         if(p.x == x && p.y == y)
         {  return true;  }   
      }
    }
}

Qualcuno lo sa?

    
posta BigOmega 30.06.2013 - 00:06
fonte

5 risposte

2

Capire le mosse legali disponibili per un particolare pezzo su una scacchiera in una particolare posizione di scacchi è molto situazionale, specialmente quando si considerano le pedine ... 1 spazio tranne quando si trova nella sua posizione di partenza, poi due, e poi lanciare nelle catture e nelle catture di en passant ... quindi costruire una serie di mosse che sono "meccanicamente" possibili è un po 'difficile da iniziare. Nel caso di en passant, hai anche bisogno di sapere se l'ultima mossa dell'opponente è abilitata en passant, poiché la mossa è valida solo per una mossa dopo che l'avversario ha fatto una mossa per attivarla.

Quindi diventa ulteriormente complicato da altre considerazioni sulla situazione. La mossa espone il re del giocatore per controllare? Per l'arrocco, il re deve spostare il controllo attraverso (se la posizione finale risulta o meno sotto controllo)? Se il re è già sotto controllo, la mossa contrasta il controllo?

Penso che sarebbe meglio impostare regole per ogni pezzo includendo considerazioni speciali, direzione e distanza, piuttosto che una matrice da attraversare, dal momento che devi letteralmente determinare dove è progettato il pezzo, quindi esaminare se la posizione dopo che ci sarà sarà legale.

    
risposta data 03.07.2013 - 23:53
fonte
1

il modo più semplice sarebbe avere il LegalMove(Move) di usare codice personalizzato per ogni pezzo diverso

in questo modo devi solo controllare che abs(x-m.x)==abs(y-m.y) per un alfiere ad esempio (senza contare i pezzi di blocco)

o se hai un riferimento alla lavagna e la posizione nel pezzo, allora una logica personalizzata sarebbe (di nuovo per il vescovo):

IEnumerable LegalMoves(){
    for(int xl = x+1,yl = y+1; yl<8 && xl<8; xl++,yl++){
        if(board[xl][yl].isFree())
            yield return Move(xl,yl);
        else if(board[xl][yl].HasEnemy()){
            yield return Move(xl,yl);
            break;//can't jump over enemy
        }else break;//can't jump over own pieces
    }
    //mirror it for each of the 4 sides
}
    
risposta data 30.06.2013 - 00:37
fonte
1

Il modo più veloce, penso, sarebbe quello di mantenere una serie di mosse legali per ogni pezzo. Quando sposti un pezzo, aggiorni le mosse legali degli altri pezzi. Per il quadrato che hai lasciato, aggiungi nuove mosse ai pezzi che ora possono spostarsi lì. Per il nuovo quadrato, rimuovi le mosse legali dai pezzi che potrebbero spostarti lì prima.

Quindi (in pseudo codice):

move piece from X0,Y0 to X1,Y1
with X0,Y0:
    check surrounding squares for king/pawn moves, add legal move where appropriate
    check the knight positions, add legal move where appropriate
    check horizontal/vertical lines for rook/queen, add legal move where appropriate
    check diagonal lines for queen/bishops, add legal move where appropriate
with X1,Y1:
    same checks, but now remove legal move

Ovviamente, i controlli lungo le linee dovrebbero fermarsi quando incontrano un altro pezzo che blocca il percorso.

Potrebbe essere utile tenere un po 'di bandiera sui quadrati, in modo da sapere se le regole di raggiungibilità speciali si applicano alle pedine o al re / torre.

Da qualche parte lungo la linea, quando i pezzi vengono rimossi, questo diventa più lento del semplice controllo delle mosse legali per i pezzi stessi. A quel punto potresti passare a un controllo diretto per il pezzo in movimento, abbandonando l'aggiornamento degli altri pezzi.

Per come memorizzarlo, una maschera a 64 bit sarebbe sufficiente per codificare una scheda 8x8.

piece.removeLegalMove(square_mask):
    mymask &= ~square_mask

pieace.addLegalMove(square_mask):
    mymask |= square_mask;

piece.canMove(x, y):
    square_mask = 1 << (x + 8 * y);
    return mymask & square_mask > 0;

Ma sono abbastanza estraneo a C #, quindi non so se gestisce le maschere di bit. Presumo che lo faccia.

    
risposta data 30.06.2013 - 02:09
fonte
0

Se passi il tuo tempo a preoccuparti del modo più veloce, non avrai mai il tempo di sviluppare un programma strong. I cicli del computer sono economici. I tuoi cicli sono una risorsa molto limitata. L'ottimizzazione a questo livello è l'ultima cosa che dovresti fare. Letteralmente.

    
risposta data 30.06.2013 - 03:17
fonte
0

Scopri come i potenti motori di scacchi implementano questo. Una buona tecnica è usare i bitboard. Un sacco di lavoro può essere salvato utilizzando il pre-calcolo. Ecco un articolo: link

    
risposta data 04.07.2013 - 11:10
fonte

Leggi altre domande sui tag