Processing math: 100%

2022年3月26日土曜日

Wordleの判定アルゴリズム

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

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

解説

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

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

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

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

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

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

実装

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

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

MakeHint.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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の判定結果からそれを満たす単語を返すメソッドを作っていきましょう。

Candidate.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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."って書いてあるけど嘘やんけ！！！

投稿者 時刻: 0 件のコメント:
ラベル: ,

2022年3月22日火曜日

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などのように偏りがあるものもありますが、概ね同様の傾向と言えるでしょう。あまりどの母集団を使うかは気にしなくてよさそうです。

ソルバーの実装/評価

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

SolverBase
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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に渡すことを想定しています。

頻出文字法

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

FrequentCharSolver
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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手目くらいなら候補を絞るためにあえて全く関係のない語を入れるという戦略も考えられます。しかし、前項のアルゴリズムはシンプルに「候補の中から次の候補を選ぶ」という操作をしているため、いわばセルフハードモード状態になっています。これを解消していきましょう。

NotHardModeSolver
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
}
MultipleUniverseBase
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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を含む語を入れたくなりますね。

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

NotCommonCharSolver
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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手程度で上がれます。
というのが、今まで私が研究してきた結論です。もっと良い方法があればコメントにて教えてください。
投稿者 時刻: 0 件のコメント:
ラベル: ,

2022年3月19日土曜日

Visual Studio 2022からSSHでgit pushする

備忘録程度に。

以前Synology NAS上に立てたGitサーバーにVS2022からSSH経由でpushしようとしたところ、以下のようなエラーが出て失敗しました。

master をプッシュしています
ssh_askpass: exec(c:/program files/microsoft visual studio/2022/community/common7/ide/commonextensions/microsoft/teamfoundation/team explorer/Git/mingw32/libexec/git-core\\git-askpass.exe): No such file or directory
Permission denied, please try again.
ssh_askpass: exec(c:/program files/microsoft visual studio/2022/community/common7/ide/commonextensions/microsoft/teamfoundation/team explorer/Git/mingw32/libexec/git-core\\git-askpass.exe): No such file or directory
Permission denied, please try again.
ssh_askpass: exec(c:/program files/microsoft visual studio/2022/community/common7/ide/commonextensions/microsoft/teamfoundation/team explorer/Git/mingw32/libexec/git-core\\git-askpass.exe): No such file or directory
gituser@192.168.*.*: Permission denied (publickey,password).
リモート リポジトリにブランチをプッシュできませんでした。詳しくは、出力ウィンドウをご覧ください。
リモート リポジトリへのブランチのプッシュ中にエラーが発生しました: Git failed with a fatal error.
Git failed with a fatal error.
Could not read from remote repository.

git-askpass.exeというバイナリが無いのが原因のようです。このバイナリは以下のサイトから入手できます。 

https://github.com/Microsoft/Git-Credential-Manager-for-Windows/releases/tag/v1.16.3

ここからダウンロードしたファイルを解凍し、そのまま当該フォルダに入れてやればOKです。

ちなみに最新のSynologyのOSではSSHポートが2222に変更されているようです（設定から変えられます）。ここもハマりポイントですので注意してください。

投稿者 時刻: 0 件のコメント:
ラベル: , , ,

2022年3月14日月曜日

e-Paper（電子ペーパー）を制御する

先日日本橋の電気街をぶらぶらしていたところ、組み込み用の電子ペーパーを見かけました。

電子ペーパーと言えばKindleなどに採用されているディスプレイで、電源を切っても表示内容を維持することができるタイプの画面です。そのため、原理的に画面更新時にしか電力を消費せず、電子書籍のように1分に1回とかの更新で良いような用途では有用なディスプレイですね。

しかし、そのお店で売っていた電子ペーパーは1万円台前半と非常に高く、「ちょっと買ってみるか」くらいでは手が出るものではありませんでした。ですが、ちょっと調べてみると、秋月電子で2,500円の電子ペーパーが売っているじゃありませんか。普通の液晶に比べればちょっと高めですが、まあ、買ってやれないものでもないでしょう。

ということで、実際に買って制御してみました。まずは完成形から見ていきましょう。

見ての通り、画面の更新に約30秒かかります。これは仕様のようです。

SPIでコントローラーのSRAMのバッファーを更新するのはほとんど一瞬で終わりますが、その後の画面リフレッシュに30秒くらいかかるようです。 時計などの用途を考えるとあんまりイケてなさそうですね。

