Pythonで〇×ゲームのAIを一から作成する　その27　アルゴリズムとデータ構造

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/273ed49a00b90c753031

# 実装の進捗状況と前回までのおさらい

## 〇×ゲームの仕様と進捗状況

1. `正方形で区切られた 3 x 3 の 2 次元のゲーム盤上でゲームを行う`
2. `ゲーム開始時には、ゲーム盤のすべてのマスは空になっている`
3. `2 人のプレイヤーが遊ぶゲームであり、一人は 〇 を、もう一人は × のマークを受け持つ`
4. `2 人のプレイヤーは、交互に空いている好きなマスに自分のマークを 1 つ置く`
5. `先手は 〇 のプレイヤーである`
6. __プレイヤーがマークを置いた結果、縦、横、斜めのいずれかの一直線の 3 マスに同じマークが並んだ場合、そのマークのプレイヤーの勝利とし、ゲームが終了する__
7. __すべてのマスが埋まった時にゲームの決着がついていない場合は引き分けとする__

仕様の進捗状況は、以下のように表記します。

* 実装が完了した部分を `背景が灰色の長方形` で記述する
* 実装の一部が完了した部分を、__太字__ で記述する

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/027/marubatsu.py

https://github.com/ysgeso/marubatsu/blob/master/027/test.py

## 前回までのおさらい

前回の記事では、`judge` メソッドのテストを行う `test_judge` を実装し、命令網羅(C0) と分岐網羅（C1) の条件を満たすテストを行いました。

# 実装がなかなか進まない点について

テストの話が始まってから、〇×ゲームの実装が全然進まないのでじれったいと思っている人が多いかもしれません。筆者もテストの話は、2、3 回くらいで終わるつもりだったのですが、執筆してみると説明したほうが良いと思えることが増えてきて、記事がどんどん長くなってしまいました。

今回の記事で取り上げる、座標を表すデータ構造についても、1 回の記事で終わらせるつもりが、次回に続くことになってしまいました。ただし、__様々なデータ構造__ と、そのデータ構造を扱う __アルゴリズム__ を __体験__ しておくことは、これから自力でプログラムを記述しようと思っている人にとっては必ず将来の役に立つと思います。

また、今回の記事で取り上げる内容は、関数のテストだけでなく、今後の 〇×ゲームや、AI を実装する際に、__実際に使用する__ ことになります。はやく実装を進めたい人にとっては退屈な記事だと思う人がいるかもしれませんが、もうしばらくテストに関する話が続きますのでお付き合いください。

# 座標を表すデータ構造に求められる性質

前回の記事では、テストケースを表すデータを、下記のように記述しました。

もちろん、今後のテストで __テストケースを増やす__ 場合に、下記のデータ構造でテストケースを記述することは可能ですが、着手の座標を表すデータを 2 つの要素を持つ list で __記述するのが大変__ だと思いませんか？

```python
testcases = [
    # 〇 の勝利のテストケース
    [
        [
            [ 0, 0 ], # 着手順とゲーム盤
            [ 0, 1 ], # 135  ooo
            [ 1, 0 ], # 24.  xx.
            [ 1, 1 ], # ...  ...
            [ 2, 0 ],
        ],
        Marubatsu.CIRCLE, # 期待される judge メソッドの返り値
    ],
    # × の勝利のテストケース
    [
        [
            [ 0, 1 ], # 着手順とゲーム盤
            [ 0, 0 ], # 246  xxx
            [ 1, 1 ], # 13.  oo.
            [ 1, 0 ], # 5..  o..
            [ 0, 2 ],
            [ 2, 0 ],
        ],
        Marubatsu.CROSS, # 期待される judge メソッドの返り値
    ],
    # 引き分けのテストケース
    [
        [
            [ 0, 0 ], # 着手順とゲーム盤
            [ 0, 1 ], # 136  oox
            [ 1, 0 ], # 245  xxo
            [ 1, 1 ], # 789  oxo
            [ 2, 1 ],
            [ 2, 0 ],
            [ 0, 2 ],
            [ 1, 2 ],
            [ 2, 2 ],
        ],
        Marubatsu.DRAW, # 期待される judge メソッドの返り値
    ],
]
```

これまでは、着手を行うマスの座標を、__x 座標 と y 座標の値を要素とする list__ というデータ構造で表現してきましたが、ゲーム盤の __異なるマス__ を、__異なるデータ__ で __表現__ することができれば、__他のデータ構造__ で座標を表すデータを __表現してもかまいません__。別の言葉でいうと、__異なるマスを区別__ することができるようなデータ構造であれば、__どのようなデータ構造__ でも __構わない__ ということです。

着手を行う __座標を表すデータ__ を、別の、より __簡潔な記述__ を行うことが出来る __データに置き換える__ ことで、__簡潔にデータを記述__ することができるようになります。

:::note warn
__異なるマスを区別__ できれば良いので、座標を表すデータ構造は、__無限に考える__ ことができます。ただし、__記述のしやすさ__ や、__扱いやすさ__ などの __差は生まれます__。

様々な __データ構造を学ぶ__ ことで、__状況__ に応じた __適切なデータ構造__ を __選択__ することが __できる__ ようになり、その結果として、__効率良く__、__バグが発生しにくい__ プログラムを __記述__ することが __できるようになります__。

本記事では、様々なデータ構造を紹介する際に、それぞれの __性質__、__利点__、__欠点__ などを合わせて紹介しますので、そのことを感じ取ってください。

:::

これから、座標を表す __データ構造__ を __いくつか紹介__ することになるので、それぞれの __データ構造__ に __名前を付けて区別__ することにします。

これまでに利用してきた、「x 座標 と y 座標を要素に持つ list」 で座標を表現するデータ構造の事を、__xy 座標__ と表記することにします。

# xy 座標の利点と欠点

xy 座標の主な利点と欠点は以下の通りです。

__利点__

* 「数値で表現された x 座標、y 座標」という、__数学__ で使われ、多くの人が __慣れ親しんでいる__ 2 次元の座標と同じ方式で、座標を表現するため、__直観的に分かりやすい__
* list を使って __2 つのデータ__ を __別々に表現__ しているため、プログラムでそれぞれの座標を __区別して扱うことが出来る__

__欠点__

* テストケースのように、xy 座標を __直接プログラム内に記述する__ 場合は、`[]` や `,` などの __記号を記述する必要__ があるため、__表記が長くなる__
* list の 0 番のインデックスの要素を x 座標に、1 番のインデックスの要素を y 座標に __対応させている__ が、そのことは __説明がなければ分かりづらい__
* __複数の xy 座標__ を表すデータは、list の中に、xy 座標を表す list を __入れ子__ にするという、__2 次元配列を表す list で表現__ する必要があるが、2 次元配列を表す list の __データの記述__ は一般的に __長く__、見た目が __わかりづらくなる__ という __欠点__ がある

:::note
2 番目の欠点がわかりづらいと思いますので、具体例を挙げて説明します。__何の説明もなし__ に、`[0, 1]` という __list だけ__ を見て、これが座標を表すデータであることを __理解することは難しい__ と思いますが、__dict__ を使った `{ "x": 0, "y": 1 }` のようなデータであれば、__キーの値__ から、座標を表すデータであることが、__説明がなくても__ 直観的に __理解する__ ことができる人は多いでしょう。ただし、この問題は、`x, y = coord` のように、__分かりやすい名前__ の変数に、list の要素を __代入する__ ことで __要素の数が少ない場合__ は __改善__ することが出来ます。

