Seeed XIAO BLEの充電回路を使いこなす

最近、国内の各電子部品店でSeeed XIAO BLEという製品が取り扱われるようになりました。親指サイズのデバイスで、nRF52840というARM Cortex-M4 CPUを持ったマイコンモジュールで、Bluetooth 5.0に対応しています。もちろん技適も通っています。

末尾に"Sense"が付いたモデルと付いていないモデルの2種類があります。Sense付きは700円程度高くなりますが、6軸IMUとPDMマイクを搭載しているようです。それ以外は同じです。

さて、特記すべきことに、このデバイスにはBQ25101というTexas Instrument製のリチウムイオン電池充電コントローラーが付いています。そのため、適当なリチウムポリマー電池などを直結して、充電式のBluetoothデバイスなんかを簡単に開発することができます。なんというかすごい時代ですね。本当にIoTが個人レベルで作りやすくなったと感じます。

ハードウェア

回路全体

さて、一応Seeed wikiにこのマイコンボードの回路図は載っているのですが、非常に見にくくてわかりずらいです。そのうえ、現物との対応もあまりとれません。ということでいろいろひも解いてみました。

結論から言うと、回路は以下のようになっています（電源にかかわらない回路は省略しています）。

点線で書いた部分のみがこのボードの外の配線となります。ですので、バッテリーを基板の裏面にある「BAT+」「BAT-」端子に接続するだけです。裏面のSMD端子なのが少し不便ですが、まあそれはよいでしょう。

（Seeed wikiより引用）

ただし、回路図から見てわかるように、Seeed XIAO BLEに搭載されているのは充電コントローラーだけで、過放電保護回路は付いていません。電子工作で手に入るリチウムポリマー電池は保護回路付のものも多いですが、18650サイズのリチウムイオン電池など、保護回路が付いていないものはDW01/FS8205などの過充放電保護ICなどを組み込むとよいでしょう。詳しくはこちらの記事を参照してください。

ちなみに、Q1はなぜダイオードではなくFETを付けているのかと思う人もいるかもしれませんが、これはダイオードでの約0.6Vの損失をなくすためです。FETだとダイオードに比べてほとんど電圧降下しませんので、3.7Vのリチウムイオン電池で駆動する際も、3.3V以上の電圧をレギュレーターに供給できるようになります。

充電コントロール回路

さて、メインディッシュは充電コントローラーのBQ25101となります。 とはいっても、BQ25101はよくあるタイプの充電コントローラーで、電圧がある一定（約4.2V）になるまでは定電流充電を行い、そこから先は定電圧充電を行うタイプのものです。電池の温度制御（温度が高くなりすぎないように電流を抑える機能）もあるようですが、今回は殺されている（TS端子に温度センサではなくただの抵抗が取り付けられている）ので機能しません。

充電プロファイル（データシートより引用）

ISET端子は充電電流を決める端子で、その抵抗値により決まります。範囲は13.5kΩ（10mA）から0.54kΩ（250mA）です。このボードではR18に2.7kΩが付いているので、デフォルトで50mA流れます。また、マイコンからP0.13をLOW出力してあげればさらに2.7kΩが並列につながるため、充電電流が50mA増えて合計100mAを流すことができます。

~CHG端子は充電状態か否かを示す端子です。オープンドレイン端子となっていて、LOW（＝FET ON）で充電状態、Open（＝FET OFF）で充電完了状態を意味します。充電LEDがこの回路に付いているのでマイコンの制御なしにそのままLEDが機能しますが、マイコン側からP0.17の値を読み込むことで充電中か否かを判断することもできます。

さらに、R16とR17で分圧されたバッテリー電圧をアナログピンで読み込む回路も一緒に入っています。これによってバッテリー電圧をマイコンで知ることができます。もちろんこの回路を有効にするにはP0.14をLOW出力する必要があります。普段はこのポートを入力（ハイインピーダンス）にしておくことで、R16-R17の計1.5MΩを流れる非常に微量の電流（約2uA）ではありますが節電することができます。

なお、このマイコンボードではバッテリー電圧を測ることしかできないため、例えば負荷が大きく上下するような環境でこの充電回路を使用した場合、負荷が上がれば（＝電流が大きくなれば）バッテリーの内部抵抗での電圧降下が大きくなるためバッテリー電圧は下がり、その後負荷が下がったときにバッテリーの電圧は回復します。そのような場合は、バッテリー電圧しか見ていないと正しく電池の消耗状態を把握することができません。もっと厳密に電池残量を測るには、クーロンカウンタと呼ばれる電荷の移動量を監視するICが必要になってきますが、このボードにはそのようなものは無いため、外付けしない限りはあまり厳密な電池残量の把握はできません。電圧はあくまでも参考程度というものになります。

ソフトウェア

さて、充電回路がわかったところでソフトを作っていきましょう。今回はサンプルでBluetoothキーボードとして使えるデバイスを作っていきます。

