世界最小・487バイトのチェスプログラム 25
ストーリー by hylom
さすがにコンピュータと対戦はできません 部門より
さすがにコンピュータと対戦はできません 部門より
あるAnonymous Coward 曰く、
わずか487バイトという世界最小のチェスプログラム「BootChess」が登場した（GIGAZINE）。
制作したのはRed Sector Incで、33年にわたって世界最小のチェスプログラムの座に君臨してきた1K ZX Chess（672バイト）よりも小さい。WindowsやLinux、OS X、DOS、FreeBSDなどで動作するとのこと。本体はBootChess by Red Sector Inc. :: pouët.netからダウンロードできる。
1K ZX Chessソースコード完全解説 (スコア:2, 参考になる)
33年にわたって世界最小のチェスプログラムの座に君臨してきた1K ZX Chessですが、
1982〜1983年に雑誌で開発者David Horne氏が自らソースコードを完全解説した記事があり、
現在archive.orgで読めるそうです。
http://www.softantenna.com/wp/software/1k-zx-chess/ [softantenna.com]
http://archive.org/stream/your-computer-magazine-1983-02/YourComputer_... [archive.org]
468byte (スコア:2)
ダウンロードしてみたのですが、作成日2/3のファイルが追加されており、現在のプログラムサイズは468byteとなっているようです。
Gigazineの記事は1/28のものですので、こちらは間違いではないです。
思考ルーチン (スコア:1)
人対人の対戦ゲームじゃなくて、思考ルーチンまで含めて最小を目指すとどうなるんだろ。
いろいろと方向性があって面白そう。
まず、「とにかくルール違反無しにプレイが進められるAI」部門。
「ユーザが入力した手が違反かどうか」を判定するルーチンはあるはずなので、
「ルール違反にならない手」を探索する処理はかなり小さく書けるはず。
左上に一番近いコマを一歩ずつ進めるのみ、と言うようなネタAIにはなるけど、
ルールが厳密なのでコードゴルフとして有りそうなレギュレーション。
優勝者と準優勝者のプログラムを「世界一頭の悪いチェス勝負」とでも称して戦わせるおまけもつけられる。
「そこそこ遊べて小さい」はルールの設定が難しいので、
ルールをどう解釈したかと言う辺りも含めたプレゼンテーションが求められるのかな。
あと、「理屈の上で絶対に負けない最小のチェスプログラム」部門というのもネタとしては成立しうる。
処理時間や必要メモリ量に関するレギュレーションを設けると恣意的なルールになるので、それ抜きにしてしまうといい。
これは、あらゆる手筋を全探索する最小のプログラムを作る勝負になる。
実際に走らせると途方もないメモリと処理時間がかかるとしても、気にしない。
評価は、プログラムを走らせるんではなくて、全探索かそれと同等になっているかどうかを、
プログラムを解析することで行う。その証明手順も含めたプレゼンテーションが求められる。
Prolog辺りで書くとすごく小さなプログラムになりそうなので、そういった処理系を小さくする工夫勝負になるかな。
あるいは、チェスの性質を数学的に検証して、刈っても大丈夫だと証明可能な枝刈りのアイデアをどれだけ出せるかの勝負とか。
Re:思考ルーチン (スコア:3, 参考になる)
>人対人の対戦ゲームじゃなくて、思考ルーチンまで含めて最小を目指すとどうなるんだろ。
思考ルーチンも487バイトに含まれてるし、対戦もできますよ。
詳しくはBootChess.txtの5.1 - The TaxiMax ai used に解説がある。
チェスは詳しくないけど一般的なMiniMax法はプログラムサイズやRAMサイズの制約から使えないので、
その亜種(TaxiMaxと名付けたらしい)を採用していて、詰み位置にキングを動かしてしまうことがある代わりにMiniMaxより半手強いと言えるらしい。
Windows環境でもXP SP3や32bit版7ならそのまま動くらしいし、DOSBox(GUIフロントエンドのD-Fend Reloaded [sourceforge.net]もあるよ)とかで簡単に動かせるから試してみては？
プレイそのものはSpanish Opening定跡の相手初手e4で始まるようになってて、チェスボードの配置 [wikipedia.org]を参考にしながら[動かしたい駒の位置][移動先の位置](例えば右端のポーンを2歩進めるならH7H5)を入力していけばいい。
DOSBoxで試した限りでは入力のタイミングに結構癖があるのと、AI思考中はしばしフリーズしたようになって反応がちょっと分かりづらいのが難点。
今まで最小だった1k ZX Chessに手を加えたZX81 1K CHESS plus [youtu.be]くらいに見た目がよければいいんだけど。
Re: (スコア:0)
＞「ユーザが入力した手が違反かどうか」を判定するルーチンはあるはず
元プログラム見てませんが、そもそも違反する入力自体が出来ない書き方をみつけて軽量化している可能性もありませんか？
小数点を扱わないコードなら0.5マス進むことはできない、みたいな。
いや頭悪いんでこれくらいしかたとえ浮かびません。
Re: (スコア:0)
例えば、1手目として「自分のポーンを相手のキングの上に移動」という入力を受け付けてしまうプログラムを
「チェスプログラム」とは称して公開したりはしないと思うんだ。
OS不要 (スコア:1)
OS不要のプログラムとDOS用のCOMファイルなので、
64bitWindowsやLinux、OS X、FreeBSDではPCエミュレータやDOSエミュレータなどが必要。
BIOSを利用しているのでFM-Rや9801などでは無改造では動かない。
80386命令で拡張されたセグメントレジスタを利用しているので、PCｊrなどでも動かない。
Re: (スコア:0)
386命令どころか486命令使ってますね
Re:OS不要 (スコア:1)
コプロ命令は？
# 487だけに
-- う～ん、バッドノウハウ？
Re: (スコア:0)
まあ487は486SXと協調して動くコプロではないしな。
Re: (スコア:0)
387/487は内蔵の足吊回路で 386/486をkillしてたんだっけ?
マイクロコード化 (スコア:0)
次はFPGAででも実装するんだ
チェス盤プログラム (スコア:0)
盤の代わりです。思考はしません。
応用して将棋盤とか、(囲碁は簡単そう)
将棋盤はキャラが問題かな
Re: (スコア:0)
日本語とか中国語とか（要は漢字）表示可能な端末を前提にしてよいならキャラは楽勝では。＞将棋
まあさかさまに表示するのはできないとして、敵側は色を変えるとか。
惜しい (スコア:0)
もうちょっと短かったらアスキーの「256バイトプログラムコンテスト」に応募できたのに
Re: (スコア:0)
そういえば最近メガデモは流行らないんですかね
スラドのトピでもめっきり見かけてないような
Re: (スコア:0)
フロッピーサイズ程でもないので、このチェスプログラムは「キロデモ」、通称「キモ」と名付けてみた。(デモとは言えないが。)
Re:惜しい (スコア:2)
普通に1k intro辺りで。
487はメインプログラムだけでは？ (スコア:0)
サブというか大部分のルーチン（プログラム）は他のファイルasmとかbinとかになってる。
メインからそのルーチンをロードして使っている。
Re:487はメインプログラムだけでは？ (スコア:1)
binだけフロッピーのブートセクタに書き込めば動きます。
comだけPC-DOSなどから起動すれば動きます。
Re: (スコア:0)
asmをロードして何に使うの?
Re: (スコア:0)
このプログラムのための特別な言語で書くという方法がありますね。
この言語には、「チェスを実行する」という命令があります。
Re: (スコア:0)
HQ9+ですか
Re: (スコア:0)
RSIの連中なら何でもやるだろう？って
AMIGAは関係ないの？
７行プログラミング (スコア:0)
国産だと7x80=560byte以下*のテトリスとか対戦オセロとかもあったよね。
* 改行はLFにすれば1byte扱いで。
# ソースレベルでだけど。でもテトリスは確かインタプリタだったはず。
# 気になる人はググって。