ジャンケンプログラムについての考察ネタです

今回はアルゴリズム…プログラムのアイデア紹介です。

2進数とビット演算の活用ネタで、ビット演算の『 | 』(ビットごとのOR) の活用事例にもなっています。

お題は「ジャンケン プログラム」

ネット検索すると、最初は if else 文で記述が面倒な条件判定をしているサンプルが提示され、それを二次元配列にすると素敵、といった記事がいくつか発見できるかと思います。 ですがその記事はジャンケンプログラムを作ることがテーマではなく、『if else の記述が二次元配列で簡単になる』という多次元配列の基本活用テクニックを紹介するための記事になっている、という印象です。
つまり、ifelse (又は配列)で判定する仕様では、複数人ジャンケンに対応するものを作るのがとても大変…場合によっては不可能、というものなのです。 （参加人数が毎回ランダムは不可能）

今回の記事では、まず2人対戦のif elseタイプを二次元配列にするネタから紹介し、それを複数人にする時の大変さ（というか無理ゲーさ）を説明します。その後、違う視点で複数人（2人以上、10人でも50人でも対応可）でジャンケンするプログラムを考察し、その時にビット演算を使うアイデアの紹介をしています。

2人で対戦するタイプ if else版

function zyanken_type_if(p){
var c=Math.floor(Math.random()*3),
h=['G','C','P'],x=h[p],y=h[c],r='プレイヤーの';
if(x==='G'){ //プレイヤーがグーの時
 if(y==='C'){r+='勝ち';}
 else if(y==='P'){r+='負け';}
 else{r='引き分け';}
}
else if(x==='C'){ //プレイヤーがチョキの時
 if(y==='P'){r+='勝ち';}
 else if(y==='G'){r+='負け';}
 else{r='引き分け';}
}
else{ //プレイヤーがパーの時
 if(y==='G'){r+='勝ち';}
 else if(y==='C'){r+='負け';}
 else{r='引き分け';}
}
//結果の r をinnerHTML変更等で画面表示する処理は省略
}

javascript版のジャンケンプログラムの例。
プレイヤーが入力する引数値は、グーの時は0、チョキの時は1、パーの時は2、とします。
プログラム中の 変数 x がプレイヤーの手(G or C or P)、変数 y がPCの手です。
※結果を画面に出力する処理は本題ではないので省略しています。

まずはこんな感じで、プレイヤーの手とコンピュータの手をif else文で判定するという教科書通りの例が紹介されたりします。
例では、コンピュータの手は、0から2の整数をランダムに作り、変数 c に入れています。その値をインデックスとして配列 h の文字列を取得して判定に使っています。

プログラムとしては、わざわざ文字列で比較しなくても数値のままでいいと思うのですが、サンプルとして分かりやすくするためにそういう例が多いのだろうと思ったりします。

zyanken_type_ifの動作テスト

ジャンケンの手を選んでください。
グー チョキ パー

ここに結果を表示します

if elseの条件部分を文字列ではなく数値にした例

function zyanken_type_if_n(p){
var c=Math.floor(Math.random()*3),k;
if(p===0){
 if(c===1){k=0;}
 else if(c===2){k=1;}
 else{k=2;}
}
else if(p===1){
 if(c===2){k=0;}
 else if(c===0){k=1;}
 else{k=2;}
}
else{
 if(c===0){k=0;}
 else if(c===1){k=1;}
 else{k=2;}
}
//後は['勝ち','負け','引き分け'][k]で
//結果の文字列作成し画面表示する等
}

文字列比較ではなく数値比較したif elseのサンプルを作って眺めてみます。
また、判定数値を表にすると、そのまま二次元配列のインデックス番号になる、というアイデアが浮かびやすいかと思います。

この複雑に見えるif elseが二次元配列を使うと簡単に

という見出しで紹介されていたりします。

function zyanken_type_ar(p){
var c=Math.floor(Math.random()*3),r,
k=[
['引き分け','あなたの勝ち','あなたの負け'],
['あなたの負け','引き分け','あなたの勝ち'],
['あなたの勝ち','あなたの負け','引き分け']
];
r=k[p][c]
//結果の r をinnerHTML変更等で画面表示する処理は省略
}

要するに、文字列判定ではなく数値判定時のp値やc値をそのまま二次元配列の引数にしている、というアイデアです。