Bluetooth 4.0から規格が制定され、もちろんこのSeeed XIAO BLEでも対応しているBLE（Bluetooth Low Energy）にはBattery Serviceというものがあり、ホスト側にバッテリー残量を知らせることができます。例えばWindows11だと、Battery Serviceに対応しているデバイスでは以下のように電池残量を示すアイコンが出てきて、極端にバッテリー残量が低下しているなどの場合は通知で警告してくるなどの機能があります。

このSeeed XIAO BLEはせっかくここまでの充電回路を持っているデバイスなので、このBattery Serviceを使いこなしていきましょう。

環境構築

さて、今回はArduinoで開発していきます。

Seeed Wikiにも書いてある通り、Arduinoの「追加のボードマネージャのURL」に "https://files.seeedstudio.com/arduino/package_seeeduino_boards_index.json" を追加して「Seeed nRF52 Boards」をインストールするのですが、ここで注意点があります。バージョン1.0.0をインストールしてください。デフォルトだと最新？の2.6.1？が出てきますが、ここで今回使うライブラリは1.0.0しか対応していないようなので、1.0.0を入れる必要があります。

あとは通常通りでOKです。ボード選択などを適宜して使える状態にすれば準備完了です。もしわからなくても、ググればそれなりに情報は出てくるはずです。

setupの実装

早速実装していきましょう。 Adafruitのライブラリを使用していきますが、特段ライブラリをインストールせずとも使えるはずです。

#include <bluefruit.h>

#define	PIN_HICHG	22
#define	PIN_INVCHG	23

BLEDis bledis;
BLEHidAdafruit blehid;
BLEBas blebas;

ヘッダーはこんな感じです。なぜかHICHG（100mA充電）端子のピンと~CHGのピンがヘッダファイルで定義されていないのでここで定義しておきます。

サービスは3つ使い、DIS (Device Information Service)、HID (Human Interface Service)、BAS (Battery Service)です。DISはデバイス情報を伝えるサービス、HIDはキーボード動作そのもののサービスです。

void setup() 
{
	setup_battery();

	Serial.begin(115200);

	setup_ble();
}

void setup_battery()
{
	// High speed charging (100mA)
	pinMode(PIN_HICHG, OUTPUT);
	digitalWrite(PIN_HICHG, LOW);

	pinMode(PIN_INVCHG, INPUT);
}

void setup_ble(void) 
{
	Bluefruit.autoConnLed(false);
	Bluefruit.begin();
	Bluefruit.setTxPower(4);  // Check bluefruit.h for supported values
	Bluefruit.setName("nRF52840 Keyboard");

	// Configure and Start Device Information Service
	bledis.setManufacturer("EH500_Kintarou");
	bledis.setModel("nRF52840");
	bledis.begin();

	blehid.begin();
	blebas.begin();

	// Advertising packet
	Bluefruit.Advertising.addFlags(BLE_GAP_ADV_FLAGS_LE_ONLY_GENERAL_DISC_MODE);
	Bluefruit.Advertising.addTxPower();
	Bluefruit.Advertising.addAppearance(BLE_APPEARANCE_HID_KEYBOARD);

	// Include BLE HID service
	Bluefruit.Advertising.addService(blehid);

	// Include BLE battery service
	Bluefruit.Advertising.addService(blebas);

	// There is enough room for the dev name in the advertising packet
	Bluefruit.Advertising.addName();

	Bluefruit.Advertising.restartOnDisconnect(true);
	Bluefruit.Advertising.setInterval(32, 244);  // in unit of 0.625 ms
	Bluefruit.Advertising.setFastTimeout(30);    // number of seconds in fast mode
	Bluefruit.Advertising.start(0);  // 0 = Don't stop advertising after n seconds
}

Setupルーチンはこんな感じでよいでしょう。まずは100mA充電を有効化し、その後にBLEのセットアップをします。各Serviceを起動して、最後はアドバタイジングの設定をすればOKです。

バッテリー残量

さて、先ほど出てきた問題です。loopルーチンを実装するにあたって、バッテリー残量をバッテリー電圧から推定しなければなりません。ということで、マイコンからバッテリー電圧を見たらどのように見えるのかを確認してみました。使用したバッテリーはaitendoで売っている300mAhのリチウムポリマー電池です。なお購入してから数年間経っているため、性能が落ちているかもしれませんがそこはご容赦ください。

まずは充電です。電池を過放電防止保護がかかるまですっからかんにしてからSeeed XIAO BLEの100mA設定で充電を開始しました。

1時間45分くらいかけて4.3Vくらいまで電圧が上がって、その先は定電圧モードになっています。4時間くらいのところで充電が終了してその拍子に少し電圧が下がっているのが見て取れます。ちなみに、これはこのマイコンボードのA/D変換で測った電圧で、4.3Vくらいまで上がっていますが、手元のテスターで測るとピッタリ4.2Vでした。抵抗の誤差とかなのかなという感じです。

