boletales/junk.cpp

## gistfile1.md

      
    Raw
  

              gistfile1.md
            
          
    ヒット・アンド・ブローの貪欲な推測戦略について

第1回 深夜の真剣レポート60分一本勝負 「今週の学び」の作品です。
今日の昼頃天井眺めてたら思いついた。
1. ゲーム「ヒット・アンド・ブロー」の概要

ヒット・アンド・ブローは二人で遊ぶ数字当てゲームで、ルールは以下の通りである：

各プレイヤーは0~9の数字から3桁の順列（以下、「組」と呼ぶ）を選ぶ（123や846など。225のような重複のあるものはだめ）。
プレイヤーは各ターン、相手の選んだ組を一つ推測し、提示する。
相手の推測に対して、以下のような情報を返す：

ヒット（H）：数字も位置も合っているものの個数
ブロー（B）：数字は合っているが位置が違うものの個数
例：答えが123、推測が324の場合、1H1Bとなる。


少ないターン数で相手の選んだ組を当てた（3H0Bを出した）方が勝ち。
自分の「答え」としてわかりやすい組を選んでしまうとすごい勢いで負けるらしい。

2. 今日思いついた戦略

方針：各ターンの情報量を貪欲に最大化する。先のことは考えない。
相手が組を完全にランダムに選んでくるとしたら（←非常に強い仮定。大概は「探られにくい」組を選ぶので、偏る。）、各回の推測で得られる情報量は計算可能である。
ある推測に対してあるヒントを得た際、そこまでのヒントからあり得る組が残りn個になったとすると、確定までに必要な情報量は残りlog_2(n) bitである。この「残り必要な情報量」の期待値を最小化するように推測をすることにする。
具体的には、推測の候補（現時点であり得る組すべて）について、それを提示したときの返答として0H0B, 0H1B, 0H2B, ..., 3H0B を得たときの残りの候補数を計算し、そこから各推測候補に対して「残り必要な情報量」の期待値を計算する。3桁のヒット・アンド・ブローでは高々720通りの候補しかないため、n^2オーダーの計算は十分許容できる。
3. 実例

以上のアルゴリズムを愚直に実装したので、いくつかの数字について推測の実例を置いておく。なお、メタ戦法対策の観点からは、期待値が同じ候補の中からランダムに選ぶことが望ましそうであるが、ここでは戦略の振る舞いを理解するために辞書順最小の候補を選ぶことにした。
自分の選択?> 8 2 5
提示した質問> 0 1 2
答え: 0H1B
残りの候補数: 252

提示した質問> 1 3 4
答え: 0H0B
残りの候補数: 80

提示した質問> 5 0 6
答え: 0H1B
残りの候補数: 21

提示した質問> 7 2 5
答え: 2H0B
残りの候補数: 2

提示した質問> 8 2 5
答え: 3H0B
残りの候補数: 1

自分の選択?> 3 7 0
提示した質問> 0 1 2
答え: 0H1B
残りの候補数: 252

提示した質問> 1 3 4
答え: 0H1B
残りの候補数: 75

提示した質問> 3 5 0
答え: 2H0B
残りの候補数: 5

提示した質問> 3 6 0
答え: 2H0B
残りの候補数: 3

提示した質問> 3 7 0
答え: 3H0B
残りの候補数: 1

自分の選択?> 2 1 9
提示した質問> 0 1 2
答え: 1H1B
残りの候補数: 42

提示した質問> 0 2 3
答え: 0H1B
残りの候補数: 18

提示した質問> 2 1 4
答え: 2H0B
残りの候補数: 5

提示した質問> 2 1 5
答え: 2H0B
残りの候補数: 4

提示した質問> 2 1 6
答え: 2H0B
残りの候補数: 3

提示した質問> 2 1 7
答え: 2H0B
残りの候補数: 2

提示した質問> 2 1 8
答え: 2H0B
残りの候補数: 1

提示した質問> 2 1 9
答え: 3H0B
残りの候補数: 1

三つ目の例は最も手数のかかる組を選んだ。この場合、分の悪い推測をしているように見える……。
4. 考察

すべての組に対して何手かかるか計算したところ、平均5.15手、最悪8手であることがわかった。これは実際高速である。なお、筆者が観測した事例によれば、本当にヒットアンドブローに勝ちたいなら、機械に推測させるより先に機械に数字を生成させるところからはじめたほうがよい。
5. 期限後追記① 答えとしてはあり得ない組を推測として出す

2 1 9に対して分の悪い推測をしていたのは、相手の答えとしてあり得ない組（上の例では7 8 9など）を推測の候補から省いていたからだった。すべての組を推測の候補に含めると、平均5.26手、最悪7手となって、平均的な成績は悪化した。なんで……
なお、この場合の2 1 9に対する推測は、以下の流れとなった：
自分の選択?> 2 1 9
提示した質問> 0 1 2
答え: 1H1B
残りの候補数: 42

