「120 行で vi っぽいエディタを作る」が予想以上に評価されておりまして、驚きつつも「いいね」していただいた皆様には本当に感謝しております。ありがたや…。
今回は 18 年前の 2001 年に 2ch に投稿された「7 行オセロ」(七行プログラミング 337)をちょっとだけ改造して、先手後手を選択できるオセロを 79 文字 × 7 行に収めてみたいと思います。
…と、これだけでは何なので、文末にオセロゲーム開発プラットフォームのコードを載せておきます。これは約 150 行からなるリファクタリング版のコードです。AI ルーチンを司る think() 関数を差し替えることより、自作の思考ルーチンなどのテストに使ってもらえれば幸いです(参考版の Mini-Max 法による思考ルーチン込)。
なお、ゲーム業界ではコンピュータ側の思考ルーチンのことを AI 等と呼ぶことがありますので、ここでも AI ルーチンと呼んでいます(昨今の機械学習系の記事を期待していた皆さん、ごめんなさい)。
7 行オセロのオリジナル版
オリジナルのコードはこんな感じです:
#include <stdio.h>
int p,t,a,d,c,v,i,m[90]={0},s,r[]={-10,-9,-8,-1,1,8,9,10};void k(){if(m[p]==0)
for(i=0;i<8;i++){for(c=0,v=p+r[i];m[v]==3-t;v+=r[i])c++;if(c&&m[v]==t){a+=c;v=
p;if(d)do m[v]=t,v+=r[i];while(m[v]!=t);}}}char*h="・○●\n";int main(){for(i=
1,m[41]=m[49]=2;i<10;m[i++*9]=3)m[40]=m[50]=t=s=1;for(;;a=d=0){for(p=9;p<82;++
p)k(),printf("%.2s",&h[m[p]*2]);if(a)for(d=a=s=p=8;a==8;k())t-2?(scanf("%d %d"
,&p,&i),p+=i*9):++p;else if(s)s=0,printf("pass");else break;t=3-t;}return 0;}
このコードを読めば読むほど、これを書いた人は本当に凄い人だと感じます(しかも読み人知らずだし…プログラム版の万葉集があるならば、収められるべき作品…だと思います)。
これを読みやすくしたものが、https://uguisu.skr.jp/othello/ さんのところに掲載されています:「オセロプログラム ~7行のC言語で書くコンピュータ対局~ https://uguisu.skr.jp/othello/7gyou.html」
オリジナル版は盤面表示が(いわゆる)全角文字を使っていたのですが、上記のサイトでは ASCII 文字の O とか X になっていますが、本質的な部分は変化していません。
オリジナル版では変数 t が、解説ページ版では変数 turn が、手番を示す情報を格納しています。先手版なら 1 が、後手版なら 2 が格納される変数です。ちなみに先手後手の切り替えは t=2-t; と記述されており、これもなかなかシビレるコードではないかと思います。
プレイヤーが後手になるための処理
変数 t が手番の管理に関わっているので、ゲーム開始時に t=2 とすれば、コンピュータが最初に指し、次に人間(=プレイヤー)が指すプログラムとなります。具体的には、main() 関数の最初の方に書かれている、m[40]=m[50]=t=s=1; を m[40]=m[50]=s=1,t=2; と変更すれば終わりです。
m[40]=m[50]=t=s=1; // これを
m[40]=m[50]=s=1,t=2; // こうする
問題は、この変数 t をどうやって 1 で初期化したり、2 で初期化するようなコードを 79x7 文字に詰め込むのか、ということになります。
余白の攻略
オリジナルのコードはかなり詰められており、1 行目以外は最後の 7 行目のみに 1 文字分の空白があるだけで、2 〜 6 行目は 78 文字目までぎっちりと詰まっております。となると、攻略すべきは必然的に 1 行目の #include 文以降のこの余白部分になります。
#include <stdio.h>/* <------ ここには 60 文字分の余白が存在している ------> */
しかし、include 文(ディレクティブ)は、gcc の挙動を見る限りでは、その後に何かコードを置くことを許可してはくれないようです。そこで、stdio.h をインクルードしないという戦略を今回は取りたいと思います。
そもそも、stdio.h をインクルードするのは何故なのでしょうか? それは、printf() と scanf() の両関数のプロトタイプ宣言のためです。なので、#include を以下のコードで置き換えます。
int printf(const char*,...);int scanf(const char*,...);
これは最早プリプロセッサディレクティブではないので、その後にもコードを書くことができます。結果として、23 文字分の余白を創出することができました。
先手後手の UI 設計
余白が出来たので、先手後手を指定するコードを追加していきたく思いますが、先手か後手を問うにはまだまだ余白が足りません。そこで今回はコマンドライン引数を活用する方法をとりたいと思います。つまり、main() 関数の引数としてシステムから与えられる argc の数を変数 t に反映させようという作戦です。単純に考えると、int main(int t,char**argv) とすれば良い気もしますが、どうも main の第 1 引数として与えられる変数は const int であるかのような振る舞いをするため、一度、別名の変数で受け取って、それを変数 t に代入する方針にします(macOS の gcc、 Apple LLVM version 10.0.0 (clang-1000.11.45.5)では argc の変更はできませんでした)。具体的には、
int main(int q,char**z){t=q; ... }
というコードに変更します。
後手の時のコマ変更
これで先手・後手を選べるようになりましたが、このままで先手後手に関わらずプレイヤー側のコマは 'o' です。これを変更するようにしたいと思います。コマの種類は変数 h にて定義されているので、この h の内容を変更すればよさそうです。
// オリジナル版における駒用キャラの定義
char*h=" - o x\n";
先手の時、つまり t=1 の時には、h[3]=='o' および h[5]=='x' とし、
後手の時、つまり t=2 の時には、h[3]=='o' および h[5]=='x' となれば良い訳です。
O と X をそれぞれ定義するようにすると、コード量が増えてしまいますので、h[3] も h[5] も 'X' としておき、t の値に応じて h[3] のみを変更するようにします。
char h[]=" - x x\n";
h[2*t+1]='o';
変数 h の型が char* から char[] に変わっていますが、これは char* 型の場合、代入される文字列が文字列定数として取り扱われるため、h[2*t+1]='o' として、その内容を変更しようとするとメモリのアクセスエラーとなってプログラムが強制終了してしまうからです。
さらに余白を作る
これらの変更を先程作った余白に詰め込んでいくのですが、捻出した 23 文字分の余白では足りませんでした(main 関数の引数追加で 13 文字使用、t=q; で 4 文字使用、h[2*t+1]='o'; にて 13 文字使用で計 30 文字使用← 7 文字余白が足りない!)。
そこで、さらに削れる部分はないかと探します。幸い、変数 m のイニシャライザは gcc の場合無くても大丈夫なようですのでこれを削除します(規格的にも大丈夫だったような気がすしたので、今しがた JIS X3010 をざっと見てみたのですが…残念ながらそのような記述は見当たりませんでした。なので現時点では「大丈夫だ!」とは言えない状況です)。
m[90]={0}, // これを
m[90], // こうする。(4 文字削減)
その他の部分としては、while での条件判断部分にて m[v]!=t と書かれている場所があったので、これを m[v]-t に変更します。m[v]==t であれば、m[v]-t は 0 となり、C 言語的には false になりますし、m[v]!=t であれば、m[v]-t は 0 以外の値となりますので、C 言語的には true となります。
while(m[v]!=t); // これを
while(m[v]-t); // こうする。(1 文字削減)
他にも、駒の表示部分で &h[m[p]*2] と書かれている部分を h+m[p]*2 に変更しました。
printf("%.2s",&h[m[p]*2]); // これを
printf("%.2s",h+m[p]*2); // こうする(2 文字削除)
最後は scanf のところのカンマ式全体を囲んでいた括弧を外しました。
t-2?(scanf("%d %d",&p,&i),p+=i*9):++p; // これを
t-2?scanf("%d %d",&p,&i),p+=i*9:++p; // こうする(2 文字削除)
こうして得られた 9 文字分の余白を使って変更を反映していきますが、成り行き上 for キーワードの途中でどうしても改行しなければならない部分が出てきてしまいました。ここは継続行の機能を使って乗り切ります:
// 行末のバックスラッシュにて継続行を作ることができ、
// こんな風に for キーワードを複数行に分割できます。
f\
or
継続行というと、複数行からなる define マクロでしか使いませんが、こんな風に使うこともできる…という例です。
余談ですが、私自身は継続行という考え方を(確か) FORTRAN を勉強している時に知った気がします。なんにせよ、今となってはあまり使わない記述方法のような気もします。
最終版
これらを全て反映させたのが以下のコードとなります(先手後手対応版):
int printf(const char*,...);int scanf(const char*,...);int p,t,a,d,c,v,i,m[90]
,s,r[]={-10,-9,-8,-1,1,8,9,10};char h[]=" - x x\n";void k(){if(m[p]==0)for(i=0
;i<8;i++){for(c=0,v=p+r[i];m[v]==3-t;v+=r[i])c++;if(c&&m[v]==t){a+=c;v=p;if(d)
do m[v]=t,v+=r[i];while(m[v]-t);}}}int main(int q,char**z){t=q;h[2*t+1]='o';f\
or(i=1,m[41]=m[49]=2;i<10;m[i++*9]=3)m[40]=m[50]=s=1;for(;;a=d=0){for(p=9;p<82
;++p)k(),printf("%.2s",h+m[p]*2);if(a)for(d=a=s=p=8;a==8;k())t-2?scanf("%d %d"
,&p,&i),p+=i*9:++p;else if(s)s=0,printf("pass");else break;t=3-t;}return 0;}
きっちり 79x7 行に収まりました (^^)v
リファクタリング版(および Mini-Max のサンプル実装追加版)
これだけでは何なので、リファクタリング版を以下に示します。基本的な構造は 7 行版と同じですが、盤面情報を格納する変数 gBoard を std::vector に変更しています。これは、盤面の情報を簡単にコピーできるようにするためです(高コストとなりますが、AI ルーチンで盤面情報を簡単に取り扱えるようにするためです)。
盤面上の (x,y) にあるマス目の情報は indexOf マクロを用いて gBoard[indexOf(x,y)] にてアクセスできます。また、相手の色を得るマクロとして opponent というものを定義しています。
新たに追加した関数のうち、bool canPut(vector& inBoard,int inColor) は、引数として与えられた盤面に対し、inColor で示される色の駒が置くことができるかどうかを確認します。例えば、canPut(gBoard,kBlack) が false を返したら、現在の盤面に対し、黒は置く場所がないことを意味します(なので、黒はパスとなります)。
human と com という関数も追加された関数のひとつですが、これらはそれぞれゲーム中における自分の駒の色を引数としてとり、どこかに駒を打った場合は true を返します(パスする場合は false を返します)。
com 関数から呼ばれる関数として think 関数があります。これが AI ルーチンの本体です。参考として、自分のコマ数を評価関数とする min-max 法を用いた AI ルーチンを搭載しておきました(が、弱いです)。
think 関数を差し替えることにより、独自の思考ルーチンを実装可能ですので、興味のある人は改造してみて下さい。
// compile: g++ -std=c++1z othello_MinMax.cpp
#include <stdio.h>
#include <vector>
using namespace std;
#define opponent(inTurn) (inTurn==kBlack ? kWhite : kBlack)
#define indexOf(x,y) ((x)+(y)*9)
enum { kInvalid=-1,kEmpty=0,kBlack=1,kWhite=2 };
vector<int> gBoard((8+1)*(1+8+1)); // size is 90.
int check(vector<int>& ioBoard,int inColor,int inTargetIndex,bool inTurnOver) {
if(ioBoard[inTargetIndex]!=kEmpty) { return 0; }
const int opponentColor=opponent(inColor);
int numOfTurnedOver=0;
const int kDir[]={-10,-9,-8,-1,1,8,9,10}; // スキャン方向のオフセット値
for(int i=0; i<8;i++) {
const int dir=kDir[i];
int t,count=0;
for(t=inTargetIndex+dir; ioBoard[t]==opponentColor; t+=dir) { count++; }
if(count==0 || ioBoard[t]!=inColor) { continue; }
numOfTurnedOver += count;
if(inTurnOver==false) { continue; }
t=inTargetIndex; do { ioBoard[t]=inColor; t+=dir; } while(ioBoard[t]!=inColor);
}
return numOfTurnedOver;
}
bool canPut(vector<int>& inBoard,int inColor) {
for(int t=0; t<90; t++) {
if(check(inBoard,inColor,t,false)!=0) { return true; }
}
return false;
}
bool human(int inPlayerColor) {
if(canPut(gBoard,inPlayerColor)==false) { return false; }
int x,y;
do {
printf("player is '%c'. input x y: ",inPlayerColor==kBlack ? 'O' : 'X');
if(scanf("%d %d",&x,&y)!=2 || x<1 || 8<x || y<1 || 8<y) {
printf("sorry?\n"); continue;
}
} while(check(gBoard,inPlayerColor,indexOf(x,y),true)==0);
return true;
}
bool think(int inComputerColor);
bool com(int inComputerColor) {
return canPut(gBoard,inComputerColor)==false ? false : think(inComputerColor);
}
void initBoard() {
for(int i=0; i<90; i++) { gBoard[i]=kInvalid; }
for(int y=1; y<=8; y++) { for(int x=1; x<=8; x++) {gBoard[indexOf(x,y)]=kEmpty;} }
gBoard[indexOf(4,4)]=gBoard[indexOf(5,5)]=kBlack;
gBoard[indexOf(5,4)]=gBoard[indexOf(4,5)]=kWhite;
}
void display(vector<int>& inBoard) {
printf("\n 1 2 3 4 5 6 7 8\n");
for(int y=1; y<=8; y++,printf("\n")) {
printf(" %d",y);
for(int x=1; x<=8; x++) { printf(" %c","-OX\n"[inBoard[indexOf(x,y)]]); }
}
printf("\n");
}
int numOf(vector<int>& inBoard,int inColor) {
return count(inBoard.begin(),inBoard.end(),inColor);
}
void printResult(int inPlayerColor) {
puts("--- GAME OVER ---");
const int numOfHuman=numOf(gBoard,inPlayerColor);
const int numOfCom =numOf(gBoard,opponent(inPlayerColor));
printf("Player is %d, Computer is %d.\n",numOfHuman,numOfCom);
if(numOfHuman==numOfCom) {
puts("This game is even.");
} else {
printf("%s is a winner\n",numOfHuman>numOfCom ? "Player" : "Computer");
}
}
int getPlayerColor() {
int color;
do {
printf("Are you the first player? (yes=1,no=2):"); scanf("%d",&color);
} while(color!=kBlack && color!=kWhite);
return color;
}
int main() {
initBoard();
int playerColor=getPlayerColor(),computerColor=opponent(playerColor);
bool alreadyPassed=false;
const int kMaxTurn=60; // =8*8-4
for(int turn=kBlack,count=0; count<kMaxTurn; turn=opponent(turn),count++) {
display(gBoard);
if((turn==playerColor ? human(playerColor) : com(computerColor))==false) {
if( alreadyPassed ) { break; }
alreadyPassed=true; printf("pass\n");
} else {
alreadyPassed=false;
}
}
printResult(playerColor);
return 0;
}
// min-max 法(実際はネガマックス法だけど…)による思考ルーチン
#include <tuple>
tuple<int,int> bestMove(vector<int>& inBoard,
int inComputerColor,int inColor,int inDepth) {
int bestMovePos=-1, maxScore=INT_MIN, sign = inComputerColor==inColor ? +1 : -1;
for(int i=0; i<inBoard.size(); i++) {
if(check(inBoard,inColor,i,false)==0) { continue; }
vector<int> board=inBoard; board[i]=inColor;
int s;
if(inDepth==0) {
s=sign*numOf(board,inColor);
} else {
auto [t,pos]=bestMove(board,inComputerColor,opponent(inColor),inDepth-1);
s=t;
}
if(maxScore<s) { maxScore=s; bestMovePos=i; }
}
return { maxScore,bestMovePos };
}
bool think(int inComputerColor) {
const int kDepth=5;
auto [s,pos]=bestMove(gBoard,inComputerColor,inComputerColor,kDepth);
return check(gBoard,inComputerColor,pos,true);
}
#if 0
// 7 行オセロと同じ思考ルーチン版(左上からスキャンしていき、置ける所に置く版
bool think(int inComputerColor) {
for(int t=indexOf(1,1); t<=indexOf(8,8); t++) {
if(check(gBoard,inComputerColor,t,true)>0) { return true; }
}
return false;
}
#endif