回路設計

回路自体はそんなに難しくないのですが、ドキュメントがイケてないのでめちゃめちゃわかりにくいです。

File:2.13inch e-Paper HAT Schematic.pdf

こちらが回路図になります。ただとても読みにくい。何がどこにつながっているのかかなり難解ですし、挙句の果てには「P1」「J2」「U1」などの部品番号も基板上にプリントされていないという有様です。

解説すると、液晶コントローラー自体は3.3Vで動作するようで、 5V系のマイコンでも操作できるようにレギュレーターとレベルコンバーターが付いているようです。そのレベルコンバーターがU1、レギュレーターがU2です。P3（基板に横向きに出ている白色コネクタ）からコントロールする場合は5Vで制御できます。

一方で、P1はピンソケットで、Raspberry Pi Zeroに直接接続することを意図しているようです（というか液晶サイズもRaspberry Pi Zeroピッタリです）。ですので、ピン配列はRaspberry Pi Zeroのものを参照するとわかりやすいでしょう。ここのコネクタから3.3V系の回路に直結できますので、3.3Vで動作するマイコンに接続する場合はP3を使用する必要はなく、P1から直接接続することができます。

今回はPIC16F18326を使うことにしました。理由は、170円と安価な割にプログラムメモリが16kワードと大きいからです。今回の液晶は104×212ドットの2色表示のため、画像1枚で5.5kBほど使います。

回路図はこんな感じになります。一応e-paper側でDeep Sleepに入ると消費電力が数μAまで下がるようですが、完全にシャットアウトできるようにPICでe-paperの電源を掌握できるようにしています。

ソフト作成

ドライバソフトはメーカーのGithubに載っています。

e-Paper

ただし、PIC用は無いため、Arduino用のを移植する必要があります。今回使うのは3色タイプのLCDなので、e-Paper/Arduino/epd2in13bc/ 以下のファイルを移植していきます。

epd2in13bc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include "epd2in13bc.h"
 
 
int EpdIf_Init(void) {
    /*
    SPI.begin();
    SPI.beginTransaction(SPISettings(2000000, MSBFIRST, SPI_MODE0));
    */
     
    return 0;
}
 
void EpdIf_SpiTransfer(unsigned char data) {
    DO_SCL = 0;
    DO_CS = 0;
 
    for(int i = 0; i < 8; i ++) {
        DO_SDA = (data & 0x80) ? 1 : 0;
        data <<= 1;
        DO_SCL = 1;
        NOP();
        NOP();
        DO_SCL = 0;
    }
 
    DO_CS = 1;
}
 
 
 
int Epd_Init(void) {
    /* this calls the peripheral hardware interface, see epdif */
    if(EpdIf_Init() != 0) {
        return -1;
    }
    /* EPD hardware init start */
    Epd_Reset();
    Epd_SendCommand(BOOSTER_SOFT_START);
    Epd_SendData(0x17);
    Epd_SendData(0x17);
    Epd_SendData(0x17);
    Epd_SendCommand(POWER_ON);
    Epd_WaitUntilIdle();
    Epd_SendCommand(PANEL_SETTING);
    Epd_SendData(0x8F);
    Epd_SendCommand(VCOM_AND_DATA_INTERVAL_SETTING);
    Epd_SendData(0x37);
    Epd_SendCommand(RESOLUTION_SETTING);
    Epd_SendData(EPD_WIDTH);     // width: 104
    Epd_SendData(0x00);
    Epd_SendData(EPD_HEIGHT);     // height: 212
    /* EPD hardware init end */
    return 0;
 
}
 
/**
 *  @brief: basic function for sending commands
 */
void Epd_SendCommand(unsigned char command) {
    DO_DC = 0;
    EpdIf_SpiTransfer(command);
}
 
/**
 *  @brief: basic function for sending data
 */
void Epd_SendData(unsigned char data) {
    DO_DC = 1;
    EpdIf_SpiTransfer(data);
}
 
/**
 *  @brief: Wait until the busy_pin goes HIGH
 */
void Epd_WaitUntilIdle(void) {
    while(DI_BUSY == 0) {      //0: busy, 1: idle
        __delay_ms(100);
    }     
}
 
/**
 *  @brief: module reset.
 *          often used to awaken the module in deep sleep,
 *          see Epd::Sleep();
 */