続いて放電です。充電が終わってから過放電保護がかかるまで電子負荷装置で100mAで放電をしました。

放電はこんな感じです。4.1Vくらいからほとんど一定に電圧が下がっていき、3.6Vくらいからガクンと落ちています。

loopの実装

さて、こんな感じでどうでしょう。

#define BAT_AVERAGE_COUNT	16
#define BAT_AVERAGE_MASK	0x0F

void loop()
{
	loop_led();
	loop_battery();
}

void loop_led()
{
	digitalWrite(LED_RED, HIGH);
	digitalWrite(LED_GREEN, HIGH);

	uint32_t ms = millis();

	if(Bluefruit.connected()) {
		uint32_t interval = ms % 3000;
		digitalWrite(LED_BLUE, (interval < 100) ? LOW : HIGH);
	} else {
		uint32_t interval = ms % 2000;
		digitalWrite(LED_BLUE, (interval < 100 || (interval >= 200 && interval < 300)) ? LOW : HIGH);
	}
}

void loop_battery()
{
	static uint32_t lastMeasure = 0;
	static bool lastIsCharging = false;
	uint32_t ms = millis();
	bool isCharging = battery_isCharging();
	static uint16_t rawvalues[BAT_AVERAGE_COUNT];
	static uint8_t index = 0;
	static uint8_t count = 0;
	
	if(ms - lastMeasure > 3000) {
		if(lastIsCharging != isCharging) {	// 充電状態が変わったらリセット
			index = 0;
			count = 0;
		}

		pinMode(VBAT_ENABLE, OUTPUT);
		digitalWrite(VBAT_ENABLE, LOW);
		rawvalues[index] = (uint16_t)analogRead(PIN_VBAT);
		pinMode(VBAT_ENABLE, INPUT);

		index = (index + 1) & BAT_AVERAGE_MASK;
		count = min(count + 1, BAT_AVERAGE_COUNT);
		uint16_t rawtotal = 0;
		for(int i = 0; i < count; i++)
			rawtotal += rawvalues[i];
		
		double volt = (double)rawtotal / count / 1024 * 3.6 / 510 * 1510;	// 10bit, Vref=3.6V, 分圧比1000:510

		if(isCharging) {
			if(volt <= 3.78)
				blebas.notify(1);
			else if(volt <= 4.02)
				blebas.notify(3);
			else if(volt <= 4.25)
				blebas.notify((uint8_t)((volt - 4) * 140 / 5 + 0.5) * 5);	// 4.25Vで35%になるよう5%単位
			else
				blebas.notify(70);	// ここからは定電圧領域になるので電圧じゃほとんどわからない
		} else {
			if(volt <= 3.5)
				blebas.notify(1);
			else if(volt <= 3.62)
				blebas.notify(3);
			else if(volt <= 3.8)
				blebas.notify((uint8_t)(((volt - 3.62) * 277.78 + 5) / 5 + 0.5) * 5);	// 3.8Vで55%、3.62Vで5%
			else if(volt <= 4.1)
				blebas.notify((uint8_t)(((volt - 3.8) * 150 + 55) / 5 + 0.5) * 5);	// 4.1Vで100%、3.8Vで55%
			else
				blebas.notify(100);
		}

		lastMeasure = ms;
		lastIsCharging = isCharging;
	}
}

bool battery_isCharging()
{
	return digitalRead(PIN_INVCHG) == LOW;
}

バッテリーは上の測定結果をもとにパーセンテージを表示するようにしています。しかし、先述の通り電圧によるバッテリー残量測定は目安程度にしかなりませんし、とくに充電なんかは定電圧領域に入ると電圧で判別することはほとんどできなくなるので70%固定とかいう雑な実装をしています。もう少し頑張りたかったら経過時間なども考慮に入れてみるのもいいかもしれません。

また、充放電以外にも接続前は青色LEDが2回点滅、接続後は1回点滅にしたかったのでそういう処理も入っています。

これでだいたいSeeed XIAO BLEをリチウムポリマー電池で使う準備が整いました。やりたいことの実装へ移っていきましょう。

Wordleの判定アルゴリズム

 まずはこちらをご覧ください。

灰色だと答えにその文字は含まれないと言ったな？スマンあれは嘘だ。

解説

よくWordleでは以下のような説明がされます。

• 緑だとその文字がその場所で使われる
• 黄だとその文字が別の場所で使われる
• 灰だとその文字は使われていない
  

5文字すべてが異なる場合に限っては合っています。ただ、同じ文字が2個以上含まれる場合はそうとは言えなくなるようです。

上の例のように答えがsloshでdrillを入力した場合、箇条書きで書いたルールに従って判定するとになります。なぜなら、4文字目のlも5文字目のlもlであることには変わりなく、答えの2文字目とは異なる場所で使われているためです。でも実際に4文字目のlしか色が付きません。