zyanken_type_arの動作テスト

ジャンケンの手を選んでください。
グー チョキ パー

ここに結果を表示します

if else/二次元配列タイプのジャンケンプログラムのアルゴリズム

複数人ジャンケンの考察の前に、2人対戦のプログラムのアイデアとなっている if else のツリーを考えてみます。
人をA、コンピュータをBとして書くと…

Aの手が[0(G)]の場合、
　Bの手が[0(G)]なら、引き分け
　Bの手が[1(C)]なら、Aの勝ち
　Bの手が[2(P)]なら、Bの勝ち
Aの手が[1(C)]の場合、
　Bの手が[0(G)]なら、Bの勝ち
　Bの手が[1(C)]なら、引き分け
　Bの手が[2(P)]なら、Aの勝ち
Aの手が[2(P)]の場合、
　Bの手が[0(G)]なら、Aの勝ち
　Bの手が[1(C)]なら、Bの勝ち
　Bの手が[2(P)]なら、引き分け

このアイデアのままで、3人対戦を考えてみると、こんなifelseツリーに…
Aの手が[0(G)]の場合、
　Bの手が[0(G)]の場合、
　　 Cの手が[0(G)]なら、引き分け
　　 Cの手が[1(C)]なら、AとBの勝ち
　　 Cの手が[2(P)]なら、Cの勝ち
　Bの手が[1(C)]の場合、
　　 Cの手が[0(G)]なら、AとCの勝ち
　　 Cの手が[1(C)]なら、Aの勝ち
　　 Cの手が[2(P)]なら、引き分け
　Bの手が[2(P)]の場合、
　　 Cの手が[0(G)]なら、Bの勝ち
　　 Cの手が[1(C)]なら、引き分け
　　 Cの手が[2(P)]なら、BとCの勝ち
Aの手が[1(C)]の場合、
　Bの手が[0(G)]の場合、
　　 Cの手が[0(G)]なら、BとCの勝ち
　　 Cの手が[1(C)]なら、Bの勝ち
　　 Cの手が[2(P)]なら、引き分け
　Bの手が[1(C)]の場合、
　　 Cの手が[0(G)]なら、Cの勝ち
　　 Cの手が[1(C)]なら、引き分け
【以下略】

プログラムの授業などで先生が2人対戦ジャンケンプログラムのみを教えて、3人、5人で対戦するプログラムを作れ、などと課題を出したりする場合はかなり意地悪かもしれません。

3人でジャンケンする結果を表にしてみました

G=0 C=1 P=2 としています。

表を縦にすると長すぎるのでAの数値で3分割して横に配置してます。数値の並びが3桁の3進数になっています。
10進数にすると0から26まで手の組み合わせパターンがあることがわかります。

つまり if else/多次元配列タイプで作ると、27個の判定結果をifelse又は多次元配列（3人は3次元）で書かなければいけない、ということです。

4人では 3*3*3*3=81、5人だと 3*3*3*3*3=243個なので ifelse を多次元配列で簡単に…などと言っている場合ではなくなってしまいます。
そして、対戦人数が変動する場合は基本アイデアの if else 判定で作るのは不可能です。なぜなら対戦者が何人いるかわからないので総当たりのifelse文や多次元配列データが用意できないからです。
つまり ifelse タイプの2人対戦ジャンケンプログラムは ジャンケンプログラムを作りたいという目的からみれば、不完全、ということなのです。

視点を変えてジャンケンのルールで全判定結果を表にしてみます

プレイヤーの数は不明として数を限定せず、勝敗条件を表にしてみます。「勝ち」「負け」「引き分け」はどう決まるでしょうか？ 次の表では、あり(誰かがその手を出した)場合を1、なし(誰も出してない)を0としています。

ジャンケンのルールでは、出された手が2種類の場合のみ勝ち負けが決まり、3種類の手が出るか、全員同じ手の時は引き分けです。

出てる手のありなしのみに注目すると、このコラムでずっと紹介してきた2進数になりました。
ジャンケンの手は3種類なので3桁の2進数であり、しかも0（GCPのどの手も出ない）はないので、結果のパターン数は7つになります。

なので、何人プレイヤーがいたとしても、それぞれの手から、判定用の変数になんらかの処理をすることで、この表の2進数の値、すなわち10進数では 1～7 のどれかになれば、勝敗判定ができる、ということが判明しました。

