BITBOARD & MATRIX

Bu öğretici(?) içerikteki karşılaşacağınız bilgiler kullanıcıya uzanan bir test aşamasından geçmemiştir. Kişisel bilgi ve tecrübelerim haricinde bir kesinlik içermemektedir.

Gözlemleyebildiğim kadarıyla başlangıç seviyesi öğreticilerin çoğunda bir programlama dili ile matris oluşturmak ve bu matrisin içerisindeki elemanların kontrol yapısının kurgulanması iç içe for döngüleriyle sağlanıyor.

Bu her ne kadar kurgulanması bir nebze daha kolay olsa da ilerleyen süreçte başa bela açacak boyutlara ulaşabilir.

Bilindiği üzere her bir for döngüsü (N döngünün tekrar sayısı olmak üzere) Big O Notasyonu’nda O(N) ile gösterilir. Bunun iç içe yazılması ise karmaşıklığın O(N²) ile hesaplanmasıyla sonuçlanır. Tekrar sayısının az olduğu göz önünde bulundurulduğunda bile masum sayılmayacak bu durumun, tekrar sayısı arttığı senaryo kabul edilebilir değildir.

Bu gibi bir soruna nasıl çözüm üretilebileceğini düşünürken aklıma bitsel işlemlerin kullanılabileceği geldi ve bu eğitici içeriği yazma kararı aldım.

İlk önce yaygın kullanılan yöntem ile anlatımımıza başlayalım.

for (int x = 0; x < width; x++)
{
  for (int y = 0; y < height; y++)
  {
    ...
  }
}

Şeklinde bir matris oluşturulur. Ardından bu matris ile ilgili kontrol işlemi yapılacağı zaman tekrar tekrar buna benzer for döngüleri yazılır, içerisinde kontrol yapıları yazılır ve makinenin gücü kullanılarak anlık kontrol sağlanır ve sonuç gerçekleşir.

Geçmişte hazırladığım iç içe for döngüleri ile hazırlanmış matris kontrol yapısı örneği:

public void FindAllMatches()
    {
        currentMatches.Clear();

        for (int x = 0; x < Board.Instance.width; x++)
        {
            for (int y = 0; y < Board.Instance.height; y++)
            {
                Gem currentGem = Board.Instance.allGems[x, y];
                if (currentGem != null)
                {
                    // LEFT & RIGHT CONTROL
                    if (x > 0 && x < Board.Instance.width - 1)
                    {
                        Gem leftGem = Board.Instance.allGems[x - 1, y];
                        Gem rightGem = Board.Instance.allGems[x + 1, y];

                        if (leftGem != null && rightGem != null)
                        {
                            if (leftGem.gemType == currentGem.gemType && rightGem.gemType == currentGem.gemType)
                            {
                                currentGem.isMatched = true;
                                leftGem.isMatched = true;
                                rightGem.isMatched = true;

                                currentMatches.Add(currentGem);
                                currentMatches.Add(leftGem);
                                currentMatches.Add(rightGem);
                            }
                        }

                    }

                    // ABOVE & BELOW CONTROL
                    if (y > 0 && y < Board.Instance.height - 1)
                    {
                        Gem aboveGem = Board.Instance.allGems[x, y + 1];
                        Gem belowGem = Board.Instance.allGems[x, y - 1];

                        if (aboveGem.gemType == currentGem.gemType && belowGem.gemType == currentGem.gemType)
                        {
                            currentGem.isMatched = true;
                            aboveGem.isMatched = true;
                            belowGem.isMatched = true;

                            currentMatches.Add(currentGem);
                            currentMatches.Add(aboveGem);
                            currentMatches.Add(belowGem);
                        }
                    }
                }
            }

gibi bir kontrol yapısı kurduğumuzda aslında optimizasyon işleminden ne kadar uzaklaştığımızı fark edeceğiz.

Bunun yerine koyulabilecek bir yöntem biliyorum. Bu yöntemin gayesi; matrisimizi bitboard dediğimiz yapının içerisinde tutmak ve formülize edilmiş yöntem ile matrisin elemanlarının kontrolünü sağlamaktır.

Hadi bunu bir örnekle inceleyelim.

• 8x8 boyutunda bir bitboard inşa ettiğimizi var sayalım. Bu bitboard’umuzdaki herhangi bir noktadaki elamanı seçmek istediğimizde:

r → row

c → column

olmak üzere;

r * 8 + c

formülü ile istediğimiz noktaya ulaşabiliriz.

• Örneğin ulaşmak istediğimiz elamanın indis numarası “19" olsun.
  8x8 lik tabloda 19 numaralı eleman 3.sıranın 3.sütununa denk gelmektedir.

3 * 8 + 3 = 19

Bitboard içerisindeki elemanın çağrılması işlemi ise:

bool GetCellState(long bitboard, int row, int col)
{
  long mask = 1L << (row * 8 + col);
  return ((bitboard & mask) != 0);
}

şeklinde tanımlanabilir.