一方で、答えがsloshでassetを入力した場合、となりました。どちらのsも色が付いています。これは、答えの単語にsが2回使われていることが影響していると考えられます。

crossやfloodを入力した結果を見ても明らかだと思います。この挙動は、「文字の場所」というよりかは「文字の入れ替え」を意識した挙動だと考えることができます。そのほうが人間にはより直感的に理解できますからね。そして、ゲームとしても同じ文字が2個以上含まれる単語を入れても「文字数」という情報を入手することができるということになります。

実装

さて、前回の記事などでもいろいろと解析してきましたが、そもそもの判定アルゴリズムが誤っていたのですから実装しなおさなければなりません。

まずはWordleの挙動と同じように色付けをするコードを実装してみます。

static WordHint MakeHint(string input, string target)
{
	var len = Math.Min(input.Length, target.Length);
	var assigned = new bool[len];

	var ret = new WordHint(input);

	// 緑を探す
	for(int i = 0; i < len; i++) {
		if(input[i] == target[i]) {
			assigned[i] = true;
			ret.Characters[i].Hint = HintState.ExactPosition;
		}
	}

	// 黄色を探す
	for(int i = 0; i < len; i++) {
		if(ret.Characters[i].Hint != HintState.ExactPosition) {
			for(int j = 0; j < len; j++) {
				if(!assigned[j] && input[i] == target[j]) {
					assigned[j] = true;
					ret.Characters[i].Hint = HintState.NotInPosition;
					break;
				}
			}
		}
	}

	return ret;
}

こんな感じでしょうか。「入れ替え」を前提にした処理をしなければならないため、二重ループにする必要があります。

つづいて、与えられた単語とWordleの判定結果からそれを満たす単語を返すメソッドを作っていきましょう。

public static IReadOnlySet<string> Nominate(IEnumerable<IWordHint> hints, IReadOnlySet<string> words)
{
	// 入力単語の文字ごとにグループを作る
	var chargroup = hints.SelectMany(p => p.Characters.Select((p, i) => (character: char.ToLower(p.Character), pos: i, hint: p.Hint)).GroupBy(p => p.character)).ToArray();
	foreach(var cg in chargroup) {
		var count = cg.Count();		// グループの要素数=入力単語でその文字が使われている回数
		var coloredcount = cg.Where(p => p.hint != HintState.NotContained).Count();	// グループのうち色が付いている文字数

		if(count > coloredcount) {  // この条件のとき、ちょうどcoloredcount回その文字が使われている語がヒットする
			var filtered = new SortedSet<string>();
			foreach(var w in words) {
				if(w.Where(p => p == cg.Key).Count() == coloredcount &&		// ちょうどcoloredcount回その文字が使われていて
				   cg.Where(p => p.hint == HintState.ExactPosition).All(p => w[p.pos] == p.character) &&    // 緑色がそこに使われていて
				   cg.Where(p => p.hint == HintState.NotInPosition).All(p => w[p.pos] != p.character))    // 黄色がそこに使われていない
					filtered.Add(w);						
			}
			words = filtered;
		} else {    // このときはcoloredcount回以上使われている
			var filtered = new SortedSet<string>();
			foreach(var w in words) {
				if(w.Where(p => p == cg.Key).Count() >= coloredcount &&		// coloredcount回以上その文字が使われているとき
				   cg.Where(p => p.hint == HintState.ExactPosition).All(p => w[p.pos] == p.character) &&  // 緑色がそこに使われていて
				   cg.Where(p => p.hint == HintState.NotInPosition).All(p => w[p.pos] != p.character))    // 黄色がそこに使われていない
					filtered.Add(w);
			}
			words = filtered;
		}
	}

	return words;
}

こっちは結構頭を使いました。ヒントの文字数を数えるところから始めます。

例えばdrillという単語が与えられ、という判定結果となったとします。まずは文字種でグルーピングします。

d:
r:
i:
l:

という判定結果になります。これらそれぞれのグループの要素数と、色が付いている（＝黄＋緑の）要素の数をそれぞれ数えます。

d: 1, 0
r: 1, 0
i: 1, 0
l: 2, 1

(グループの要素数) > (色が付いている要素の数)の場合、答えの単語ではちょうど(色が付いている要素の数)だけその文字が含まれることがわかります。今回はd, r, i, lすべての文字がこの条件を満たしていますので、答えの単語はそれぞれの文字が0, 0, 0, 1個ずつ含まれるということがわかります。あとは、文字が含まれている場合は緑ならその場所、黄色なら異なる場所という判定をしてやればいいです。すでに文字数の判定は済ませてあるので、1個目のlがどこに割り当てられて…などと考える必要もありません。