ここで活用するのが、ビット演算の | （ビットごとのOR）です。

OR ってなんやねん

ANDの時のように書いてみますと、
OR演算子は以下のような計算になります。
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

両方が0の時以外は1になるというものです。
ビットごとのOR演算のポイントは、あるビットが OR で 1 になってしまったら、OR ではもう二度と 0 には戻せない、という 銀河鉄道999を40代のおじさんたちが青春の幻影を泣きながら思い出すような計算なのです。

ビットごとのORは[|]記号を使います。
0|2=2、2|4=6、6|1=7、という感じです。
10進数で書くと意味不明な感じですが、2進数にすると
000|010=010、010|100=110、110|001=111、となり、
なんとなく雰囲気は伝わるかと思います。

ビットごとにORを順に計算してみる

3桁の2進数の 000 に 2進数1桁目のビットマスク、すなわち001でビットごとのORを計算してみます。
000 (結果判定値)
001 (グー、がでてるよ～)
↓ビットごとにOR（※0と0の時は0、それ以外は1）すると…
001 （ 000 | 001 = 001 になった）
次に、その数値に2桁目のビットマスク(010)でビットごとのORを計算してみます。
001 (結果判定値)
010 (チョキ、もでてます)
↓ビットごとにORすると…
011 （ 001 | 010 = 011 になった）
最後に、この数値に3桁目のビットマスク(100)でビットごとのORを計算してみます。
011 (結果判定値)
100 (パー、がでました)
↓ビットごとにORすると…
111 （ 011 | 100 = 111 になった）→ 10進数の7
これ以降は、3桁の2進数の場合、どのビットマスク(001 , 010 , 100)でORしても、結果は 111 で 7 のままです。
これはすなわち、GCPで引きわけ、ということです。

Gの時は001=1(10進数)、Cの時は010=2(10進数)、Pの時は100=4(10進数)でそれぞれ結果用の変数値と | (ビットごとのOR) してやれば、何人プレイヤーがいても、大量のifelse文を書かずに複数人ジャンケンの結果を判定する値を作ることができる、ということになります。(＝ジャンケンプログラムのアルゴリズム)

複数人ジャンケンのアルゴリズム

■複数人ジャンケンは、各プレイヤーが3種類のどれかの手を出す
■3種類の手がすべて出てる、又は全員が同じ手の時はあいこで引き分け
■2種類の手の場合は勝敗のある2人ジャンケンと同じ。

ということで、初期値を0とした判定用の変数 k に参加するプレイヤーの各手に対応するビットマスク値を順に、| 演算(ビットごとのOR)して、上記の表の判定値を作ります。

複数人ジャンケンのアルゴリズムのポイント

手を a とした場合、 k = k | (1<<a) 又は好みで k | = 1<<a というビット演算が複数人ジャンケンのアルゴリズムのメインアイデアとなります。
グー[a = 0]、チョキ[a = 1]、パー[a = 2] として、グー → k|=1<<0、チョキ → k|=1<<1、パー → k|=1<<2、という計算になります。そして、kの値が 7 になると、以降は、| 演算の結果が常に k=7 なので、プログラム時にはその値判定もしておくと無駄な計算をはぶけるかと思います。

javascriptでプログラムを書いてみると…

人間1人 対 コンピュータn人 でジャンケンする時の判定用の値 k を計算しているプログラム例

function zyanken_type_or(p,n){
var c=[],k=0,i,
x=['無','全員Gで引きわけ','全員Cで引きわけ',
'Gが勝ち','全員Pで引きわけ','Pが勝ち','Cが勝ち',
'GCPで引きわけ'];
k|=1<<p;//プレイヤーの手を[|演算]
for(i=0;i<n;i++){//pc n人分のループ
c[i]=Math.floor(Math.random()*3);//pcの手(0～2)
if(k!==7)k|=1<<c[i];//pcの手を[|演算]
}
//後はx[k]で結果の文字列作成し画面表示したり、
//配列cや引数pから個別の勝ち負けを画面表示したり…
}

この関数では、引数pに人間プレイヤーの手の数値(0～2)、引数nに対戦するPCの人数を渡します。
初期値0のkに人間プレイヤーの手を[|演算]し、その後、n人のPCの手をランダムに作って配列cに入れ、kが7になってない場合のみPCの手を[|演算]します。後はkの値を配列xのインデックス番号にして結果を表示するなどになります。