上記の __dict__ を使って座標を表現する __データ構造__ は、__データの記述__ が xy 座標よりも __さらに長くなってしまう__ という __欠点__ があります。また、xy 座標の場合は、数学の座標を (0, 1) のように表記するので、`[0, 1]` が座標を表すデータであることを __直観的に理解__ することは __困難ではない__ でしょう。


今回の記事では、テストケースを __簡潔に記述__ することができるデータ構造を __紹介する__ ことが __目的__ なので、dict を使って座標を表現する具体例は紹介しません。

なお、dict を使ってデータを表現する具体例については、今回の記事の「`excel_to_xy` の定義その 2」の所で紹介します。
:::

xy 座標は、`test_judge` のブロックの中の下記のプログラムのように、__xy 座標__ の中の 2 つの x 座標と y 座標を表すデータを、__簡単に__ 異なる __変数に代入__ して __扱うことができる__ ので、__既に変数に代入__ されている __xy 座標__ のデータを __処理__ する際には __便利です__。

```python
    for x, y in testcase:
        mb.move(x, y)
```

一方、テストケースのように、複数の xy 座標を表すデータをプログラム内に __直接記述__ する場合は、__記述が長く__、見た目が __わかりづらい__ という __大きな欠点__ があります。

# 座標を表すデータ構造その 1（Excel 座標）

Excel という表計算ソフトでは、表のセル（マスのこと）を __A1__ のように、__列__ を表す __アルファベット__ と、__行__ を表す __整数__ を __並べる__ ことで表記します。そこで、座標を表す下記のようなデータ構造を考え、__Excel 座標__[^1] と表記することにします。

:::note warn
__Excel 座標__ の __データ構造__ を以下のように __定義__ する。

* __x 座標__ を、__x 番目__ の __大文字のアルファベット__ で表現する。ただし、__一番左の列__ に対応するアルファベットを __`"A"`__ とする
* __y 座標__ を __整数__ を表す __文字列__ で表現する。ただし、__一番上の行__ を __`"1"`__ とする
* __x 座標__ を表す __アルファベット__ と、__y 座標__ を表す __整数__ を __並べた文字列__ を座標を表すデータとする
:::

Excel 座標では、__y 座標__ を 0 からではなく、__1 から数える点__ に注意して下さい。

:::note
本記事では扱いませんが、xy 座標のように、y 座標を __0 から数える__ ような座標を使っても __構いません__。また、x 座標を __小文字__ で表現したり、__ひらがななど__ で表現しても __構いません__。興味と余裕がある方はチャレンジしてみて下さい。
:::

:::note
__チェス__ でも同様の方法でマスの座標を表現しますが、__x 座標__ を __小文字で表現__ する点と、__y 座標__ を、__一番下__ の行を 1 とし、__上に向かって__ 数字を __増やしていく__ という点が異なるようです。詳しくは下記のリンク先を参照して下さい。

__オセロ__（リバーシ）の場合は、__x 座標__ を __小文字で表現__ する点を除けば、__Excel 座標と同じ方法__ でマスの座標を表現するようです。詳しくは下記のリンク先を参照して下さい。
:::

https://en.wikipedia.org/wiki/Chess

https://en.wikipedia.org/wiki/Reversi

Excel 座標で、〇× ゲームのゲーム盤の 9 つのマスの座標は、下図のように表記します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/108ee683-e40a-9935-43fa-e728537fb162.png" width="150">

下記は、テストケースの中の、xy 座標を表すデータを、Excel 座標に __置き換えた__ プログラムです。元のプログラムと比較して、__簡潔__ に、__わかりやすく__ 記述することが出来るようになります。また、__複数の座標__ を表すデータの __データ構造__ が、元は __2 次元配列__ を表す list であったのが、__1 次元配列__ の list になっており、__簡潔__ になっています。

```python
from marubatsu import Marubatsu

testcases = [
    # 〇 の勝利のテストケース
    [                                      # 着手順とゲーム盤
        [ "A1", "A2", "B1", "B2", "C1" ],  # 135  ooo
        Marubatsu.CIRCLE,                  # 24.  xx. 
    ],                                     # ...  ...
    # × の勝利のテストケース
    [                                            # 着手順とゲーム盤
        [ "A2", "A1", "B2", "B1", "A3", "C1" ],  # 246  xxx 
        Marubatsu.CROSS,                         # 13.  oo.
    ],                                           # 5..  ...
    # 引き分けのテストケース
    [                                                              # 着手順とゲーム盤
        [ "A1", "A2", "B1", "B2", "C2", "C1", "A3", "B3", "C3" ],  # 136  oox 
        Marubatsu.DRAW,                                            # 245  xxo
    ],                                                             # 789  oxo
]
```

## Excel 座標の利点と欠点

Excel 座標の主な利点と欠点は以下の通りです。

__利点__

* 〇×ゲームの場合は、2 文字の文字列で __簡潔に表記できる__
* アルファベットと数値という __異なる方法__ で x 座標と y 座標を __記述__ しているので、どの文字が x 座標と y 座標を表しているかを __一目で区別__ できる
* 同様の理由で、x 座標と y 座標を表す文字列を、数学の座標の `(0, 1)` のように、`,` などの __記号で区切らず__ に、__直接並べて短く記述__ することが出来る。
* Excel 座標の表記に慣れれば、__直観的でわかりやすい__
* 複数の Excel 座標を表すデータを __1 次元配列__ を表す __list で表現__ できる

__欠点__

* x 座標と y 座標を表すデータを __1 つの文字列で表現__ しているので、`move` メソッドの仮引数のように、x 座標と y 座標を __別々に扱う必要がある__ 際に __利用しづらい__
* 慣れるまでは、アルファベットで記述された __x 座標__ の __意味__ が __理解しづらい__
* __x 座標__ を __アルファベットで表現__ しているので、__元の整数__ の x 座標を __利用したい__ 場合は、アルファベットを整数の座標に __変換__ する必要がある

上記のように、Excel 座標は、__データの記述が簡潔__ であるという利点がある反面、そのデータをプログラムで利用する際に __何らかの処理が必要__ になります。

## データの変換

Excel 座標で記述したテストケースでは、座標を表す __データ構造が変わった__ ので、それに合わせて __プログラムを修正__ する必要があります。

修正する方法として、`Marubatsu` クラスの `move` メソッドや `place_mark` メソッドなど、__xy 座標__ を使って __処理__ が行われている __部分をすべて__、__Excel 座標__ 使って __処理を行う__ ように __修正__ するという方法が考えられます。しかし、先程の利点と欠点の所で説明したように、Excel 座標は、データをプログラムに直接 __記述する際は便利__ ですが、Excel 座標のデータをプログラム内で __利用する際__ は、__xy 座標と比較__ すると __不便__ です。

他の修正方法としては、__Excel 座標__ を、__xy 座標__ に __変換__ する __関数を定義__ して利用するという方法があります。こちらの方法であれば、これまでに記述した xy 座標で処理を行う部分のプログラムを __修正__ する __必要はありません__。別の言葉で説明すると、__データの記述__ は __Excel 座標__ で __簡潔に記述__ し、__データの処理__ は __xy 座標__ を使って行うという、両者の __良い所取り__ をするという方法です。本記事では、こちらの方法を採用することにします。

## 関数の仕様

そのような関数を定義するためには、関数の名前、入力、処理、出力 の 仕様を決める 必要があり、本記事では、それぞれを以下のように決めることにします。

* __関数の名前__：Excel 座標を xy 座標に変換するので、__`excel_to_xy`__ にする
* __入力__：__座標__ を表す coordinates という英単語を略した、__`coord`__ という名前の __仮引数__ に、__Excel 座標を代入__ する
* __処理__：Excel 座標を xy 座標に __変換__ する
* __出力__：__返り値__ として、__xy 座標を返す__

