双子座線型群

Искусственный язык / Программирование / Шахматы / Математика

月別: 8月 2015

シェルトの棋譜の圧縮

2015-08-25 by 古城みの コメントする

シェルトの指し手は、動かす駒(29 通り)とその動き(盤上+方向転換+張り戻しの計 52 通り)と随伴情報(随伴なし+上下左右随伴の計 5 通り)の三つで表すことができるので、単純に指し手を符号化する場合 $5+6+3=14$ ビットで表せることになります。

局面の最大分岐数(合法手数)は、将棋は 593 手1、チェスは今まで見つかっている中では 218 手2のようなので、だいたいシェルトの最大分岐数も 200 以下に収まる気がします(予想)。その場合、局面のすべての合法手を列挙&ソートしたときのインデックスで手を表すという方法をとると、一手あたり 8 ビット程度で表せることになります。『シェルト-Vas e Lantis-』の棋譜URLでは一手あたり 7 ビットで表している(違法手は別の手段で表す)ので、$n$ 手の棋譜は $\frac{7}{6} n$ 文字で表されることになります。


  1. 将棋における最大分岐数 – 奈良女子大学 ↩
  2. max amount of moves from a position? ↩
カテゴリー: ボードゲーム タグ: シェルト

シェルトの局面ハッシュ

2015-08-23 by 古城みの コメントする

サイトに局面図を表示したい都合で局面図スクリプトを作っていたら、局面ハッシュ(圧縮)を再考してみたくなったので再考してみました。そのうち何らかの形でサイトの方にまとめると思います。

このハッシュは可逆ハッシュで、34 文字(204 ビット)で 1 つの局面を表すことができます。1 文字あたり 6 ビットを割り当てて、文字は Base64url と同じものを使います。この場合表現できる状態の数は $2\times 10^{61}$ ということになりますが、以前シェルトの合法局面数を計算(ページ作成中)したところ $8\times 10^{49}$ という値になったので、やろうと思えばもっと縮められるはずということになります。ただ、ここから縮めようとするとちょっと面倒なことにならざるを得ない感じだったので、やめることにしました。

このハッシュは、手番情報と方向転換情報からなる先頭 5 文字($1+29$ ビット)と、1 文字あたり 1 つの駒の状態を表した 29 文字を合わせた計 34 文字からなります。手番情報は、次の手番が先手か後手かを表すもので、方向転換情報は、29 の駒が方向転換しているかどうかを(方向転換不能な駒も含めて)表すものです。この場合、1つの駒がとりうる状態は盤上のマス(49 通り)と持ち駒台と張り駒台と駒箱の計 52 通りなので、ちょうど 1 文字で表せることになります。

この仕様だと 1 文字に 1 つの駒の情報が(方向転換を除いて)対応するうえビットが余りなく(6 ビットで区切る場合)使い切られるので、個人的に扱いやすそう&まとまってる感があります。駒の情報の並びについては使徒の順(dia, vio, lis, …)にすることを考えました。なお後衛の方向転換情報を取り除くと 2 文字削れて 32 文字(2 ビット余り)になります。この場合は駒の情報の並びは開始局面に倣ったもの(pal, ful, mik, …)にしたほうが分かりやすそうです。

カテゴリー: ボードゲーム タグ: シェルト

プロフィール

古城みの

リンク

  • 線型結界(サイト)
  • Twitter
  • Pixiv
  • SoundCloud

最近の投稿

  • 詰めシェルトの解答
  • tiv 1
  • シェルトの指し手表記
  • シェルトの対局記録
  • 高さ実数のテトレーション

最近のコメント

  • シェルトの対局記録 に シェルトの指し手表記 – 双子座線型群 より
  • JavaScriptでparse_str(クエリ文字列のパース) に JavaScriptでhttp_build_query より

アーカイブ

  • 2018年2月
  • 2018年1月
  • 2017年2月
  • 2016年10月
  • 2016年1月
  • 2015年12月
  • 2015年11月
  • 2015年9月
  • 2015年8月
  • 2014年9月

カテゴリー

  • プログラミング
  • ボードゲーム
  • モジュール
  • 制作
  • 告知
  • 数学
  • 棋譜

メタ情報

  • ログイン
  • 投稿フィード
  • コメントフィード
  • WordPress.org

Copyright © 2021 双子座線型群.

Omega WordPress Theme by ThemeHall