提示した質問> 0 3 4
答え: 0H0B
残りの候補数: 10

提示した質問> 1 5 6
答え: 0H1B
残りの候補数: 3

提示した質問> 0 7 8
答え: 0H0B
残りの候補数: 1

提示した質問> 2 1 9
答え: 3H0B
残りの候補数: 1

6. 期限後追記② 3H0Bでの確定をより良いものとして評価する

何らかのヒントを受けて相手の選んだ組が確定したとき、3H0Bとそれ以外では最終的なターン数が1異なる。上の例から720通りの絞り込みに平均5手程度要していることを考えると、一手あたりおおよそ2bit程度の情報量を得ていることになる。
そのため、3H0Bが出る場合の「推測に必要な残り情報量」を-2bitとして計算するようコードを改変したところ、平均5.02手、最悪7手となり、成績が改善した。
必要手数が最大であった例について、推測の流れは以下の通りであった：
自分の選択?> 3 2 9
提示した質問> 0 1 2
答え: 0H1B
残りの候補数: 252

提示した質問> 1 3 4
答え: 0H1B
残りの候補数: 75

提示した質問> 3 5 0
答え: 1H0B
残りの候補数: 16

提示した質問> 6 4 0
答え: 0H0B
残りの候補数: 6

提示した質問> 3 2 7
答え: 2H0B
残りの候補数: 2

提示した質問> 3 2 8
答え: 2H0B
残りの候補数: 1

提示した質問> 3 2 9
答え: 3H0B
残りの候補数: 1


## junk.cpp
#include <vector>
#include <iostream>
#include <tuple>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

using Nums = tuple<int,int,int>;
using HB   = tuple<int,int>;

HB hitblow(Nums answer, Nums query){
    vector<int> ans_v = {get<0>(answer), get<1>(answer), get<2>(answer)};
    vector<int> que_v = {get<0>(query) , get<1>(query) , get<2>(query)};

    int hit = 0;
    int blow = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if(ans_v[i] == que_v[j]){
                if(i == j){
                    hit = hit + 1;
                }else
                {
                    blow = blow + 1;
                }
            }
        }
    }
    return tuple(hit, blow);
}

vector<Nums> get_possible_all(){
  vector<Nums> possible_all;
  int count = 0;
  for (int x = 0; x <= 9; x++){
      for (int y = 0; y <= 9; y++){
          for (int z = 0; z <= 9; z++){
              if(x != y && y != z && z != x){
                  //cout << x << y << z << "\n";
                  possible_all.push_back(tuple(x,y,z));
                  //count = count + 1;
              }
          }
      }
  }
  return possible_all;
}

vector<tuple<double, Nums>> getGuesses(vector<Nums> possible_all, vector<Nums> possible_enemy){
  vector<tuple<double, Nums>> guesses = vector<tuple<double, Nums>>();

  // 高速化：初手はなに投げても
  if(possible_enemy.size() == possible_all.size()){
    auto query = possible_enemy[0];

    map<HB, int> hbcount = map<HB,int>();
    for (auto &&posans : possible_enemy){
        auto hb = hitblow(posans, query);
        if(hbcount.count(hb) == 0){
            hbcount[hb] = 1;
        }else{
            hbcount[hb] += 1;
        }
    }

    double heikin_bits = 0;
    for(auto &&hbs : hbcount){
        int count = hbs.second;
        double possibility = ((double)count)/((double)possible_enemy.size());
        double bits = log2((double) count);
        heikin_bits += possibility * bits;
    }

    for(auto &&posans : possible_enemy){
        guesses.push_back(tuple(heikin_bits, posans));
    }
    return guesses;
  }
  // 高速化ここまで

  // 確定してたら終わり
  if(possible_enemy.size() == 1){
    guesses.push_back(tuple(0, possible_enemy[0]));
    return guesses;
  }

  for (auto &&query : possible_all)
  {
      // query に対して 0H0B, ... , 3H0B のそれぞれが返ってきたときの残り候補数を集計
      map<HB, int> hbcount = map<HB,int>();
      for (auto &&posans : possible_enemy){
          auto hb = hitblow(posans, query);
          if(hbcount.count(hb) == 0){
              hbcount[hb] = 1;
          }else{
              hbcount[hb] += 1;
          }
      }

      double heikin_bits = 0;
      for(auto &&hbs : hbcount){
          int count = hbs.second;
          double possibility = ((double)count)/((double)possible_enemy.size());
          double bits = log2((double) count);
          if(hbs.first == tuple(3,0)){ // 3H0Bのときだけ「残り必要情報量」を-2bit
            bits -= 2;
          }
          heikin_bits += possibility * bits;
      }

      guesses.push_back(tuple(heikin_bits, query));
  }
  sort(guesses.begin(), guesses.end());

  return guesses;
}