具体的には、下記のような関数を定義することにします。

```python
def excel_to_xy(coord):
    coord を xy 座標に変換する処理
    return [x, y]
```

`excel_to_xy` の実装が __完了した後__ で、`test_judge` メソッド内の、__xy 座標__ を使ってマスに __マークを配置__ する、下記の部分の __処理を修正__ する必要があります。`excel_to_xy`  を使って、どのように修正すれば良いかについて少し考えてみて下さい。

```python
        for x, y in testdata:
            mb.move(x, y)
```

__`testdata`__ には、`[ "A1", "A2", "B1", "B2", "C1" ]` のような、__Excel 座標を要素__ として持つ __list が代入__ されています。従って、上記の for 文を __`for coord in testdata:`__ のように __修正__ することで、__先頭の要素__ から __順番__ に、__`coord`__ に __Excel 座標を代入__ して __繰り返し処理__ を行うことができます。

for 文のブロックの中では、先ほど定義した、__`excel_to_xy`__ の実引数に __`coord`__ を記述して __呼び出す__ ことで、__Excel 座標__ を __xy 座標__ に __変換__ することができます。

下記のプログラムは、そのように修正したプログラムです。__`excel_to_xy` を定義して利用__ することで、下記以外の __修正__ を一切行う __必要がなくなります__。

```python
        for coord in testdata:
            x, y = excel_to_xy(coord)
            mb.move(x, y)
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
-       for x, y in testdata:
+       for coord in testdata:
+           x, y = excel_to_xy(coord)
            mb.move(x, y)

```
</details>

なお、`x, y = excel_to_xy(coord)` の部分は、`excel_to_xy` の __返り値__ が、__list__ でも __tuple__ でも __同じ処理__ が行われます。そのため、`excel_to_xy` の `return` 文を、__`return x, y`__ のように記述して、__tuple を返す__[^2]ように __変更__ しても __同一の処理__ が行われます。こちらの場合は、`[]` を記述する必要がない点と、__実際に良く記述される__ ので、本記事でも下記のように、関数の返り値を __`return x, y`__ のように記述することにします。

```python
def excel_to_xy(coord):
    coord を xy 座標に変換する処理
    return x, y
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def excel_to_xy(coord):
    coord を xy 座標に変換する処理
-   return [ x, y ]
+   return x, y
```
</details>


次に、`excel_to_xy` の定義を記述します。この関数の定義のブロックに、どのようなプログラムを記述すれば良いかについて少し考えてみて下さい。

## アルゴリズムとは何か

アルゴリズムとは、__何らかの処理__ を行うための __手順__ のことを表します。__同じ処理__ に対して、__様々なアルゴリズム__ を考えることが出来ますが、アルゴリズムの __種類__ によって、処理の記述のしやすさ、処理にかかる時間などの __性質が異なります__。

現実の例で例えると、東京から大阪まで旅行する場合の事を考えてみて下さい。旅行するための __方法__ のが __アルゴリズムに相当__ します。旅行する方法としては、「飛行機で行く」、「新幹線で行く」、「長距離バスで行く」、「車で行く」、「バイクで行く」、「自転車で行く」、「歩いていく」など、__様々な方法__ が考えられます。また、__同じ__「車で行く」の場合でも、どの道で行くかによって、__様々な方法__ が考えられます。それぞれの方法によって、「費用」、「時間」、「疲れ」などの __性質が異なる__ ので、旅行を行う際には、それらの方法の __性質__ と、旅行を行う際の __自分の都合__ を __考慮__ して、__最もふさわしい__ と __自分で考えた方法__ を __選択する__ ことになるはずです。

プログラミングを学ぶ際に、__アルゴリズムを学ぶことが重要__ であると良く言われるのは、__様々なアルゴリズムを学ぶ__ ことで、__自分が行いたい処理__ を __実装する__ ために __ふさわしい__ アルゴリズムを、__自分で選択__ してプログラミングを行うことが __出来るようになる__ からです。例えば、上記の旅行の例で、__お金をかけずに1日以内__ で旅行したい場合、格安の長距離バスがあることを __知っていれば__ 、それを __選択して__ 安く旅行することが __できます__ が、そのことを __知らなければ__、別の __より高い方法__ しか選択することはできません。

本記事では、__同じ処理__ に対して __様々な__ アルゴリズムが __存在する例__ として、`excel_to_xy` を様々なアルゴリズムで実装し、それらの __利点__ と __欠点__ について説明します。

## アルゴリズムとデータ構造

同じ処理であっても、データを表す __データ構造__ が異なれば、__アルゴリズム__ も __異なります__。例えば、xy 座標から、x 座標と y 座標を取り出して利用する場合は、下記のプログラムのような代入文を使ったアルゴリズムを利用することが出来ます。

```python
coord = [0, 1]
x, y = coord
```

また、下記のプログラムのように、それぞれの要素を __個別に変数に代入する__ というアルゴリズムも考えられるでしょう。

```python
coord = [0, 1]
x = coord[0]
y = coord[1]
```

一方、Excel 座標の場合は、上記のアルゴリズムは __いずれも__ 利用することは __できません__。

このように、__アルゴリズムとデータ構造__ は、__セットになる概念__ です。従って、プログラミングを学ぶ際には、アルゴリズムとデータ構造の __両方を学ぶ__ ことが __重要__ です。

今回の記事では、Excel 座標というデータ構造に対するアルゴリズムを紹介します。

## `excel_to_xy` の定義その 1（if 文を使う方法）

最も __単純__ な方法として、下記のような __if 文__ を使ったアルゴリズムが考えられます。

```python
def excel_to_xy(coord):
    if coord == "A1":
        return 0, 0
    elif coord == "A2":
        return 0, 1
    elif coord == "A3":
        return 0, 2
    elif coord == "B1":
        return 1, 0
    elif coord == "B2":
        return 1, 1
    elif coord == "B3":
        return 1, 2
    elif coord == "C1":
        return 2, 0
    elif coord == "C2":
        return 2, 1
    elif coord == "C3":
        return 2, 2
    else:
        print("invalid coord", coord)
```

上記のプログラムは、__if 文__ を使って、__`coord`__ が 〇×ゲームのそれぞれのマスの __Excel 座標と等しい__ かどうかを __チェック__ し、__等しければ__ 対応する __xy 座標__ を __`return` 文で返しています__。また、〇×ゲームの __どのマス__ の __Excel 座標__ とも __等しくなければ__、不正な（invalid）座標であることを表す __メッセージを表示__ しています。

下記のプログラムは、Excel 座標の __`"A1"`__ を `excel_to_xy` を使って __xy 座標に変換__ するプログラムです。実行結果から正しく変換できていることが確認できます。

```python
x, y = excel_to_xy("A1")
print(x, y)
```
実行結果
```
0, 0
```

なお、下記のプログラムのように、〇×ゲームのゲーム盤に __存在しない__ `"E5"` のような Excel 座標を、`excel_to_xy` を使って xy 座標に変換しようとすると、`if` 文の `else` の次の行で __`invalid coord E5`__ が __表示された後__ で、__エラーが発生__ します。

```python
x, y = excel_to_xy("E5")
print(x, y)
```
実行結果
```
invalid coord E5
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 4 line 1
----> 1 x, y = excel_to_xy("E5")
      2 print(x, y)

TypeError: cannot unpack non-iterable NoneType object
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データタイプ（type）に関するエラー
* __cannot unpack non-iterable NoneType object__
[反復可能オブジェクト](https://qiita.com/ysgeso/items/0d64d1ddba1982b5a5d3#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88)（iterable）でない（non）None（NoneType のこと）は、展開（unpack）することはできない（cannot）
:::

このエラーは、下記の `else` の行が実行された後で、__`return` 文__ を __実行せず__ に、`excel_to_xy` の __ブロックの処理が終了__ したことが原因です。 

```python
    else:
        print("invalid coord", coord)
