Scacchi: decidere in modo efficiente se è stato effettuato un accoppiamento di controllo

3

Questa domanda riguarda la creazione di un motore di scacchi. Ho fatto proprio questo, e a mio modesto parere abbastanza elegantemente. Ma mi mancano le mie condizioni finali.

Ecco alcune funzioni di pseudopython che uso.

# Move from position old to new
def move(old, new):
    if is_legal(old, new):
        # Eat and move
        if is_legal(new, enemy_king) or check_in_los(enemy_king, old):
            # Set check on enemy king
        if piece_type == 'Pawn' and position at the end of board:
            # Convert to Queen

def is_legal(old, new):
    # Assure piece is moving, it's your own and new position not on another own piece
    # Based on piece type, assure it's maneuvering properly
    # Assure there are no pieces in between the positions if applicable

    if piece_type == 'King':
        is_checked(new)  # Not moving to a checked square
    elif checked:
        # Assure check is removed
    else:
        check_in_los(own_king, old)  # Moving the piece does not create a check from behind

# Determine if king is checked from line of sight
def check_in_los(king_pos, direction):
    # Divide path into single-square steps
    # Find next piece in direction by incrementing king position by step
    if is_legal(next, king_pos):
        # King is checked from direction

# Determine if king is checked
def is_checked(king_pos):
    # Check if knight positions around kings contain enemy knights
    # For every 8 directions around king, check_in_los(king, direction)

Ora al compagno di controllo. Sarebbe banale controllare tutte le posizioni intorno al re se si tratta di una posizione legale, ma non è abbastanza.

Considera il seguente scenario in cui il re bianco è minacciato:

   A    B    C    D    E    F    G    H
1  BR |    | BR |    |    |    |    |   
2     |    |    |    |    |    |    |   
3     |    |    |    |    |    |    |   
4     |    |    |    |    |    |    |   
5     |    |    |    |    |    |    |   
6     |    |    |    |    |    |    |   
7     |    |    |    | WN |    |    |   
8     | WK | BQ |    |    |    |    |   

Il re (B8) non ha mosse legali a sinistra, ma il cavaliere (E7) può salvarlo mangiando la regina. Allo stesso modo se la posizione della regina è cambiata e il cavaliere è invece una torre:

   A    B    C    D    E    F    G    H
1  BR |    | BR |    |    |    |    |   
2     |    |    |    |    |    |    |   
3     |    |    |    |    |    |    |   
4     | BQ |    |    |    |    |    |   
5     |    |    |    |    |    |    |   
6     |    |    |    |    |    |    |   
7     |    |    |    | WR |    |    |   
8     | WK |    |    |    |    |    |   

La torre bianca può salvare il re spostandosi su B7.

Un approccio ingenuo al controllo di un compagno immagino che implichi il controllo di ogni possibilità, ma ciò sembra uno spreco.

Quale sarebbe un buon modo per raggiungere questo obiettivo? Preferibilmente usando le funzioni già in atto. Sono anche aperto ad altri approcci, se necessario. Mi è venuto in mente che forse sarebbe utile tenere traccia dei pezzi di controllo o anche di ogni quadrato che viene controllato e il modello di controllo di ogni singolo pezzo, ma non ne sono sicuro ..

    
posta Felix 15.09.2018 - 18:53
fonte

3 risposte

2

Questa è una di quelle situazioni in cui la mente umana ha un vantaggio rispetto a un computer. È abbastanza semplice per un essere umano decidere se una posizione negli scacchi è un compagno di controllo o meno.

Possiamo scartare la maggior parte delle mosse come non rilevanti per la posizione. Creare un algoritmo che scarta queste mosse è piuttosto complicato.

La semplice soluzione di affrontare tutte le mosse possibili (che al massimo possono essere nella regione 40-50 con molti pezzi sulla scacchiera, spesso molto meno) è forse ingenua, ma è veloce e richiede molto meno sforzo di cercando di mettere in atto un algoritmo per decidere se una posizione è un compagno di controllo o no.

Immaginando una posizione in cui un cavaliere e un alfiere controllano il re, puoi prendere il cavaliere ma è ancora un controllo del vescovo. Oppure puoi prendere una regina che controlla il re, ma il pezzo che può farlo non può essere spostato perché ciò provocherebbe un controllo da una torre.

Diventa davvero molto complesso molto veloce. Perché non passare lo stesso tempo a migliorare altre parti del programma?

Questo è il motivo per cui link menzionato da Ewan nei commenti dice che lo stoccafisso prova tutti si muove e se non ci sono mosse legali allora è il compagno di assegno (simile al compagno stantio se non ci sono controlli in primo luogo).

    
risposta data 15.09.2018 - 19:18
fonte
2

Quando generi tutte le mosse possibili e le valuti per il meglio, sei sicuro di prendere in considerazione il valore dei pezzi che potrebbero essere presi.

Usa lo stesso metodo e dai al Re un valore molto alto; questo è il solito approccio.
Non esiste una scorciatoia magica per riconoscere uno scacco matto - ricorda che è definito come "il Re sarà inevitabilmente catturato nella prossima mossa".

Fermare una partita a scacchi una mossa prima della cattura del Re è una cortesia storica. Va bene fare lo stesso nel tuo programma, ma non c'è bisogno o guadagno dall'inventare una meccanica diversa.

    
risposta data 16.09.2018 - 02:12
fonte
2

Questo requisito non cade semplicemente da qualunque routine determina la mossa migliore da fare in ogni punto del gioco?

Non sei autorizzato a terminare la tua mossa con il tuo re sotto controllo. Questa non è una mossa valida, quindi la routine di movimento non dovrebbe mai prenderla.

Quindi, dopo la mossa dell'avversario, prova a determinare la mossa migliore che puoi fare normalmente. Se non ci sono mosse legali, il gioco è finito. Se il re è attualmente sotto controllo, allora è scacco matto, altrimenti è in stallo.

    
risposta data 17.09.2018 - 15:38
fonte

Leggi altre domande sui tag