vector<Nums> narrow_down(vector<Nums> possible_enemy, Nums query, HB answer){
    vector<Nums> possible_new = vector<Nums>();
    for (auto &&posans : possible_enemy)
    {
        auto hb = hitblow(posans, query);
        if(hb == answer){
            possible_new.push_back(posans);
        }
    }
    return possible_new;
}

int autoplay(Nums answer, bool output = true){
  vector<Nums> possible_all = get_possible_all();
  auto possible_enemy = possible_all;
  int turn = 0;
  while(true){
    turn++;
    auto guesses = getGuesses(possible_all, possible_enemy);
    auto query = get<1>(guesses[0]);
    auto hb = hitblow(answer, query);
    possible_enemy = narrow_down(possible_enemy, query, hb);
    if(output){
      /*for (int i = 0; i < min(5, (int)guesses.size()); i++)
      {
        Nums query = get<1>(guesses[i]);
        cout << "候補" << i + 1 << ": " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << " " << get<0>(guesses[i]) << "bits \n";
      }*/
      cout << "提示した質問> " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << "\n";
      cout << "答え: " << get<0>(hb) << "H" << get<1>(hb) << "B\n";
      cout << "残りの候補数: " << possible_enemy.size() << "\n";
      cout << "\n";

      // char x; cin >> x;
    }
    if(get<0>(hb) == 3){
      break;
    }
  }
  return turn;
}

int interactive(){

    vector<Nums> possible_all = get_possible_all();
    vector<Nums> possible_enemy = possible_all;

    while (true)
    {
        auto guesses = getGuesses(possible_all, possible_enemy);
        for (int i = 0; i < min(5, (int)guesses.size()); i++)
        {
            Nums query = get<1>(guesses[i]);
            cout << "候補" << i + 1 << ": " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << " " << get<0>(guesses[i]) << "bits \n";
        }
        // 質問と絞り込み
        {
            cout << "提示した質問?>";
            int x, y, z;
            cin >> x >> y >> z;

            cout << "答え?(1H2Bなら「1 2」と入力)>";
            int h, b;
            cin >> h >> b;

            possible_enemy = narrow_down(possible_enemy, tuple(x,y,z), tuple(h,b));
        }
    }
    return 0;
}