```

[以前の記事](https://qiita.com/ysgeso/items/95282cb1532602799052#%E5%87%BA%E5%8A%9B%E3%81%8C%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E9%96%A2%E6%95%B0) で説明したように、__`return` 文を実行せず__ に __関数__ のブロックの __処理が終了__ すると、__返り値__ として __`None`__ が __返ります__。従って、`x, y = excel_to_xy("E5")` を呼び出すと、__`x, y = None`__ が __実行される__ ことになります。

### 反復可能オブジェクトの展開

これまで説明していませんでしたが、__`x, y = 式`__ のような __代入文__ は、__式の値__ が list や tuple、文字列型のような、__反復可能オブジェクト__ の場合に利用できます。このような、__反復オブジェクト__ の中のデータの __一部を別々に取り出して利用__ することを __展開__（unpack） と呼びます。__`None`__ は __反復可能オブジェクトではない__ ため、展開できない（cannot unpack）というメッセージが表示されるエラーが発生します。

なお、`else` のブロックの中に、下記のような return 文を記述して __tuple を返す__[^3] ようにプログラムを __修正__ することで、__エラーが発生しない__ ようにすることもできますが、`excel_to_xy` の場合は、そのような __修正__ を __行う必要はない__ と思います。

```python
    else:
        print("invalid coord", coord)
        return None, None
```

その理由は、テストケースを表すデータの中の座標に、`"E5"` のような、〇×ゲームのゲーム盤に __存在しない座標__ が __記述__ されていた場合は、__データが間違っている__ ので、そのテストケースでは __正しいテスト__ を行うことが __出来ません__。そのため、そのようなテストケースを使ってテストを行った際に、__エラーが発生__ して __プログラムが停止__ したほうが、__良い__ からです。逆に、__正しいテスト__ を行うことが __出来ない__ のに、__エラーが発生せず__、__最後まで__ プログラムが __実行される__ ことのほうが __問題がある__ でしょう。

### 動作の確認

下記のプログラムは、`test_judge` を修正したプログラムです。

```python
def test_judge(testcases):
    for testcase in testcases:
        testdata, winner = testcase
        mb = Marubatsu()
        for coord in testdata:
            x, y = excel_to_xy(coord)
            mb.move(x, y)
        print(mb)

        if mb.judge() == winner:
            print("ok")
        else:
            print("error!")
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def test_judge(testcases):
    for testcase in testcases:
        testdata, winner = testcase
        mb = Marubatsu()
-       for x, y in testdata:
+       for coord in testdata:
+           x, y = excel_to_xy(coord)
            mb.move(x, y)
        print(mb)

        if mb.judge() == winner:
            print("ok")
        else:
            print("error!")
```
</details>

下記は、`test_judge` の実引数に、__Excel 座標__ で座標を __記述__ した、先程の命令網羅(C0) の __テストケース__ を記述して __テストを行う__ プログラムです。実行結果から、Excel 座標を使ったテストケースに対して、正しくテストが行われることが確認できます。

```python
test_judge(testcases)
```
実行結果
```
Turn x
ooo
xx.
...

ok
Turn o
xxx
oo.
o..

ok
Turn x
oox
xxo
oxo

ok
```

### `excel_to_xy` に対するテストの必要性

ところで、__`excel_to_xy`__ に対して、__テストを行う必要があるのでは__ と思った人はいないでしょうか？`excel_to_xy` の場合は、`test_judge` に対して現在行っているようなテストを __行う必要はない__ と思います。その理由は、`testcases` の中の、__引き分けを表すテストケース__ には、〇×ゲームの __すべてのマスの座標__ が __含まれる__ ので、`test_judge` を実行し、__表示される__ テストケースの __ゲーム盤__ を __目で見て確認__ することで、__実質的__ に、__`excel_to_xy`__ の __[全数テスト](https://qiita.com/ysgeso/items/728cee8982fe0ed9da38#%E5%85%A8%E6%95%B0%E3%83%86%E3%82%B9%E3%83%88%E3%81%A8%E6%8A%9C%E3%81%8D%E5%8F%96%E3%82%8A%E3%83%86%E3%82%B9%E3%83%88)__ を行っていると __みなすことが出来る__ からです。

従って、上記のプログラムの実行は、`test_judge` だけでなく、__`excel_to_xy` が正しく動作__ するかどうかの __確認__ を __兼ねています__。__`ok` が表示__ されることを確認する __だけでなく__、__それぞれのテストケース__ で __正しいマス__ に __マークが配置__ されているかどうかを __目で確認する__ ことを __忘れない__ で下さい。

このように、定義した __すべての関数__ に対して __詳細なテスト__ を行うのは __手間がかかりすぎる__ ので、テストを行うまでもないような __単純な関数__ や、上記のような __他の手段__ で __テストを代替__ できる場合などでは、__テストを省略__ することが良くあります。

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* 行っている処理の __意図__ が __わかりやすい__

__欠点__

* プログラムの __記述が長く__、__大変__
* __すべての座標__ に __対応__ する __条件式__ を __記述__ する必要がある
* 行っている処理の意図はわかりやすいが、__具体的__ に行われる __処理を理解__ するために、if 文のそれぞれの条件文とブロックの処理を見る必要がある点では __わかりづらい__

## `excel_to_xy` の定義その 2（テーブルを使う方法）

__if 文__ を使った `excel_to_xy` の __アルゴリズム__ は、行っている処理の意図が __わかりやすい__ という __利点__ がありますが、__記述が長くなる__ という __欠点__ があります。

そこで、if 文 より __簡潔に記述__ できる __アルゴリズム__ をいくつか紹介します。

`excel_to_xy` が行う処理は、__Excel 座標__ から __xy 座標__ への __対応づけ__ です。これは、[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93%E3%81%AE%E6%84%8F%E5%91%B3) で説明した、__名前からオブジェクト__ への __対応づけ__ を行う、__名前空間__ と __似ている__ と思いませんか？また、[以前の記事](https://qiita.com/ysgeso/items/44884dcf168aab949508#dict-%E3%81%AB%E3%82%88%E3%82%8B%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93%E3%81%AE%E7%AE%A1%E7%90%86) で行った、__名前空間__ は、__dict__ を使って __実現されている__ という説明を思い出してください。

__Excel 座標__ が __文字列で表現__ されることと、dict の __キー__ に __文字列を利用できる__ ことから、__dict を使う__ ことで、__Excel 座標__ から __xy 座標__ への __対応づけ__ を __表現__ することが __できます__。具体的には、dict の __キー__ に __Excel 座標__ を、その __キーの値__ に対応する __xy 座標__ を __代入__ することで、下記のプログラムのように、__Excel 座標__ と __xy 座標__ を __対応付け__ ます。

```python
excel_to_xy_table = {
    "A1": [0, 0],
    "A2": [0, 1],
    "A3": [0, 2],
    "B1": [1, 0],
    "B2": [1, 1],
    "B3": [1, 2],
    "C1": [2, 0],
    "C2": [2, 1],
    "C3": [2, 2],
}
```

このような対応づけは、下記のような __表__（table）を __作っている__ ようなものなので、この対応づけを表す dict を代入する __変数の名前__ は、__`excel_to_xy_table`__ という名前にしました。また、このような __データ__ から __別のデータ__ への __対応づけ__ を目的とする __データ__ の事を、__テーブル__ と呼ぶことがあるので、本記事でもそのように表記します。

| excel 座標 | xy 座標 |
|:-:|:-:|
| `"A1"`  | `[0, 0]` |
| `"A2"`  | `[0, 1]` |
| 略  | 略  |
| `"C3"`  | `[2, 2]` |

このデータを使って `excel_to_xy` を下記のプログラムのように定義することが出来ます。なお、先ほどの `excel_to_xy_table` は、この関数の __ローカル変数__ としています。

```python
def excel_to_xy(coord):
    excel_to_xy_table = {
        "A1": [0, 0],
        "A2": [0, 1],
        "A3": [0, 2],
        "B1": [1, 0],
        "B2": [1, 1],
        "B3": [1, 2],
        "C1": [2, 0],
        "C2": [2, 1],
        "C3": [2, 2],
    }
    return excel_to_xy_table[coord]
```

下記のプログラムを実行することで、修正した `excel_to_xy` が正しく動作することが確認できます。その際に、__テストケース__ の __データ構造__ は __変更されていない__ ので、__`test_judge`__ を __変更__ する必要は __ありません__。なお、実行結果は先ほどと __同じ内容__ になるので __省略__ します（github の方では、下記のプログラムを実際に実行します）。

```python
test_judge(testcases)
```

:::note
このアルゴリズムの場合も、〇×ゲームのゲーム盤に __存在しない__ `"E5"` のような Excel 座標を、`excel_to_xy` を使って xy 座標に変換しようとすると、下記のプログラムのように、`"E5"` というキーが dict に存在しないという __エラーが発生__ しますが、先程と同じ理由でエラーが発生しないようにする修正は行いません。

```python
print(excel_to_xy("E5"))
```
実行結果
```
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 9 line 1
----> 1 print(excel_to_xy("E5"))

c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 9 line 1
      1 def excel_to_xy(coord):
      2     excel_to_xy_table = {
      3         "A1": [0, 0],
      4         "A2": [0, 1],
   (...)
     11         "C3": [2, 2],
     12     }
---> 13     return excel_to_xy_table[coord]

KeyError: 'E5'
```
:::

:::note
下記のプログラムのように、テーブルを表すデータを変数に代入せず、__直接 return 文に記述__ することもできます。__分かりづらい__ と思いますので初心者の方には __お勧めしません__ が、__実際に__ このような __記述が行われる__ 場合があるので紹介しました。なお、確認を行うプログラムとその実行結果は省略します。

```python
def excel_to_xy(coord):
    return {
        "A1": [0, 0],
        "A2": [0, 1],
        "A3": [0, 2],
        "B1": [1, 0],
        "B2": [1, 1],
        "B3": [1, 2],
        "C1": [2, 0],
        "C2": [2, 1],
        "C3": [2, 2],
    }[coord]
```
:::

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* if 文を使ったアルゴリズムより __記述が短い__
* __慣れれば__ Excel 座標と xy 座標の __対応__ が __わかりやすい__

__欠点__

* __すべての座標__ に __対応__ する __キーと値__ を __記述__ する必要がある
* __慣れるまで__ は、if 文を使ったアルゴリズムより __意図がわかりづらい__

## `excel_to_xy` の定義その 3（x、y 座標を分ける）

if 文を使った場合と、テーブルを使った場合は、いずれも 〇×ゲームの __全て__ のマスの __座標__ に対応する __記述を行う__ 必要があります。〇×ゲームの場合は、9 マスしかないのでそれほど大変ではありませんが、例えば $9 * 9 = 81$ マスもある将棋のようなゲーム盤の場合は、81 もの記述を行う必要があるので __大変__ です。

この問題は、__x 座標__ と、__y 座標__ のデータを __分けて処理__ を行うことで __改善__ することが出来ます。__文字列型__ のデータは、__反復可能オブジェクト__ なので、先程説明したように、下記のプログラムのように記述することで、__展開__ によって __それぞれの文字__ を __個別の変数__ に __代入__ することが出来ます。

```python
x, y = "A1"
print(x, y)
```
実行結果
```
A 1
```

上記のように記述することで、__Excel 座標__ の __x 座標__ と __y 座標__ を表す文字列を、__個別__ に __xy 座標__ に __変換する__ ことができるようになります。先ほどの __テーブル__ を使う __方法__ を利用する場合、下記のプログラムのように、2 ~ 6 行目で __Excel 座標__ の __x 座標__ を __変換するテーブル__ と、7 ~ 11 行目で __y 座標__ を __変換するテーブル__ という、__2 つのテーブル__ を用意します。13 行目で、__`x`__ と __`y`__ に、`coord` の __1 文字目__ と __2 文字目__ を __代入__ し、14 行目で、__2 つのテーブル__ を使って、__xy 座標__ を __計算__ して返しています。


```python
 1  def excel_to_xy(coord):
 2     excel_to_x_table = {
 3         "A": 0,
 4         "B": 1,
 5         "C": 2,
 6     }
 7     excel_to_y_table = {
 8         "1": 0,
 9         "2": 1,
10         "3": 2,
11     }
12
13     x, y = coord
14     return excel_to_x_table[x], excel_to_y_table[y]
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def excel_to_xy(coord):
    excel_to_x_table = {
        "A": 0,
        "B": 1,
        "C": 2,
    }
    excel_to_y_table = {
        "1": 0,
        "2": 1,
        "3": 2,
    }

    x, y = coord
    return excel_to_x_table[x], excel_to_y_table[y]
```
</details>

### テーブルの項目数の比較

上記のように、x 座標と y 座標の 2 つのテーブルに __分離__ することで、テーブルの中の __項目数__ を 9 個から、$3 + 3 = 6$ 個に __減らす__ ことが出来ます。

ゲーム盤の __縦横のサイズ__ を $n$ とした場合、__分離しない場合__ のテーブル内のデータの数は $n * n$ になりますが、__分離した場合__ は $n * 2$ となり、下の表のように、$n$ が __大きく__ なればなるほど、__その差__ は __大きく__ なります。

| n | 分離しない場合 | 分離する場合 | ゲームの例 |
|--:|--:|--:| :-: |
| 3  |  9 |  6 | 〇×ゲーム |
| 8  | 64  | 16  | オセロ |
| 9  | 81  | 18  | 将棋 |
| 19  | 381  | 38  | 囲碁 |
| 100  | 10000  | 200  |     |

下記のプログラムを実行することで、修正した `excel_to_xy` が正しく動作することが確認できます。実行結果は先程と同様になるので省略します。

```python
test_judge(testcases)
```

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* 1 つのテーブルを使ったアルゴリズムよりは __記述が短い__
* テーブルの項目数の合計が少なくなる
 
__欠点__

* __慣れるまで__ は、1 つのテーブルを使ったアルゴリズムより __意図がわかりづらい__

## `excel_to_xy` の定義その 4（y 座標を計算で変換する）

その 3 の `excel_to_xy` 定義で、__y 座標__ を __テーブル__ を使って __変換__ するのが __馬鹿らしいと__ 思った人はいませんか？具体的には、__Excel 座標__ の y 座標を表す __2 文字目__ に対応する __xy 座標__ の __y 座標__ は、いずれも __値が 1 つ小さくなる__ ので、`excel_to_xy` の __return 文__ を、下記のように __修正__ すれば良いと思った人がいるのではないでしょうか？。

```python
    return excel_to_x_table[x], y - 1
```

実際に、上記のように `excel_to_xy` の定義を修正して、下記のプログラムを実行すると、実行結果のような __エラーが発生__ します。なお、今後は、__エラーメッセージが長い__ 場合は、下記の実行結果のように、__一部を省略__ することにします。

```python
test_judge(testcases)
```

実行結果
```
略
c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 16 line 9
      2 excel_to_x_table = {
      3     "A": 0,
      4     "B": 1,
      5     "C": 2,
      6 }
      8 x, y = coord
----> 9 return excel_to_x_table[x], y - 1

TypeError: unsupported operand type(s) for -: 'str' and 'int'
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（type）に関するエラー
* __unsupported operand type(s) for -: 'str' and 'int'__
文字列型（str）と（and）整数型（int）に対する（for）`-` 演算子（operand）による演算を行うことはできない（unsupported）
:::

このエラーは、__`y`__ に代入されている __文字列型__ のデータから、__`1`__ という __整数型__ のデータを __`-` 演算子__ で __減算__ しようとしている点が原因です。別の言葉で説明すると、Python では、__文字列__ と __数値__ を __`-` 演算子__ で減算 __できない__ ということです。

### 明示的な型変換と、暗黙の型変換

このエラーを修正するためには、__文字列型__ の __`y`__ を、__数値型__ のデータに __変換__ する必要があります。__整数型__ へのデータの __変換__ は、[以前の記事](https://qiita.com/ysgeso/items/a189461ae32a6531ff7f#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E5%9E%8B%E3%81%AE%E5%A4%89%E6%8F%9B) で説明したように、__`int`__ という組み込み関数を使って行うことが出来るので、下記のプログラムのように `excel_to_xy` の return 文で `y` を __`int(y)`__  のように修正することでエラーが発生しなくなります。なお、__必要が無くなった__ ので、__`excel_to_y_table`__ は __削除__ しました。

```python
def excel_to_xy(coord):
    excel_to_x_table = {
        "A": 0,
        "B": 1,
        "C": 2,
    }
    x, y = coord
    return excel_to_x_table[x], int(y) - 1
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def excel_to_xy(coord):
    excel_to_x_table = {
        "A": 0,
        "B": 1,
        "C": 2,
    }
-   excel_to_y_table = {
-       "1": 0,
-       "2": 1,
-       "3": 2,
-   }

    x, y = coord
-   return excel_to_x_table[x], y - 1
+   return excel_to_x_table[x], int(y) - 1
```
</details>

`int` などを使って、__意図的__ にデータの型変換を行うことを __明示的な型変換__ と呼びます。

一方、JavaScript など、プログラム言語によっては、数値型のデータと文字列型のデータを `-` 演算子で __減算できる__ 場合があります。そのような場合は、どちらかのデータ型が、もう片方のデータ型に __自動的に変換__ されて計算が行われます。

__異なるデータ型__ に対して __演算を行う__ 際に、__自動的__ に行われる __データ型の変換__ のことを、__暗黙の型変換__ と呼びます。

:::note
必要になった時点で詳しく説明しますが、Python でも、__整数型__ と __浮動小数点数型__ のデータを演算する場合などで、__暗黙の型変換が行われる__ 場合があります。
:::


下記のプログラムを実行することで、修正した `excel_to_xy` が正しく動作することが確認できます。実行結果は先程と同様になるので省略します。

```python
test_judge(testcases)
```

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* __y 座標__ に関する __テーブル__ が __必要なくなり__、プログラムを __短く記述__ できる

__欠点__

* y 座標の値を計算する際の、__`1` を減算__ する処理の __意図がわかりづらい__

:::note
__`x, y = coord`__ によって、__Excel 座標__ の x 座標と、y 座標を表す文字列を、`x` と `y` に __代入できる__ のは、__〇×ゲーム__ では、Excel 座標の __x 座標__ と、__y 座標__ を表す文字列が、__必ず 1 文字__ であるからです。例えば、囲碁のような、ゲーム盤のサイズが 19 もあるようなゲーム盤の場合は、Excel 座標が __`"A19"`__ のように __3 文字以上__ になってしまう場合があます。実際に `x, y = "A19"` を実行すると、__文字数が 3__ であるのに対して、__代入__ する __変数の数__ が __2 つしかない__ ため、下記のプログラムの実行結果のように __エラーが発生__ します。

```python
x, y = "A19"
```
実行結果
```
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 19 line 1
----> 1 x, y = "A19"

ValueError: too many values to unpack (expected 2)
```

上記のエラーメッセージは、以下のような意味を持ちます。

* __ValueError__
値（文法のこと）（syntax）に関するエラー
* __too many values to unpack (expected 2)__
展開（unpack）するデータの値の数（values）が、期待された 2（expected 2）より多い（too many）

そのような場合は、正規表現などの、__別の方法を使う__ 必要がある点に注意が必要です。長くなるので今回の記事ではプログラムの意味は説明しませんが、正規表現を使う場合は、下記のプログラムのように記述します。

```python
import re # 正規表現を利用するためのモジュールをインポートする

def excel_to_xy(coord):
    excel_to_x_table = {
        "A": 0,
        "B": 1,
        "C": 2,
    }

    # 正規表現を使って、Excel 座標のアルファベットの部分と整数の部分を分離する
    m = re.fullmatch("([A-Z]+)(\d+)", coord)
    # 分離したデータを x と y に代入する
    x = m.group(1)
    y = m.group(2)
    return excel_to_x_table[x], int(y) - 1
```

下記のプログラムは、上記の `excel_to_xy` を使って、`"A19"` を xy 座標に変換しています。実行結果から正しく変換できることが確認できます。

```python
print(excel_to_xy("A19"))
```
実行結果
```
(0, 18)
```

__正規表現__ は文字列の中から、__特定のパターン__ を持つ文字列を __検索__ したり、__置換__ したりすることが出来る __非常に強力__ で __便利__ な __機能__ ですが、__使いこなす__ にはある程度の __勉強が必要__ です。本記事では必要になった時点で紹介するかもしれませんが、自分で勉強したい方は下記のリンク先などを参照して下さい。
:::

https://docs.python.org/ja/3/library/re.html

## `excel_to_xy` の定義その 5（文字列のテーブルを利用する）

実は、Excel 座標の __x 座標__ のほうも、__テーブルを使わず__ に xy 座標に __変換__ することが出来ます。そのうちの一つの方法は、__文字列型__ のデータに対して利用できる、__`index` メソッド__ を利用する方法です。`index` メソッドは、__実引数__ に記述した __文字列__ が、インスタンスの __何番の文字列__ であるかを計算して __返す__ メソッドです。ただし、その際に __先頭の文字__ を __0 番__ と __数える__ 点に注意して下さい。例えば、下記のプログラムは、`"A"` という文字列が、`"ABC"` という文字列の何番に存在するかを計算しますが、`"A"` は `"ABC"` の __先頭の 0 番__ に存在するので、実行結果に `0` が表示されます。

```python
"ABC".index("A")
```
実行結果
```
0
```

:::note
文字列の中に、`index` メソッドの実引数に記述された文字が __複数存在__ した場合は、__先頭から__ 探して __最初に見つかった文字__ の番号が返されます。
:::

__Excel 座標__ の x 座標の `"A"`、`"B"`、`"C"` は、__xy 座標__ の x 座標の `0`、`1`、`2` に __対応する__ ので、__`"ABC"`__ に対して __`index` メソッド__ を使って `"ABC".index(coord)` のように記述することで、「__Excel 座標__ の x 座標」を「__xy 座標__ の x 座標」に __変換__ することが出来ます。下記のプログラムは、そのように `excel_to_xy` メソッドを修正したプログラムです。なお、必要が無くなったので、`excel_to_x_table` は削除しました。

```python
def excel_to_xy(coord):
    x, y = coord
    return "ABC".index(x), int(y) - 1
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def excel_to_xy(coord):
-   excel_to_x_table = {
-       "A": 0,
-       "B": 1,
-       "C": 2,
-   }
    x, y = coord
-   return excel_to_x_table[x], int(y) - 1
+   return "ABC".index(x), int(y) - 1
```
</details>


そのように見えないかもしれませんが、この方法も __`"ABC"`__ という、一種の __テーブル__ を使って、Excel 座標の x 座標から、xy 座標の x 座標を __対応づけ__ ています。

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* dict の __テーブル__ が __必要なくなり__、プログラムを __短く記述__ できる

__欠点__

* x 座標の値を計算する処理の __意図がわかりづらい__
* `"ABC"` のような、__文字列のテーブルが必要__ なので、__x 座標の数が多い__、将棋のようなゲーム盤の場合は、`"ABCDEFGHI".index(coord)` のような __長い記述__ を行う必要がある

### 簡潔な記述の欠点

この修正で、`excel_to_xy` を __たった 2 行__ でかなり __簡潔に記述__ することが出来るようになりましたが、__簡潔に記述__ するとプログラムが __わかりにくくなる__ 場合が多いという __欠点__ があります。例えば、__if 文__ で記述した `excel_to_xy` は、プログラムは長いですが、__初心者でも__ 何を行うプログラムであるかを __理解することは難しくないでしょう__。一方、上記の 2 行で記述した `excel_to_xy` が何を行っているかを、__一目で理解する__ ことはそれほど __簡単ではない__ と思います。

例えば、`excel_to_xy` を下記のプログラムのように __1 行__ で __まとめる__ ことも可能ですが、__さらにわかりづらい__ プログラムになっていると思いませんか？下記のプログラムはわかりづらいので、本記事では採用しないことにします。

```python
def excel_to_xy(coord):
    return "ABC".index(coord[0]), int(coord[1]) - 1
```

## `excel_to_xy` の定義その 6（`ord` を利用する）

__初心者__ がこの方法を __思いつく__ ことは __困難__ だと思いますが、__文字コード表の知識__ と、組み込み関数 __`ord`__ を知っていれば、`"ABC"` のような文字列のテーブルを __使わず__ に __Excel 座標__ の x 座標を、__xy 座標__ の x 座標に __変換__ することが出来ます。

コンピューターでは、一つ一つの __文字__ を __整数__ で表現しています。文字と整数の __対応づけ__ は、__文字コード表__ という表を使って行われ、文字に対応する整数の事を __文字コード__ と呼びます。文字の中で __半角の文字__ に対しては、__ASCII 文字コード表__ が使われます。

ASCII 文字コード表では、下記のリンク先の表からわかるように、半角の大文字のアルファベットの __`A` を `65`__ という __整数__ に __対応づけ__ ています。また、`B` は `66`、`C` は `67` のように __`A` から `Z`__ までのアルファベットは、__`65` から__ の整数に __順番に__ 対応しています。

https://ja.wikipedia.org/wiki/ASCII

組み込み関数 __`ord`__ は、__実引数__ に記述した __文字列__ に対応する __整数の文字コード__ を __返す__ 関数で、下記のプログラムのように、`"A"` を実引数として `ord` を呼び出すと、`65` が返ります。`ord` の詳細は下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/functions.html#ord

```python
print(ord("A"))
```
実行結果
```
65
```

__ASCII 文字コード表__ の __性質__ と、__`ord`__ を __組み合わせる__ ことで、`A` を `0`、`B` を `1`、`C` を `2` に __計算__ で __変換__ することが出来ます。具体的には、下記のプログラムの `ord(x) - 65` のように、__文字__ に対応づけられた __整数__ の __文字コード__ から、__`A` に対応づけられた `65`__  を __減算__ します。具体的な計算については、下記の表を見て下さい。

| `x` | `ord(x)` | `ord(x) - 65' |
|:-:|:-:|:-:|
| `"A"`  | `65`  | `0`  |
| `"B"`  | `66`  | `1`  |
| `"C"`  | `67`  | `2`  |

```python
def excel_to_xy(coord):
    x, y = coord
    return ord(x) - 65, int(y) - 1
```

### テーブルを使わない事の影響

テーブルを使わないようにプログラムを修正したことによって、`"E5"` のような、〇×ゲームのゲーム盤に __存在しない__ Excel 座標を `excel_to_xy` で xy 座標に変換しようとした際に、下記のプログラムのように __エラーが発生しなくなります__。

:::note
説明していませんでしたが、__定義その 4__ から __y 座標__ に関して __テーブルを使わなくなった__ ので、`"A5"` のような、〇×ゲームに __存在しない y 座標__ が記述された Excel 座標を `excel_to_xy` 変換しても、エラーが __発生しなくなっていました__。
:::

```python
print(excel_to_xy("E5"))
```
実行結果
```
(4, 4)
```

これは、`ort` や `int` を使って座標を変換することによって、Excel 座標の x 座標に __任意のアルファベット__ を記述した場合と、y 座標に __任意の 1 桁の整数__ を記述した場合でも、__座標の変換__ の計算を行うことが __出来てしまう__ ためです。

このように、__計算__ を使って変換を行う方法は、__テーブル__ を使って変換を行う方法と比較して、__汎用性が高くなる__ という性質がありますが、〇×ゲームのゲーム盤に存在しない座標のような、__想定外のデータ__ を変換しようとした場合の事を __考慮する__ 必要が生じます。

〇×ゲームに存在しない座標を変換しようとした際に、エラーが発生するように `excel_to_xy` を修正することもできますが、`excel_to_xy` でエラーが発生しなくとも、__変換後の xy 座標__ を使って、__`move`__ メソッドを __実行__ すると、下記のプログラムのように __エラーが発生__ するので、今回の記事では `excel_to_xy` の修正は行いません。その方法については、今後の記事で、同様の処理を行う必要が出てきた場合に紹介します。

なお、下記のプログラムでは `x` と `y` に `4` が代入された結果、`place_mark` のブロックの中で、`self.board[x][y]`、すなわち `self.board[4][4]` という、__範囲外のインデックス__ を使って list の要素を参照することになる、IndexError が発生します。

```python
mb = Marubatsu()
x, y = excel_to_xy("E5")
mb.move(x, y)
```
実行結果
```
略
File c:\Users\ys\ai\marubatsu\027\marubatsu.py:69, in Marubatsu.place_mark(self, x, y, mark)
     50 def place_mark(self, x: int, y: int, mark: str) -> bool:
     51     """ ゲーム盤の指定したマスに指定したマークを配置する.
     52 
     53     (x, y) のマスに mark で指定したマークを配置する.
   (...)
     66         マークを配置できた場合は True、配置できなかった場合は False
     67     """
---> 69     if self.board[x][y] == Marubatsu.EMPTY:
     70         self.board[x][y] = mark
     71         return True

IndexError: list index out of range
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __IndexError__
インデックス（index）に関するエラー
* __list index out of range__
list のインデックス（index）が範囲外（out of range）である
:::

### 利点と欠点

このアルゴリズムの主な利点と欠点は以下の通りです。

__利点__

* __テーブル__ が __完全に必要なくなり__、プログラムを __最も短く記述__ できる
* アルファベットと整数を並べた座標であれば変換できるので、__汎用性が高くなる__

__欠点__

* プログラムを記述するために、__文字コード__ と __`ord`__ の __知識が必要__ になる
* プログラムの __意図__ が最も __わかりづらい__
* __想定しない__ Excel 座標に対する __対処が必要__ になる場合がある

## どのアルゴリズムを選ぶべきか

今回の記事で紹介した __どの__  `excel_to_xy` を __使っても__ 正しい __計算を行う__ ことが __可能__ なので、__どれを選んでも構いません__。ただし、慣れないうちに、__自分が理解できない__ ようなプログラムを記述すると、__後でバグが発生__ した時に __手に負えなくなる__ 可能性が高いので、__自分の力だけで__ 一からプログラムを記述する場合は、慣れないうちは、__自分が理解できる__ ようなレベルのプログラムを __記述する__ ことをお勧めします。

ただし、__いつまでも__ 最初の __if 文__ を使った `excel_to_xy` のようなアルゴリズムを __記述する__ のは __効率が悪い__ ので、理解できるようになったら、短くプログラムをまとめて記述できるようなアルゴリズムに __チャレンジしてみて下さい__。

初心者の方で、文字コードの知識がある人はあまり多くないと思いますので、本記事では、`excel_to_xy` の __定義その 5__ を採用することにします。

:::note warn
勘違いする人がいるかもしれれないので補足しますが、if 文を使ったアルゴリズムが常に効率が悪いわけでは __ありません__。if 文を使ったアルゴリズムが __最も効率が良い__ 場合が実際に __良くあります__。__適切__ なアルゴリズムを __選択する能力__ を身に付けるためには、__様々なアルゴリズム__ でプログラムを __実際に記述__ し、それぞれの性質の違いを __実際に体験__ して __学ぶ必要がある__ ということです。
:::

## 小文字のアルファベットに対応する方法

本記事のプログラムでは採用しませんが、`"a5"` のような、x 座標を表すアルファベットに __小文字を記述__ できるようなプログラムを記述する方法について補足します。

文字列型のデータには、__`upper`__ という、__小文字のアルファベット__ を __大文字に変換__ した文字列を __作成して返す__ メソッドがあります。なお、`upper` は、下記のプログラムの実行結果のように、小文字のアルファベット __以外の文字__ は __変換しません__。

```python
print("a1".upper())
print("B2".upper())
```
実行結果
```
A1
B2
```

`upper` を使って、下記のプログラムのように `excel_to_xy` を修正することで、Excel 座標に小文字のアルファベットを記述できるようになります。

```python
def excel_to_xy(coord):
    x, y = coord.upper()
    return "ABC".index(x), int(y) - 1
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def excel_to_xy(coord):
-   x, y = coord
+   x, y = coord.upper()
    return "ABC".index(x), int(y) - 1

```
</details>

## `index` メソッドに関する補足

__`index` メソッド__ は、文字列型だけでなく、__list__、__tuple__ に対しても __利用__ することが __出来ます__。list、tuple に対して `index` メソッドを呼び出した場合、下記のプログラムのように、__実引数__ に記述したデータが代入されている __要素のインデックス__（index）を返すという処理が行われます。これが、このメソッドの __名前が `index`__ である __理由__ です。

```python
print([1, 2, 3].index(2)) # 1 番の要素に 2 が代入されているので、1 が返る
print((1, 2, 3).index(3)) # 2 番の要素に 3 が代入されているので、2 が返る
```
実行結果
```
1
2
```

このことは、__文字列型__ のデータでも __同様__ です。その理由は、[以前の記事](https://qiita.com/ysgeso/items/0d64d1ddba1982b5a5d3#%E4%BB%96%E3%81%AE%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88) で説明したように、文字列型のデータは __先頭の文字__ から __順番__ に、__0 から始まる整数__ の __インデックス__ が割り当てられており、list や tuple と同様に、__`[]`__ を使って、下記のプログラムのように、__インデックス番__ の __文字を参照__ することが出来るからです。

```python
print("ABC"[1]) # 1 番のインデックスのデータである "B" が表示される
```
実行結果
```
B
```

:::note
下記のプログラムのように、文字列の中に __存在しない文字列__ を、`index` メソッドの実引数に記述して呼び出すと、__エラーが発生__ します。具体例は示しませんが、__list や tuple__ に対して要素に __存在しない値__ を`index` メソッドの実引数に記述して呼び出した場合も __同様に__ エラーが発生します。
```python
"ABC".index("D")
```
実行結果
```
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\027\marubatsu.ipynb セル 36 line 1
----> 1 "ABC".index("D")

ValueError: substring not found
```

上記のエラーメッセージは、以下のような意味を持ちます。

* __ValueError__
値（value）に関するエラー
* __substring not found__
substring（`[]` の中に記述するインデックスの事）が見つからなかった（not found）
:::

# 今回の記事のまとめ

:::note warn
Excel 座標を利用することで、下記のように、xy 座標を利用した場合と比較して、__テストケース__ を __簡潔に__、__分かりやすく__ 記述できる。

```python
testcases = [
    # 〇 の勝利のテストケース
    [                                      # 着手順とゲーム盤
        [ "A1", "A2", "B1", "B2", "C1" ],  # 135  ooo
        Marubatsu.CIRCLE,                  # 24.  xx. 
    ],                                     # ...  ...
    # × の勝利のテストケース
    [                                            # 着手順とゲーム盤
        [ "A2", "A1", "B2", "B1", "A3", "C1" ],  # 246  xxx 
        Marubatsu.CROSS,                         # 13.  oo.
    ],                                           # 5..  ...
    # 引き分けのテストケース
    [                                                              # 着手順とゲーム盤
        [ "A1", "A2", "B1", "B2", "C2", "C1", "A3", "B3", "C3" ],  # 136  oox 
        Marubatsu.DRAW,                                            # 245  xxo
    ],                                                             # 789  oxo
]
```

Excel 座標を利用する場合は、後述する __Excel 座標__ を __xy 座標__ に __変換__ する __関数 `excel_to_xy` を定義__ し、下記のプログラムのように `test_judge` の 6 行目に __`x, y = excel_to_xy()` を追加するだけ__ で、他の部分を __一切変更することなく__ テストを行うことが出来る。

```python
 1  def test_judge(testcases):
 2     for testcase in testcases:
 3         testdata, winner = testcase
 4         mb = Marubatsu()
 5         for coord in testdata:
 6             x, y = excel_to_xy(coord) # この行を追加するだけで済む
 7             mb.move(x, y)
 8         print(mb)
 9
10          if mb.judge() == winner:
11              print("ok")
12         else:
13              print("error!")
```

`excel_to_xy` は様々な方法で定義することが出来るが、__工夫する__ ことで、下記のプログラムのように __簡潔に定義__ することが出来る。

```python
def excel_to_xy(coord):
    x, y = coord
    return "ABC".index(x), int(y) - 1
```
:::

長くなったので今回の記事はここまでにします。次回は、複数の Excel座標を短く記述できるデータ構造などの、他のデータ構造とそれを処理するアルゴリズムを紹介します。

# 本記事で入力したプログラム

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/027/marubatsu.ipynb

今回の記事では、marubatsu.py は更新していないので、marubatsu_new.py はありません。

以下のリンクは、今回の記事で作成した test.py です。`excel_to_xy` は定義その 5 のものを記述しますが、参考までに定義 1 ~ 4、6 は、`excel_to_xy_1`` のような名前で記述しておくことにします。

https://github.com/ysgeso/marubatsu/blob/master/027/test_new.py

# 次回の記事

https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4

[^1]:表のセルの座標を、A1 のように最初に表記したソフトは Excel ではありませんが、現在では、そのような座標を使う最も有名なソフトが Excel なので、Excel 座標と表記することにしました
[^2]:`x, y` という記述は、`(x, y)` という tuple の `()` を省略した記述です
[^3]:xy 座標に変換する座標が存在しないので、tuple の 2 つの要素を `None` にしました