(グループの要素数) = (色が付いている要素の数)の場合、答えの単語でその文字は(色が付いている要素の数)個以上使われていると言えます。あとは同様に緑か黄色かで場所を判断してやればいいだけです。

再評価

前回の記事でalertやtrailあたりが1語目に良いという判断をしました。これらの手数を、この修正したアルゴリズムで再評価してみました。

alert

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6667	6
過去問	common→all	2	3.8551	6
過去問	all	2	4.2138	9
frequent	frequent→common→all	1	3.1905	6
frequent	common→all	1	3.8057	7
frequent	all	1	4.2008	8
common	frequent→common→all	1	3.8876	10
common	common→all	1	3.8309	9
common	all	1	4.2571	9
all	frequent→common→all	1	4.5722	13
all	common→all	1	4.5432	13
all	all	1	4.4346	11

trail

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6268	7
過去問	common→all	2	3.8333	7
過去問	all	2	4.2174	9
frequent	frequent→common→all	1	3.1879	5
frequent	common→all	1	3.7902	7
frequent	all	1	4.1519	7
common	frequent→common→all	1	3.8908	9
common	common→all	1	3.8353	8
common	all	1	4.2505	9
all	frequent→common→all	1	4.6055	11
all	common→all	1	4.5181	12
all	all	1	4.4344	12

ほとんど差はありませんでしたが、アルゴリズム修正前より平均手数は微減のようです。そりゃ同じ文字があった時の情報量が微妙に増えるのですから、そうでしょう。

一方で、計算時間は結構長くなりました。まあ、複雑になったから仕方ないですね。現状のプログラムではこの本体のアルゴリズム外のところにもう少し改善の余地はありますが、本筋とは関係ないのでぼちぼちやっていくこととしましょう。

余談

Wordleに初回アクセスした際に次のようなイントロダクションが表示されます。 

"The letter U is not in the word in any spot."って書いてあるけど嘘やんけ！！！

Wordleのソルバーを作る

先日の記事でWordleに表示された条件を入力したら候補の単語を表示してくれるソフトを作りました。この応用で、「次に入力すべき単語」を提案してくれるソフトを作っていきたいと思います。

メタ的なアプローチ

いきなりですがメタ的なアプローチをします。メタ的というのは、「こういう単語が出そう」という予想から始めるという意味です。

Wordleに入力できる（＝答えとしてあり得る） 単語はこちらのページに出ています。

Wordle 単語リスト

しかし、中には固有名詞だったり普通の英和辞典では出てこなかったりと、かなりニッチな単語もあります。そのような単語が答えになることはまずなく、メジャーな単語が答えになる「だろう」という解き方です。

邪道と思う人も多いかもしれませんが、現実としてWordleを少ない手数で解こうと思うとかなり有効と考えられます。

メジャーな単語

さて、そうするとここで重要になってくるのが「メジャーな単語」です。何をもってメジャーと言うかですが、こういうのは意外と世の中研究されているようです。今回は2種類持ってきました。

Moby Word Lists by Grady Ward

BNC database and word frequency lists

前者には様々な単語のリストがありますが、今回は「common」を選びました。これは2つ以上の辞書に載っているような一般的な単語が入っているようです。後者は「Lemmatised list（見出し語リスト）」から選びました。おそらく記事の見出しなどで使われる言葉なんだと思います。

前者は約75,000語、後者は約6,300語ありますが、Wordle単語リストに含まれていないものを除外するとそれぞれ4,056語、777語となりました。便宜上、前者を「common」、後者を「frequent」と呼ぶこととします。

common.txt

frequent.txt

評価

本日（2022年3月21日）時点でWordleは275まで来ています。どうもスタートは0だったらしく、合計276語が今までに出題されていたようです。この単語がcommonやfrequentにどれくらい含まれているかを調べてみました。

	Common	Frequent
答えが含まれている割合	96.74%	42.03%
全体に対する単語数の割合	31.27%	5.99%

Wordleの全単語のうち6%に42%の答えが集中し、1/3弱に96%以上の答えが集中していることになります。これを愚直に全単語から1つの単語を取り出すためのアルゴリズムを考え続けるのはかなりもったいないです。ですので、メタ的な解法ではありますが、基本戦略としてこれら2つの単語リストをできるだけ生かしていくことにします。

文字の出現頻度

さて、続いて正統派（？）なアプローチをしていきます。Wordleはできるだけ少ない手数で上がるゲームですので、絞り込みが進めば進むほど、すなわち単語を入力したときに次の候補の数が少なければ少ないほど良い手と言えます。

ですので、極端に言えば、総当たりですべての入力可能な単語を入れて、そして答えがすべてのパターンだった時を想定して、候補数が最小になるものを選べば良いという話になります。ただ、基本的に入力可能な単語の数も答えの候補の数もオーダーは同じですので、すべての組み合わせを試すには$O(n^2)$の計算量が必要です。全単語は13,000語弱ありますから、良いアプローチとは言えません。