int main(){
  interactive();

  /*
  cout << "自分の選択?> ";
  int x, y, z;
  cin >> x >> y >> z;
  autoplay(tuple(x,y,z));
  */

  /*
  auto possible_all = get_possible_all();
  double sum = 0;
  for(auto &&ans: possible_all){
    cout << get<0>(ans) << get<1>(ans) << get<2>(ans) << " :";
    int turn = autoplay(ans, false);
    sum += turn;
    cout << turn << "\n";
  }

  cout << "平均: " << sum / ((double)possible_all.size()) << "手\n";
  */
  return 0;
}
	#include <vector>
	#include <iostream>
	#include <tuple>
	#include <map>
	#include <cmath>
	#include <algorithm>

	using namespace std;

	using Nums = tuple<int,int,int>;
	using HB = tuple<int,int>;

	HB hitblow(Nums answer, Nums query){
	vector<int> ans_v = {get<0>(answer), get<1>(answer), get<2>(answer)};
	vector<int> que_v = {get<0>(query) , get<1>(query) , get<2>(query)};

	int hit = 0;
	int blow = 0;
	for (int i = 0; i < 3; i++)
	{
	for (int j = 0; j < 3; j++)
	{
	if(ans_v[i] == que_v[j]){
	if(i == j){
	hit = hit + 1;
	}else
	{
	blow = blow + 1;
	}
	}
	}
	}
	return tuple(hit, blow);
	}

	vector<Nums> get_possible_all(){
	vector<Nums> possible_all;
	int count = 0;
	for (int x = 0; x <= 9; x++){
	for (int y = 0; y <= 9; y++){
	for (int z = 0; z <= 9; z++){
	if(x != y && y != z && z != x){
	//cout << x << y << z << "\n";
	possible_all.push_back(tuple(x,y,z));
	//count = count + 1;
	}
	}
	}
	}
	return possible_all;
	}

	vector<tuple<double, Nums>> getGuesses(vector<Nums> possible_all, vector<Nums> possible_enemy){
	vector<tuple<double, Nums>> guesses = vector<tuple<double, Nums>>();

	// 高速化：初手はなに投げても
	if(possible_enemy.size() == possible_all.size()){
	auto query = possible_enemy[0];

	map<HB, int> hbcount = map<HB,int>();
	for (auto &&posans : possible_enemy){
	auto hb = hitblow(posans, query);
	if(hbcount.count(hb) == 0){
	hbcount[hb] = 1;
	}else{
	hbcount[hb] += 1;
	}
	}

	double heikin_bits = 0;
	for(auto &&hbs : hbcount){
	int count = hbs.second;
	double possibility = ((double)count)/((double)possible_enemy.size());
	double bits = log2((double) count);
	heikin_bits += possibility * bits;
	}

	for(auto &&posans : possible_enemy){
	guesses.push_back(tuple(heikin_bits, posans));
	}
	return guesses;
	}
	// 高速化ここまで

	// 確定してたら終わり
	if(possible_enemy.size() == 1){
	guesses.push_back(tuple(0, possible_enemy[0]));
	return guesses;
	}

	for (auto &&query : possible_all)
	{
	// query に対して 0H0B, ... , 3H0B のそれぞれが返ってきたときの残り候補数を集計
	map<HB, int> hbcount = map<HB,int>();
	for (auto &&posans : possible_enemy){
	auto hb = hitblow(posans, query);
	if(hbcount.count(hb) == 0){
	hbcount[hb] = 1;
	}else{
	hbcount[hb] += 1;
	}
	}

	double heikin_bits = 0;
	for(auto &&hbs : hbcount){
	int count = hbs.second;
	double possibility = ((double)count)/((double)possible_enemy.size());
	double bits = log2((double) count);
	if(hbs.first == tuple(3,0)){ // 3H0Bのときだけ「残り必要情報量」を-2bit
	bits -= 2;
	}
	heikin_bits += possibility * bits;
	}

	guesses.push_back(tuple(heikin_bits, query));
	}
	sort(guesses.begin(), guesses.end());

	return guesses;
	}

	vector<Nums> narrow_down(vector<Nums> possible_enemy, Nums query, HB answer){
	vector<Nums> possible_new = vector<Nums>();
	for (auto &&posans : possible_enemy)
	{
	auto hb = hitblow(posans, query);
	if(hb == answer){
	possible_new.push_back(posans);
	}
	}
	return possible_new;
	}

	int autoplay(Nums answer, bool output = true){
	vector<Nums> possible_all = get_possible_all();
	auto possible_enemy = possible_all;
	int turn = 0;
	while(true){
	turn++;
	auto guesses = getGuesses(possible_all, possible_enemy);
	auto query = get<1>(guesses[0]);
	auto hb = hitblow(answer, query);
	possible_enemy = narrow_down(possible_enemy, query, hb);
	if(output){
	/*for (int i = 0; i < min(5, (int)guesses.size()); i++)
	{
	Nums query = get<1>(guesses[i]);
	cout << "候補" << i + 1 << ": " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << " " << get<0>(guesses[i]) << "bits \n";
	}*/
	cout << "提示した質問> " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << "\n";
	cout << "答え: " << get<0>(hb) << "H" << get<1>(hb) << "B\n";
	cout << "残りの候補数: " << possible_enemy.size() << "\n";
	cout << "\n";

	// char x; cin >> x;
	}
	if(get<0>(hb) == 3){
	break;
	}
	}
	return turn;
	}

	int interactive(){

	vector<Nums> possible_all = get_possible_all();
	vector<Nums> possible_enemy = possible_all;

	while (true)
	{
	auto guesses = getGuesses(possible_all, possible_enemy);
	for (int i = 0; i < min(5, (int)guesses.size()); i++)
	{
	Nums query = get<1>(guesses[i]);
	cout << "候補" << i + 1 << ": " << get<0>(query) << " " << get<1>(query) << " " << get<2>(query) << " " << get<0>(guesses[i]) << "bits \n";
	}
	// 質問と絞り込み
	{
	cout << "提示した質問?>";
	int x, y, z;
	cin >> x >> y >> z;

	cout << "答え?(1H2Bなら「1 2」と入力)>";
	int h, b;
	cin >> h >> b;

	possible_enemy = narrow_down(possible_enemy, tuple(x,y,z), tuple(h,b));
	}
	}
	return 0;
	}

	int main(){
	interactive();

	/*
	cout << "自分の選択?> ";
	int x, y, z;
	cin >> x >> y >> z;
	autoplay(tuple(x,y,z));
	*/

	/*
	auto possible_all = get_possible_all();
	double sum = 0;
	for(auto &&ans: possible_all){
	cout << get<0>(ans) << get<1>(ans) << get<2>(ans) << " :";
	int turn = autoplay(ans, false);
	sum += turn;
	cout << turn << "\n";
	}

	cout << "平均: " << sum / ((double)possible_all.size()) << "手\n";
	*/
	return 0;
	}