void Epd_Reset(void) {
    DO_RST = 0;
    __delay_ms(200);
    DO_RST = 1;
    __delay_ms(200);  
}
 
/**
 *  @brief: transmit partial data to the SRAM
 */
void Epd_SetPartialWindow(const unsigned char* buffer_black, const unsigned char* buffer_red, int x, int y, int w, int l) {
    Epd_SendCommand(PARTIAL_IN);
    Epd_SendCommand(PARTIAL_WINDOW);
    Epd_SendData(x & 0xf8);     // x should be the multiple of 8, the last 3 bit will always be ignored
    Epd_SendData((unsigned char)(((x & 0xf8) + w  - 1) | 0x07));
    Epd_SendData((unsigned char)(y >> 8));       
    Epd_SendData(y & 0xff);
    Epd_SendData((unsigned char)((y + l - 1) >> 8));       
    Epd_SendData((y + l - 1) & 0xff);
    Epd_SendData(0x01);         // Gates scan both inside and outside of the partial window. (default)
    __delay_ms(2);
    Epd_SendCommand(DATA_START_TRANSMISSION_1);
    if (buffer_black != NULL) {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(buffer_black[i]); 
        } 
    } else {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(0x00); 
        } 
    }
    __delay_ms(2);
    Epd_SendCommand(DATA_START_TRANSMISSION_2);
    if (buffer_red != NULL) {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(buffer_red[i]); 
        } 
    } else {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(0x00); 
        } 
    }
    __delay_ms(2);
    Epd_SendCommand(PARTIAL_OUT); 
}
 
/**
 *  @brief: transmit partial data to the black part of SRAM
 */
void Epd_SetPartialWindowBlack(const unsigned char* buffer_black, int x, int y, int w, int l) {
    Epd_SendCommand(PARTIAL_IN);
    Epd_SendCommand(PARTIAL_WINDOW);
    Epd_SendData(x & 0xf8);     // x should be the multiple of 8, the last 3 bit will always be ignored
    Epd_SendData((unsigned char)(((x & 0xf8) + w  - 1) | 0x07));
    Epd_SendData((unsigned char)(y >> 8));       
    Epd_SendData(y & 0xff);
    Epd_SendData((unsigned char)((y + l - 1) >> 8));       
    Epd_SendData((y + l - 1) & 0xff);
    Epd_SendData(0x01);         // Gates scan both inside and outside of the partial window. (default)
    __delay_ms(2);
    Epd_SendCommand(DATA_START_TRANSMISSION_1);
    if (buffer_black != NULL) {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(buffer_black[i]); 
        } 
    } else {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(0x00); 
        } 
    }
    __delay_ms(2);
    Epd_SendCommand(PARTIAL_OUT); 
}
 
/**
 *  @brief: transmit partial data to the red part of SRAM
 */
void Epd_SetPartialWindowRed(const unsigned char* buffer_red, int x, int y, int w, int l) {
    Epd_SendCommand(PARTIAL_IN);
    Epd_SendCommand(PARTIAL_WINDOW);
    Epd_SendData(x & 0xf8);     // x should be the multiple of 8, the last 3 bit will always be ignored
    Epd_SendData((unsigned char)(((x & 0xf8) + w  - 1) | 0x07));
    Epd_SendData((unsigned char)(y >> 8));
    Epd_SendData(y & 0xff);
    Epd_SendData((unsigned char)((y + l - 1) >> 8));
    Epd_SendData((y + l - 1) & 0xff);
    Epd_SendData(0x01);         // Gates scan both inside and outside of the partial window. (default)
    __delay_ms(2);
    Epd_SendCommand(DATA_START_TRANSMISSION_2);
    if (buffer_red != NULL) {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(buffer_red[i]); 
        } 
    } else {
        for(int i = 0; i < w  / 8 * l; i++) {
            Epd_SendData(0x00); 
        } 
    }
    __delay_ms(2);
    Epd_SendCommand(PARTIAL_OUT); 
}
 
/**
 * @brief: refresh and displays the frame
 */