zyanken_type_orの動作テスト

※このテストはx[k]の結果と手のみを表示しています。

対戦するコンピュータの数を選んでください。

ジャンケンの手を選んでください。
グー チョキ パー

ここに結果を表示します

勝ち負けを判定して表示してみたもの

function zyanken_type_or2(p,n){
var e=document.getElementById('op_wbc5_4'),
c=[],k=0,i,r='',w,s='',
x=['コンピュータ','グー','チョキ','グーで',
'パー','パーで','チョキで','グーチョキパー'];
s+='あなたの手['+['G','C','P'][p]+']<br>';
k|=1<<p;
for(i=0;i<n;i++){
c[i]=Math.floor(Math.random()*3);
if(k!==7)k|=1<<c[i];
s+='PC'+(i+1)+'の手['+['G','C','P'][c[i]]+'] ';
}
w=(k===3)?0:(k===5)?2:(k===6)?1:3;
if(w===3){r+='全員の手が'+x[k]+'で引き分け';}
else{
 if(p===w){r+='【プレイヤー】';}
 for(i=0;i<n;i++){if(c[i]===w){r+='【'+x[0]+(i+1)+'】';}}
 r+='が'+x[k]+'勝ち';
}
if(e)e.innerHTML=r+'<hr>'+s+'<br>(参考：k='+k+')';
}

zyanken_type_or2の動作テスト

対戦するコンピュータの数を選んでください。

ジャンケンの手を選んでください。
グー チョキ パー

ここに結果を表示します

ということで、複数人ジャンケンプログラムを作るアルゴリズムで | 演算を活用する例を紹介してみました

ジャンケンプログラムをweb検索すると、当然であるかのように2人対戦プログラムで、ほとんどがif elseで手を比較する形になっていて、それを二次元配列で簡単に、というオチになるものが多い印象です。なので真剣にジャンケンプログラムが作りたい…という人（がいるのかどうかは不明だけど）が複数人でも対応可能なジャンケンプログラムを作る参考（回答）になるように考察してみました。

また、ジャンケンプログラム（を作ってほしい）と聞いて、最初から複数人ジャンケンを想定するかどうかで考えたり作業したりの時間が変化するかと思いますのでいきなり検索する癖のある人は、多数意見と思っているgoogle検索上位に出てくる結果に惑わされてしまい、複数人を想定して考えると全く異なるアルゴリズムで作れるという視点（プログラムの判定条件）に気づかない場合があるかもしれません。

プログラムは同じ結果を出すためにいろんな方法（作り方）があるので、いろいろ視点を変えて最適な手法を考えるのが重要ポイントだと思ったりします。
ということで今回は「G vs G」「G vs C」「G vs P」「G vs P vs C」… の総当たり判定方法から、「Gが出てるか？Cが出てるか？Pが出てるか？」に視点変更することで人数無制限のジャンケンプログラムのアルゴリズムを作りました。
※ 20人、50人対戦なんてのは何回やっても結果はほぼ引き分けになってて、誰かが勝つのは奇跡的かと思ったりしました…

ついでに紹介するとアンケートフォームの複数選択状態を表現する数値を作る場合も|演算が使えます

以前のコラムで複数選択のあるアンケートで「1:映画=1」「2:音楽=2」「3:釣り=4」「4:パソコン=8」「5:車=16」という選択値のビットマスク値を加算して、選択状態を表す数値を作る、という紹介をした時には単純に、ビットマスク値を加算する形で紹介しました。
Ａさん → 選択肢1:映画 , 選択肢3:釣り → 00001 + 00100 → 2^0 + 2^2 = 1 + 4 = 5
これも、a = 00000 に a|=00001 で a = 00001 になり、さらに a|=00100 で a = 00101、結果、Ａさんの a = 5 という値を作ることができます。

複数人ジャンケンプログラムの場合もビットマスク値を加算する形でも作れますが、何も考えずに出た手の値から作ったビットマスク値を片っ端から加算するだけだと、判定結果の値が7を超えてしまう可能性があるので、値が7を超えないように判定文を入れることが必須となる点がポイントとなります。
ということで、今回の最適な手法は「|演算」ではないかと思い紹介してみました。