swiftで配列を拡張して分岐を作りたい

Question

環境:

macOS Catalina バージョン 10.15.1
Xcode Version 11.2.1

やりたい事:

Xcode の PlayGround で簡単な囲碁プログラムを作ろうとしています。

下記コードを実行すると

.........
.........
.........
.....@...
...@.oo..
.........
....o....
.........
.........

のように出力されます。

コードのコメント(1)~(5)のように対局が進む間は「着手」を「棋譜」にappendしていけばいいのですが、コメント(6)のように一旦手を戻して(7)のように別の着手をした場合に、現段階では(5)が消えてしまい、(1)(2)(3)(4)(7)と打ったように配列がなってしまいます。

これを、(1)~(5)はそれはそれで取って置き、それを消さずに(7)の変化図も記憶しておきたいのです。

つまり、

(1) -> (2) -> (3) -> (4) -> (5)
                  L> (7)

のような状態を何らかの方法で保持したいのです。

こういった場合にどんなアルゴリズムが用いられるのかをご教授願いたいです。

よろしくお願いします。

let 黒: String = "@"
let 白: String = "o"
let 空: String = "."
let 盤の大きさ: Int = 9
var 手番: String = 黒

struct 着手 {
    var 色: String
    var x: Int
    var y: Int
    init(色: String, x: Int, y: Int) {
        self.色 = 色
        self.x = x
        self.y = y
    }
}

var 棋譜: [着手] = []
var 局面: [[String]] = Array(repeating: Array(repeating: 空, count: 盤の大きさ), count: 盤の大きさ)

func 着手する(x: Int, y: Int) {
    棋譜.append(着手(色: 手番, x: x - 1, y: y - 1))
    手番 = 手番 == 黒 ? 白 : 黒
}

func 戻す() {
    let 最後の着手: 着手 = 棋譜.popLast()!
    局面[最後の着手.y][最後の着手.x] = 空
    手番 = 手番 == 黒 ? 白 : 黒
}

着手する(x: 6, y: 4)    // (1)
着手する(x: 5, y: 7)    // (2)
着手する(x: 4, y: 5)    // (3)
着手する(x: 7, y: 5)    // (4)
着手する(x: 7, y: 4)    // (5)
戻す()                  // (6)
着手する(x: 6, y: 5)    // (7)

for i in 0 ..< 棋譜.count {
    局面[棋譜[i].y][棋譜[i].x] = 棋譜[i].色
}
for y in 0 ..< 盤の大きさ {
    for x in 0 ..< 盤の大きさ {
        print(局面[y][x], separator: " ", terminator: "")
    }
    print()
}

追記、masatoUchidaさんの回答を元に考えてみたこと(2019.11.22 19:47)

なるほどと思いました。
で、「何手目か」と「分岐番号」を(何手目か, 分岐番号)で簡略的に表しながら考えてみました。

まずは初期状態から5手まで打ったのが下の0行目です。
ここで(2, 0)に戻って3手目で別の手を打ち5手目まで打ったのが1行目。
更に(1, 0)に戻って別の2手目を打って5手目まで打ったのが2行目。
で、ここからが本題です。

(3, 0)に戻って(4, 0)とは別の4手目を打った場合には(4, 3)と表すことになるのかなと思います。一旦そうします。
今度はに(3, 1)に戻って(4, 1)とは別の4手目を打った場合に(4, 4)と表すこととしたとします。
すると、一見良さそうに見えますが、この図だけから見ると(4, 4)はどこから派生したのかが分からなくなります。
つまり、(4, 4)は(3, 1)の次の手に見えますが、(3, 2)の次の手の可能性もあり得るのではないかという事です。

(0, 0) -> (1, 0) -> (2, 0) -> (3, 0) -> (4, 0) -> (5, 0) // 0行目
                           L> (3, 1) -> (4, 1) -> (5, 1) // 1行目
                 L> (2, 2) -> (3, 2) -> (4, 2) -> (5, 2) // 2行目
                                     L> (4, 3) -> (5, 3) // 3行目
                                     L> (4, 4) -> (5, 4) // 4行目

僕の理解力不足であればいいのですが。もしそうでしたらご指摘ください。

で、代案としてstruct着手に自分の通番(id)と前の着手の通番(id)を持っておくといいんじゃないかという気がしています。
まだ見えてる訳ではないのですが、その路線で進めてみようと思っています。
進展があったらご報告します。

引き続き回答、アドバイス等あればお待ちしています。

追記(2019.11.26 8:41)

MasatoUchidaさんのアドバイスを手がかりにデータの持ち方を変えてみました。
簡単のため石の色や座標は省略し、着手番号(id)と次の着手(idの配列)を持たせることにしました。
structだとエラーが出るのでclassにしてみました。
それが下のコードです。

var 通番: Int = 0
class 着手 {
    var 着手番号: Int
    var 次の着手: [着手]
    init() {
        self.着手番号 = 通番
        self.次の着手 = []
        通番 += 1
    }
    func append(次の着手: 着手) {
        self.次の着手.append(次の着手)
    }
    func print() {
        if 次の着手.count == 0 {
            Swift.print(self.着手番号)
        } else {
            for i in 0 ..< 次の着手.count {
                if 次の着手[i].着手番号 == 4 {
                }
                Swift.print(self.着手番号, " - ", separator: "", terminator: "")
                次の着手[i].print()
            }
        }
    }
}

let 棋譜 = 着手()
let A = 着手()
let B = 着手()
let C = 着手()
let D = 着手()
let E = 着手()
let F = 着手()
let G = 着手()
let H = 着手()
let I = 着手()
let J = 着手()
let K = 着手()
棋譜.append(次の着手: A)
A.append(次の着手: B)
A.append(次の着手: C)
B.append(次の着手: D)
D.append(次の着手: G)
D.append(次の着手: H)
D.append(次の着手: I)
C.append(次の着手: E)
C.append(次の着手: F)
F.append(次の着手: J)
F.append(次の着手: K)

棋譜.print()

これを実行すると、

0 - 1 - 2 - 4 - 7
4 - 8
4 - 9
1 - 3 - 5
3 - 6 - 10
6 - 11

と表示されます。
本当は

0 - 1 - 2 - 4 - 7
      |       L 8
      |       L 9
      L 3 - 5
          L 6 - 10
              L 11

のように表示させたいのですが、それは本筋とは関係ないので良しとします。

上のコードにはundo()は書いてありませんが、一つ戻るだけじゃなく任意の着手にジャンプできるので基本この形でいいのかなと思ってます。

アドバイス、回答、ありがとうございました。

ソースが汚い、無駄があるなどありましたら是非お知らせください。

Comments

[t_obara]

戻す時に、配列からpopするのではなく、戻ることを示す着手を配列に入れれば良いのでは？

[taro_nii_chan]

確かにpopしちゃったら消えちゃいますもんね。我ながら思慮不足だと思いました。
MasatoUchidaさんの回答にも同様のアドバイスがあるので、その方向で考えてみたいと思います。
ありがとうございます。

Answer 1

struct着手に何手目かと分岐番号を保持するのはいかがでしょうか。
考慮することが多そうですがそうすれば、戻した時にpopLastさせることなくどこから分岐した盤面なのか管理できるかと思います。

Comments

[taro_nii_chan]

回答ありがとうございます。とても参考になっています。
思ったところがあるのですが、回答へのコメントでは書き表しにくいので質問に追記させていただきました。
よろしければご指摘等お願いします。

[taro_nii_chan]

時間がかかってしまいましたが、おかげさまで何とか先に進めそうです。
質問に追記しましたのでよければご覧ください。

ありがとうございました。