void Epd_DisplayFrame(const unsigned char* frame_buffer_black, const unsigned char* frame_buffer_red) {
    if (frame_buffer_black != NULL) {
        Epd_SendCommand(DATA_START_TRANSMISSION_1);
        __delay_ms(2);
        for (int i = 0; i < EPD_WIDTH * EPD_HEIGHT / 8; i++) {
            Epd_SendData(frame_buffer_black[i]);
            //Epd_SendData(~(i & 0xFF));
        }
        __delay_ms(2);
    }
    if (frame_buffer_red != NULL) {
        Epd_SendCommand(DATA_START_TRANSMISSION_2);
        __delay_ms(2);
        for (int i = 0; i < EPD_WIDTH * EPD_HEIGHT / 8; i++) {
            Epd_SendData(frame_buffer_red[i]);
            //Epd_SendData(0xFF);
        }
        __delay_ms(2);
    }
    Epd_SendCommand(DISPLAY_REFRESH);
    Epd_WaitUntilIdle();
}
 
/**
 * @brief: clear the frame data
 */
void Epd_ClearFrame(void) {
    Epd_SendCommand(DATA_START_TRANSMISSION_1);          
    __delay_ms(2);
    for(int i = 0; i < EPD_WIDTH * EPD_HEIGHT / 8; i++) {
        Epd_SendData(0xFF); 
    } 
    __delay_ms(2);
    Epd_SendCommand(DATA_START_TRANSMISSION_2);          
    __delay_ms(2);
    for(int i = 0; i < EPD_WIDTH * EPD_HEIGHT / 8; i++) {
        Epd_SendData(0xFF); 
    } 
    __delay_ms(2);
 
    Epd_SendCommand(DISPLAY_REFRESH);
    Epd_WaitUntilIdle();
}
 
/**
 * @brief: This displays the frame data from SRAM
 */
void Epd_Refresh(void) {
    Epd_SendCommand(DISPLAY_REFRESH);
    Epd_WaitUntilIdle();
}
 
 
/**
 * @brief: After this command is transmitted, the chip would enter the deep-sleep mode to save power.
 *         The deep sleep mode would return to standby by hardware reset. The only one parameter is a
 *         check code, the command would be executed if check code = 0xA5.
 *         You can use Epd::Reset() to awaken and use Epd::Init() to initialize.
 */
void Epd_Sleep() {
    Epd_SendCommand(POWER_OFF);
    Epd_WaitUntilIdle();
    Epd_SendCommand(DEEP_SLEEP);
    Epd_SendData(0xA5);     // check code
}
epd2in13bc.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#ifndef EPD2IN13B_H
#define EPD2IN13B_H
 
#include <xc.h>
#define _XTAL_FREQ 32000000    // Fosc = 8MHz
 
 
#define DO_SDA          LATCbits.LATC2
#define DO_SCL          LATCbits.LATC0
#define DO_CS           LATCbits.LATC4
#define DO_DC           LATCbits.LATC5
#define DO_RST          LATCbits.LATC3
#define DI_BUSY         PORTAbits.RA4
 
 
// Display resolution
#define EPD_WIDTH       104
#define EPD_HEIGHT      212
 
// EPD2IN13B commands
#define PANEL_SETTING                               0x00
#define POWER_SETTING                               0x01
#define POWER_OFF                                   0x02
#define POWER_OFF_SEQUENCE_SETTING                  0x03
#define POWER_ON                                    0x04
#define POWER_ON_MEASURE                            0x05
#define BOOSTER_SOFT_START                          0x06
#define DEEP_SLEEP                                  0x07
#define DATA_START_TRANSMISSION_1                   0x10
#define DATA_STOP                                   0x11
#define DISPLAY_REFRESH                             0x12
#define DATA_START_TRANSMISSION_2                   0x13
#define VCOM_LUT                                    0x20
#define W2W_LUT                                     0x21
#define B2W_LUT                                     0x22
#define W2B_LUT                                     0x23
#define B2B_LUT                                     0x24
#define PLL_CONTROL                                 0x30
#define TEMPERATURE_SENSOR_CALIBRATION              0x40
#define TEMPERATURE_SENSOR_SELECTION                0x41
#define TEMPERATURE_SENSOR_WRITE                    0x42
#define TEMPERATURE_SENSOR_READ                     0x43
#define VCOM_AND_DATA_INTERVAL_SETTING              0x50
#define LOW_POWER_DETECTION                         0x51
#define TCON_SETTING                                0x60
#define RESOLUTION_SETTING                          0x61
#define GET_STATUS                                  0x71
#define AUTO_MEASURE_VCOM                           0x80
#define READ_VCOM_VALUE                             0x81
#define VCM_DC_SETTING                              0x82
#define PARTIAL_WINDOW                              0x90
#define PARTIAL_IN                                  0x91
#define PARTIAL_OUT                                 0x92
#define PROGRAM_MODE                                0xA0
#define ACTIVE_PROGRAM                              0xA1
#define READ_OTP_DATA                               0xA2
#define POWER_SAVING                                0xE3
 