そこで、文字の出現頻度を使った方法を考えていきます。Wordleは⬜よりも🟨や🟩が出た時のほうがゲームが大きく進むことを利用し、最も使われる文字から入れていって早く🟨や🟩を出してしまおうという作戦です。

それぞれの文字の出現頻度は以下の通りです。

前述の通り、Wordleに入れられるすべての文字のほか、commonやfrequentという単語セットを用意しましたので、それぞれについて求めています。一部eやsなどのように偏りがあるものもありますが、概ね同様の傾向と言えるでしょう。あまりどの母集団を使うかは気にしなくてよさそうです。

ソルバーの実装/評価

まずは、出現頻度評価が簡単にできるようにこんな基底クラスを実装してみました。

public abstract class SolverBase : ISolver
{
	public abstract string Suggest(IEnumerable<IWordHint> hints);

	protected Dictionary<char, int> GetCharCount(IEnumerable<string> words)
	{
		return GetCharCount(words.SelectMany(p => p));
	}

	protected Dictionary<char, int> GetCharCount(IEnumerable<char> chars)
	{
		var result = new Dictionary<char, int>();
		for(var c = 'a'; c <= 'z'; c++)
			result[c] = 0;
		foreach(var c in chars)
			result[c]++;
		return result;
	}

	protected IEnumerable<(string word, int point)> GetWordRanking(IEnumerable<string> words, IReadOnlyDictionary<char, int> charcount)
	{
		return words.Select(p => (word: p, point: p.Distinct().Sum(p => charcount[p]))).OrderByDescending(p => p.point);
	}
}

GetCharCount()は各文字が何回ずつ使われているかを数えるメソッドです。

GetWordRanking()は単語リストを与えると、各文字に割り当てられた点数をもとにスコアを計算し、上位から順に返すメソッドです。同じ文字が2回以上使われる単語で点数を重複して加算するのは不適切なので、そのような場合は2回目以降ゼロ点になるようにしています。

実際は、GetCharCount()で得た文字の出現回数をそのまま点数としてGetWordRankingに渡すことを想定しています。

頻出文字法

さて、具体的に実装と評価を行っていきます。まずはシンプルに、「頻出文字を多く含む単語から順に入れていく」作戦をします。

public class FrequentCharSolver : SolverBase
{
	IReadOnlySet<string>[] universe;

	public FrequentCharSolver(IReadOnlySet<string>[] universe)
	{
		this.universe = universe;
	}

	public override string Suggest(IEnumerable<IWordHint> hints)
	{
		IReadOnlySet<string>? candidates = null;

		foreach(var list in universe) {
			candidates = Candidate.Nominate(hints, list);
			if(candidates.Count > 0)
				break;
		}

		if(candidates == null || candidates.Count <= 0)
			throw new InvalidOperationException();

		return GetWordRanking(candidates, GetCharCount(candidates)).First().word;
	}
}

コンストラクタで受け取るuniverseは調べる単語の母集団、すなわちfrequent / common / allです。1つ目の母集団のつもりで検索をかけ、もしも無かったら次の母集団に行くという流れになります。回答を確実に含む母集団が必ずなければなりませんので、allを最後に含める必要があります。

これらについて、お題の単語を過去問 / frequent / common / allの4つパターンを与え、計12パターンの評価をしてみました。

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.7572	8
過去問	common→all	2	4.0326	8
過去問	all	2	4.5000	11
frequent	frequent→common→all	1	3.1609	6
frequent	common→all	2	4.0193	10
frequent	all	2	4.5328	13
common	frequent→common→all	1	3.9768	10
common	common→all	1	3.9539	10
common	all	2	4.5155	14
all	frequent→common→all	1	4.8251	17
all	common→all	1	4.9184	16
all	all	1	4.8366	16

上3行を見ても明らかですが、前述の「メタ解法」がめちゃめちゃ有効であることがわかります。ほかはあまり言えることはなさそうですが、まあ一般として検索母集団が最初から大きければ大きいほど手数がかかること、検索母集団とお題の母集団が一致しているときは比較的手数が少なくて済む（逆転現象すら起こりうる）というところでしょうか。

過去問の母集団がfrequentとcommonのどちらが近いかと言われるとなかなか難しいので、ひとまず今後の評価ではこれら12通りをやっていくことにします。

セルフハードモード解除

さて、上のアルゴリズムには1つ大きな問題があります。それはセルフハードモードだということです。

Wordleにはハードモードというものがあり、緑や黄色の文字が出てきたら、それをしかるべき場所に使わなくてはならないというモードです。一方で、ハードモードでなければ、すでに緑や黄色の文字が出ていても2手目くらいなら候補を絞るためにあえて全く関係のない語を入れるという戦略も考えられます。しかし、前項のアルゴリズムはシンプルに「候補の中から次の候補を選ぶ」という操作をしているため、いわばセルフハードモード状態になっています。これを解消していきましょう。

