Predstavitev pozicij: Razlika med redakcijama
Vrstica 1: | Vrstica 1: | ||
− | + | Predstavitev šahovske igre vključuje predstavitev pozicij in potez. Pozicije predstavljajo stanja igre, poteze pa operatorje, ki spreminjajo eno pozicijo v drugo pozicijo. Obe predstavitvi morajo biti sposobne izvajati naslednje operacije: | |
− | * | + | * naredi potezo |
− | * | + | * vrni potezo |
− | * | + | * ustvarei seznam vseh možnih potez |
− | * | + | * ustvari seznam potez jemanja |
− | * | + | * ovrednoti pozicijo |
− | * | + | * shrani poteze |
− | * | + | * primerjava pozivcij |
− | * | + | * nastavi pozicijo |
− | * | + | * preverjanje ali se je pozicija ponovila tri krat |
− | * | + | * preverjanje pravila 50 potez |
− | * | + | * preverjanje ali je kralj v šahu |
− | + | Vse naštete operacije morajo biti časovno zelo učinkovite, kajti uporabljamo jih znotraj iskalnega algoritma. | |
+ | Tako se učinkovitost predstavitve šahovske igre prenese tudi na učinkovitost šahovskega programa. | ||
− | Bitboard | + | Najbolj učinkovito predstavitev predstavlja ''''Bitboard'''. Ta predstavitev vsebuje množico 64 bitnih celih števil. Oba igralca imata 6 števil za vsak tip figure. Npr. spodnja pozicija ima naslednjo bitno predstavitev kmetov: |
− | + | ||
<center> | <center> | ||
<table width ="80%"><tr><td> | <table width ="80%"><tr><td> |
Redakcija: 16:35, 5. oktober 2006
Predstavitev šahovske igre vključuje predstavitev pozicij in potez. Pozicije predstavljajo stanja igre, poteze pa operatorje, ki spreminjajo eno pozicijo v drugo pozicijo. Obe predstavitvi morajo biti sposobne izvajati naslednje operacije:
- naredi potezo
- vrni potezo
- ustvarei seznam vseh možnih potez
- ustvari seznam potez jemanja
- ovrednoti pozicijo
- shrani poteze
- primerjava pozivcij
- nastavi pozicijo
- preverjanje ali se je pozicija ponovila tri krat
- preverjanje pravila 50 potez
- preverjanje ali je kralj v šahu
Vse naštete operacije morajo biti časovno zelo učinkovite, kajti uporabljamo jih znotraj iskalnega algoritma. Tako se učinkovitost predstavitve šahovske igre prenese tudi na učinkovitost šahovskega programa.
Najbolj učinkovito predstavitev predstavlja 'Bitboard. Ta predstavitev vsebuje množico 64 bitnih celih števil. Oba igralca imata 6 števil za vsak tip figure. Npr. spodnja pozicija ima naslednjo bitno predstavitev kmetov:
0 0 0 0 0 0 0 0 |
The 64-bit presentation allows the move generator to be made very fast and a fast evaluation function. For example, the expression (WhitePawns << 8) & ~AllSquares is used to represent all possible destination squares of white pawns for one square up. Let us see this expression in grater detail. Firstly, the presentation of white pieces was shifted by 8 bits or moved for one square up. Then with negation of presentation of all pieces we get presentation of empty squares. Finally, with bitwise operation AND between both presentations we get presentation of destination squares. This presentation and presentation of white pawns enables generating all possible moves for white pawns for one square up. Similarly, we can calculate all possible moves for pawns, knights, and the king. For generating moves for sliding pieces we use addition information which is described below.
Rotated bitboard
The standard bitboard presentation described above is very useful in generating moves for all pieces except sliding ones (bishop, rock, queen). Rotated bitboard provides additional information for certain types of pieces, namely the sliding ones. Bitboard is rotated by 45, 90, and 135 degreees. The 45 and 135 degrees rotations are used for calculating diagonal and the 90 degrees for calculating vertical moves. The speedup of rotated bitboard relies on quick discovery of attacks on certain squares without the need to use program loops which is the case for all other representations.