int  Epd_Init(void);
void Epd_SendCommand(unsigned char command);
void Epd_SendData(unsigned char data);
void Epd_WaitUntilIdle(void);
void Epd_Reset(void);
void Epd_SetPartialWindow(const unsigned char* buffer_black, const unsigned char* buffer_red, int x, int y, int w, int l);
void Epd_SetPartialWindowBlack(const unsigned char* buffer_black, int x, int y, int w, int l);
void Epd_SetPartialWindowRed(const unsigned char* buffer_red, int x, int y, int w, int l);
void Epd_DisplayFrame(const unsigned char* frame_buffer_black, const unsigned char* frame_buffer_red);
void Epd_Refresh(void);
void Epd_ClearFrame(void);
void Epd_Sleep(void);
 
#endif

オリジナルのライブラリでは、ハードウェアのインターフェース部と論理部できれいに分けて実装されていたのですが、移植するにあたってごちゃ混ぜにしてしまいました。XC8がC++をサポートしていないうえ、PICのピン操作は直接レジスタ触ることになるというのが主な理由です。もう少しやりようはあったかもしれませんが、まあ処理速度優先ということで。

あと、一応回路上ではPICのMSSP（ハードウェアSPI）に対応したピンにアサインしているのですが、SPI送信中に何か別のことをしたいわけでもないので、ソフトウェアで簡単にSPIを実装しています。SPI程度ならMSSPの使い方をデータシート見ながら実装するよりGPIOで作っちゃったほうが簡単ですね。

main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
void UpdateLcd()
{
    DO_LCD_PWR = 1;
    TRIS_LCD_PWR = 0;
     
    __delay_ms(100);
     
    Epd_Init();
 
    switch(content++) {
        case 0:
            Epd_DisplayFrame(img1_black, img1_yellow);
            break;
        case 1:
            Epd_DisplayFrame(img2_black, img2_yellow);
            break;
        default:
            Epd_ClearFrame();
            content = 0;
            break;
    }
 
    Epd_Sleep();   
    TRIS_LCD_PWR = 1;
    LATA = 0;
    LATC = 0;
}
 
void init()
{
    LATA = 0;
    WPUA = 0x20;
    ODCONA = 0;
    ANSELA = 0;
    TRISA = 0xFF;
 
    LATC = 0;
    WPUC = 0;
    ODCONC = 0;
    ANSELC = 0;
    TRISC = 0xC2;
 
    IOCAN = 0x20;
    PIE0 = 0x10;
    INTCON = 0x80;
}
 
void loop()
{
    SLEEP();
    NOP();
     
    if(DI_SW == 0)
        UpdateLcd();   
}
 
void __interrupt() ISR(void)
{
    if(PIR0bits.IOCIF) {
        if(IOCAFbits.IOCAF5) {
            IOCAFbits.IOCAF5 = 0;
        }
    }
}
 
void main(void) {
    init();
     
    while(1)
        loop();
}

main.cでは処理をしていない間はPICをスリープにするようにしています。スイッチを押されるとInterrupt On Change (IOC)にてスリープからウェイクアップすると続きの処理を実行するようになります。この際発生する割り込みの割り込みフラグはちゃんとリセットしないとスリープに入れない（常にスリープ復帰条件ができてしまう）ので、割り込みルーチンではフラグのリセットのみを行っています。

また、e-Paperをdeep sleepにした後はLCDの電源を切っていますが、その際に制御用ピンがHighになっていると、そちらから電源側へ電流が流れてしまう（おそらく液晶コントローラー内に保護用にダイオードが入っている）ので、同時にすべてのピンの出力をゼロにしています。

これで、待機中はナノアンペアオーダーの電流しか流れない、ボタン電池で駆動しても何の支障もないe-Paperができました。

 

それにしても、更新に30秒かかるのはちょっと残念ですね…。せめて数秒程度にしてほしかった…。

投稿者 時刻: 1 件のコメント:
ラベル: , , , , ,
登録: 投稿 (Atom)