public class NotHardModeSolver: MultipleUniverseBase
{
	public NotHardModeSolver(IReadOnlySet<string>[] universe) : base(universe) { }

	public override string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates)
	{
		if(candidates.Count >= 9) {
			var score = GetCharCount(candidates);

			// 緑や灰の文字はできるだけ使わないようにする
			foreach(var c in hints.SelectMany(p => p.Characters).Where(p => p.Hint != HintState.ExactPosition || p.Hint != HintState.NotContained).Select(p => p.Character))
				score[c] = -1;

			var yellow = hints.SelectMany(p => p.Characters.Select((c, i) => (c, i))).Where(p => p.c.Hint == HintState.NotInPosition).ToArray();

			return GetWordRanking(WordList.All, score)
				.Select(p => (p.word, p.point, ypt: yellow.Select(p1 => p.word[p1.i] == p1.c.Character).Count(p => p)))	// ypt: 黄色の文字がその場所で使われている個数
				.OrderBy(p => p.ypt)			// 黄色の文字がその場所で使われている個数が少ない順で
				.ThenByDescending(p => p.point)	// pointが高い順
				.First().word;
		}

		return GetWordRanking(candidates, GetCharCount(candidates)).First().word;
	}
}

public abstract class MultipleUniverseBase : SolverBase
{
	IReadOnlySet<string>[] universe;

	public MultipleUniverseBase(IReadOnlySet<string>[] universe)
	{
		this.universe = universe;
	}

	public sealed override string Suggest(IEnumerable<IWordHint> hints)
	{
		IReadOnlySet<string>? candidates = null;

		foreach(var univ in universe) {
			candidates = Candidate.Nominate(hints, univ);
			if(candidates.Count > 0)
				break;
		}

		if(candidates == null || candidates.Count <= 0)
			throw new InvalidOperationException();

		return Suggest(hints, candidates);
	}

	public abstract string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates);
}

先ほどのFrequentCharSolverから複数の母集団を指定する機能を分離しました。そのうえで、今回のセルフハードモード解除を実装しています。

その実装にあたっては、候補が9個以上あった場合にこのアルゴリズムが発動するようにしました。9の根拠は希薄ですが、8や10を入れた時より過去問のfrequent→common→allの平均手数が少なくなったからです。

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6920	7
過去問	common→all	2	3.9601	7
過去問	all	2	4.3587	9
frequent	frequent→common→all	1	3.1918	6
frequent	common→all	2	3.9408	10
frequent	all	2	4.2664	10
common	frequent→common→all	1	3.9001	10
common	common→all	2	3.8715	10
common	all	2	4.2710	10
all	frequent→common→all	1	4.6425	13
all	common→all	1	4.6295	12
all	all	1	4.4554	12

過去問でも平均0.1手程度下がっており、候補数の多いall-allなどでは特に顕著に下がっています。まあ、all-allは本命ではないですが、十分良い結果と言えるでしょう。

1文字違い対策

さて、Wordleを長くやっていると一度はぶち当たる問題、それは1文字違いです。例えば答えが"hatch"の場合、上のアルゴリズムに沿って解くとaleart→chinsと入力することになり、その時点での候補が以下の通りになります。

batch
match
patch
watch
（この段階ではfrequentリストで検索しているためhatchが含まれていません。）

嫌らしいですねぇ。最初の1文字だけが違い、あとは全部-atchと続きます。このとき順に候補を入れていった場合、答えにたどりつくまでにかかる手数の期待値は2.5となります。一方で、次の一手でbmpwをできるだけ含む単語を1つ入れてやれば、その次の1手で答えにたどり着ける可能性が高まります。

しかしこれには注意しなければいけない要素があります。例えば、catchなど未確定部が確定部の文字を含む場合、cを含む語を用意したところでcatchのcなのかcatchのcなのかを判別することは（緑にならない限り）できません。このような語は除外して消去法で考えるべきでしょう。

類題も見ていきましょう。答えがwhelpの場合、alert→whidsと入力されることになります。この時点での候補は

wheel
whelk
whelm
whelp

となります。1字違いではないですが、この時点ではkmpを含む語を入れたくなりますね。

ここでのポイントは、「候補のすべてに共通する文字を除いた残りの文字をたくさん使う語を選ぶ」にほかなりません。これを実装していきましょう。

public class NotCommonCharSolver : NotHardModeSolver
{
	public NotCommonCharSolver(IReadOnlySet<string>[] universe) : base(universe) { }

	public override string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates)
	{
		const int commoncharcnt = 4;

		if(candidates.Count >= 4) {
			var intersect = candidates.First().ToArray();
			foreach(var candidate in candidates.Skip(1)) {
				intersect = intersect.Intersect(candidate).ToArray();
				if(intersect.Length < commoncharcnt)
					break;
			}

			if(intersect.Length >= commoncharcnt) {
				var hintwords = hints.Select(p => p.Word).ToArray();
				var excepted = candidates.SelectMany(p => p).Except(intersect).ToArray();
				if(excepted.Length > 0)	// アナグラムになっていたらこのアルゴリズムは使わない
					return GetWordRanking(WordList.All, GetCharCount(excepted)).First().word;					
			}
		}

		return base.Suggest(hints, candidates);
	}
}

こんな感じでどうでしょう。候補が4つ以上で共通の文字が4個以上あったらこのアルゴリズムが発動し、その共通の文字以外の文字が多く使われている語を探し出してきます。

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6703	6
過去問	common→all	2	3.9094	7
過去問	all	2	4.3261	9
frequent	frequent→common→all	1	3.1905	6
frequent	common→all	2	3.9331	7
frequent	all	2	4.2664	8
common	frequent→common→all	1	3.8935	10
common	common→all	2	3.8676	8
common	all	2	4.2668	9
all	frequent→common→all	1	4.5880	13
all	common→all	1	4.5692	12
all	all	1	4.4411	12

平均手数は本当に微減ですが、最大手数が小さくなっているものが多いです。特に今までのアルゴリズムだと1字違いは総当たりになっていたため、単語によってはめちゃめちゃ回数を使っていました。それを底上げすることができたので、最大手数削減という結果につながったのですね。

さらに、なんと過去問の最大手数が6手になりました。すなわち、過去問は全クリできるということになります。素晴らしい。

最強の1手目を求めて

さて、今までは1手目にはあまりこだわらずにソフトを組んできました。今までのアルゴリズムによって自動的に求められる1手目が入力されています。具体的には、検索母集団がfrequentのときはalert、commonのときはarose、allのときはaerosが入っていました。

しかしこれが本当に最良なの？という疑問も同時にあるわけです。特に、1手目は完全にノーヒントで、今までの結果には何も左右されません。「最善」を探すうえでは条件は比較的緩いでしょう。

ということで調べてみましょう。…と言っても時間がかかるので、頻出単語を上から順に適当に漁ってみた際の良さげな単語をすでに拾ってきております。その名もずばりalert、sonde、trailです。

alert

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6703	6
過去問	common→all	2	3.8587	7
過去問	all	2	4.2138	9
frequent	frequent→common→all	1	3.1905	6
frequent	common→all	2	3.8069	7
frequent	all	2	4.2008	8
common	frequent→common→all	1	3.8935	10
common	common→all	1	3.8331	9
common	all	1	4.2586	9
all	frequent→common→all	1	4.5880	13
all	common→all	1	4.5538	13
all	all	1	4.4369	11

frequentスタートはもともとalertだったので変わりませんが、それ以外は全体的に手数が少なくなっています。

snode

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6630	8
過去問	common→all	2	3.8587	7
過去問	all	2	4.2283	8
frequent	frequent→common→all	1	3.2561	6
frequent	common→all	2	3.8456	8
frequent	all	2	4.2291	8
common	frequent→common→all	2	3.9068	9
common	common→all	2	3.8333	7
common	all	2	4.2756	9
all	frequent→common→all	2	4.6222	11
all	common→all	2	4.5203	13
all	all	2	4.4367	11

過去問のfrequentスタートは平均手数が微減していますが（というかそれで選んできました）最大手数が8手になってしまい、過去問全クリならずです。他のアルゴリズムは全体的に平均手数も最大手数も悪化する傾向にあり、alertと比較してあまり良い手と言えないかもしれません。

trail

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6232	7
過去問	common→all	2	3.8297	7
過去問	all	2	4.2210	9
frequent	frequent→common→all	1	3.1879	5
frequent	common→all	1	3.7902	7
frequent	all	1	4.1532	7
common	frequent→common→all	1	3.8950	9
common	common→all	1	3.8351	8
common	all	1	4.2522	9
all	frequent→common→all	1	4.6203	11
all	common→all	1	4.5272	12
all	all	1	4.4371	12

過去問のfrequentスタートは最も平均手数が少ないですが、最大手数は7でやはりはみ出ています。平均手数は全体的にはalertより若干下くらいで、最大手数が増えたことを踏まえるとどっこいどっこいでしょうか。

まとめ

Wordleをやるときは最初にalertまたはtrailを入れて、あとは比較的平易な英単語を探してください。

探す際は、基本的に頻出文字を多く含んだ単語を入れ、候補が9個以上あるなら答えは狙わずに今まで出てきていない文字+黄色の文字を含んだ語を入れる、候補の単語に共通の文字が4つあるなら、共通ではない文字を多く含む単語を入れるという戦略で行けば、平均3.6～3.7手程度、最大6～7手程度で上がれます。

というのが、今まで私が研究してきた結論です。もっと良い方法があればコメントにて教えてください。