Битбордтар немесе битбордтар

Кіріспе

Жақында мен өзімнің шахмат қозғалтқышымды жазғым келді. Бір қызығы, Интернетте бұл тақырып бойынша жақсы мақалалар көп емес. Әлсіз бағдарламалары бар мақалалар болды, олардың көпшілігі тіпті кейбір маңызды ережелерді өткізіп жіберді. Жақсы бағдарламалары бар мақалалар болды (кейбіреулері мен жасағаннан да жақсырақ болды), бірақ онда авторлар егжей-тегжейлерді өткізіп жіберіп, тек негізгі идеяларды айтты, бұл мұндай мақалаларға бірдеңе жазуды қиындатады. Сондықтан мен өз бағдарламамды жазғаннан кейін осы тақырыпқа қызығушылық танытқандардың өмірін жеңілдету үшін мақала жазуды жөн көрдім. Мен өзімді ең жақсы шахмат бағдарламасы немесе ең таза код деп санамаймын, бірақ бұл мақала өз бетімен бірдеңе жазғысы келетіндер үшін жақсы әрі оңай бастама.

Битбордтар немесе битбордтар

Тақтаны ұсынудың өте ыңғайлы жүйесі бар, егер орыс тілінде бит тақтасы немесе бит тақтасы деп аталады. Битбордтар идеясы керемет сәйкестікке негізделген: шахмат тақтасында 64 шаршы бар, ал қазіргі компьютерлер 64 биттік сандармен керемет жылдам жұмыс істей алады. Сонымен, біз барлық кескіндерді сақтау үшін осы нүктелік кескіндердің 12-ін пайдалана аламыз. Әрбір осындай тақтайшада фигураның (немесе пешканың) қандай да бір түрі сақталады, мысалы - бір тақта қара рыцарларға, екіншісі ақ пешкаларға, үшіншісі қара патшаға жауап береді.

64 ұяшықтан тұратын массив емес, бит тақтасын таңдаудың басты себебі - жоғары жылдамдық және таңқаларлық емес болғандықтан, ыңғайлылық. Мысалы, біз пешканың берілгенін тексеруіміз керек. Өткізілген пешка, Википедияға сәйкес, болып табылады

бір файлдағы пешка
, оның алдында жаудың күркелері жоқ, ал іргелес файлдарда не жаудың пештері жоқ немесе олар шабуылда тұрған шаршыларды ұстамайды, олар арқылы пешка көтерілу алаңына
өтуі керек .

64 шаршының массивін пайдалана отырып, қайсысының өтіп бара жатқанын және қайсысы өтпейтінін анықтау үшін, ең нашар жағдайда, әрбір пешке үшін 18 шаршыны тексеру керек еді. Растрлық кескіндерді пайдалана отырып, біз пешканың өткен пешка деп аталуы үшін қарсыластың пешкалары қай шаршыларда болмау керектігін алдын ала есептей аламыз, содан кейін бұл мәліметтерді пайдаланып, пешке бір разрядта «және» өткізілген пешка екенін анықтай аламыз. операция.

Мен бит тақталарымызды іске асыруға көшуді ұсынамын. Шындығында, оларды жүзеге асырудың қажеті жоқ, өйткені бит тақтасы 64 биттік нөмірдің әдемі атауы ғана. Сонымен, бит тақтасының мәлімдемесі келесідей болады:

typedef uint64_t Bitboard;

Обращаю внимание, что используется именно беззнаковое число, так как в процессе программирования будут использоваться битовые сдвиги, а битовые сдвиги со знаковыми переменными работают не так как нам надо будет (ведь 1 бит из 64 при использовании знаковых переменных отвечает за знак числа и его компьютер трогать болмайды).

Бірақ бір декларациямен өмір сүру өте өкінішті, өмірді жеңілдету үшін бірнеше қосымша операцияларды орындау керек.

static constexpr void set_1(Bitboard &bb, uint8_t square) {

        bb = bb | (1ull << square);

}

static constexpr void set_0(Bitboard &bb, uint8_t square) {

     bb = bb & (~(1ull << square));

}

static constexpr bool get_bit(Bitboard bb, uint8_t square) {

    return (bb & (1ull << square));

}

Мұнда индекс бойынша нүктелік кескіндерге қатынасуға арналған қарапайым әрекеттер берілген. Сіз олардан аулақ болуға тырысуыңыз керек, өйткені олар өте баяу, бірақ оларсыз мүлдем жасай алмайсыз.

Біз сондай-ақ жалғыз биттердің санын санауымыз керек. Бұл білім, мысалы, позицияны бағалау кезінде қажет. Позицияның қаншалықты жақсы екенін білу үшін, кем дегенде, Ақта қанша бөлік бар және Қарада қанша бөлік бар екенін білу керек және ол үшін оларды санау керек.

Бірақ мұны қалай жасауға болады? Сіз ойлай алатын ең аңғал нәрсе - барлық 64 бит арқылы өту және санау, бірақ менің ойымша, бұл өте тиімсіз екені анық. Habré-де осы тақырып бойынша тамаша мақала бар , бірақ бұл стандартты кітапханада, атап айтқанда бит тақырыбында енгізілген, сондықтан дайын функцияны қолданайық: