Approach ビームサーチです。

  • 各点の重み : (1 << 3 * 中心からのチェビシェフ距離)
    この後、対角線上の点なら 4 倍、その隣なら 2 倍する。
  • 評価関数 : 各点ごとに、合ってたら 1 ,違ってたら -1 を重みに掛けて和をとる。
    この評価関数は、外側からそろえる。
  • 次の深さのノードの作り方 : バウンディングボックスに完全に含まれるまわし方で、バウンディングボックスの端またはその一つ内側を含むものに限定
  • 重複除去に Zobrist hashing
    • 現在の深さのノード群を評価が良い順に見ていくときに除去する方法と、次の深さのノードを作るときに除去する方法が有ると思いますが、今回は前者を使いました。ハッシュセットを使わずに、評価とハッシュで並べ替えて、直前のノードと同じハッシュなら除去した。
  • ビーム幅 : 残り時間を275等分して、各深さごとできるだけ多くノードを見る。最初の方は1とか2で、最後の方は3桁くらい。
  • たまに完全解にならない

  • うまくいった時 208手(input_1.txt)



  • 時間制限10倍 うまくいった時 193手(input_1.txt)



  • 時間制限100倍 うまくいった時 174手(input_1.txt)