ぼくの考えたKKPとKPPの実装(4) - 思うだけで学ばない日記 2.0

KPPの説明

　　KPP[PSpec][PSpec'][PPos][PPos'][OUPosB]
　= KPP[PSpec'][PSpec][PPos'][PPos][OUPosB]
　= KPP[PSpec][PSpec'][fh(PPos)][fh(PPos')][fh(OUPosB)]
　= KPP[PSpec'][PSpec][fh(PPos')][fh(PPos)][fh(OUPosB)]
※添字の順序を変更した。アドレスがprincipalか否か判定する上でP-P交換は排除しやすいので[PSpec'][PSpec]を先頭に持ってきた方が良い。

GMA0BNの理解

先日の記事

KPPが本当に必要だったコード

原理的にはこれ↓でおk

### 同値な4アドレスを取得します。
sub get_equiv_addrs($$$$$)
{
    my ($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB) = @_;
    my @addrs;
    push @addrs, addr($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB);
    push @addrs, addr($PSpecR, $PSpecL, $PPosR, $PPosL, $OUPosB);
    my $fh_PPosL = fh($PPosL);
    my $fh_PPosR = fh($PPosR);
    my $fh_OUPosB = fh($OUPosB);
    push @addrs, addr($PSpecL, $PSpecR, $fh_PPosL, $fh_PPosR, $fh_OUPosB);
    push @addrs, addr($PSpecR, $PSpecL, $fh_PPosR, $fh_PPosL, $fh_OUPosB);
    return @addrs;
}

### 同値な4アドレスのprincipalを取得します。(単純だが低速)
sub get_principal(\@)
{
    our @addrs;
    local *addrs = $_[0];
    my $pa = $addrs[0];
    if ($addrs[1] < $pa) { $pa = $addrs[1] }
    if ($addrs[2] < $pa) { $pa = $addrs[2] }
    if ($addrs[3] < $pa) { $pa = $addrs[3] }
    return $pa;     # 同値4アドレスのうち最小のものを返す
}

### principalか否か判定します。
sub is_principal($$$$$)
{
    my ($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB) = @_;
    my @addrs = get_equiv_addrs($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB);
    my $pa = get_principal(@addrs);
    return ($addrs[0] == $pa) ? 1 : 0;
}

ただし、これは毎回4アドレスをバカ正直に生成するから遅い
先日の記事では上記コードの高速化を狙ったのであった
最終的にこうなった

### アドレスがprincipalか否か判定します。(高速版)
sub is_principal_fst($$$$$)
{
    my ($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB) = @_;

    # P-Pの交換で絞る
    if ($PSpecR < $PSpecL) { return 0 }

    # 水平反転で絞る
    if ($PSpecL != $PSpecR) {
=pod
        PSpecL < PSpecRなので、P-P交換でアドレスを減少できる可能性は無い。
        →次の2アドレスの最小値とaddr0の一致を見る。
        addr0 =    PPosL  * SzPPosSpc^2 +    PPosR  * SzPPosSpc +    OUPosB     # ~(P-P交換) & ~(水平反転)
        addr2 = fh(PPosL) * SzPPosSpc^2 + fh(PPosR) * SzPPosSpc + fh(OUPosB)    # ~(P-P交換) &  (水平反転)
=cut
        my $fhL = fh($PPosL);
        if ($fhL < $PPosL) { return 0 }
        if ($fhL == $PPosL) {
            my $fhR = fh($PPosR);
            if ($fhR < $PPosR) { return 0 }
            if ($fhR == $PPosR) {
                my $fhO = fh($OUPosB);
                if ($fhO < $OUPosB) { return 0 }
            }
        }
    } else {
=pod
        PSpecL == PSpecRなので、P-P交換でアドレスを減少できる可能性が残っている。
        →次の4アドレスの最小値とaddr0の一致を見る。
        addr0 =    PPosL  * SzPPosSpc^2 +    PPosR  * SzPPosSpc +    OUPosB     # ~(P-P交換) & ~(水平反転)
        addr1 =    PPosR  * SzPPosSpc^2 +    PPosL  * SzPPosSpc +    OUPosB     #  (P-P交換) & ~(水平反転)
        addr2 = fh(PPosL) * SzPPosSpc^2 + fh(PPosR) * SzPPosSpc + fh(OUPosB)    # ~(P-P交換) &  (水平反転)
        addr3 = fh(PPosR) * SzPPosSpc^2 + fh(PPosL) * SzPPosSpc + fh(OUPosB)    #  (P-P交換) &  (水平反転)
=cut
        #** PPosL減少チェック
        if ($PPosR < $PPosL) { return 0 }   # addr1 < addr0確定
        my $fhL = fh($PPosL);
        if ($fhL < $PPosL) { return 0 }     # addr2 < addr0確定
        my $fhR = fh($PPosR);
        if ($fhR < $PPosL) { return 0 }     # addr3 < addr0確定
        #** PPosR減少チェック
        if ($PPosR == $PPosL) {
            if ($fhL < $PPosL) { return 0 }         # addr1 < addr0確定
            if ($fhL == $PPosL) {
                #** OUPosB減少チェック
                my $fhO = fh($OUPosB);
                if ($fhO < $OUPosB) { return 0 }    # addr1 < addr0確定
            }
        }
        if ($fhL == $PPosL) {
            if ($fhR < $PPosR) { return 0 }         # addr2 < addr0確定
            if ($fhR == $PPosR) {
                #** OUPosB減少チェック
                my $fhO = fh($OUPosB);
                if ($fhO < $OUPosB) { return 0 }    # addr2 < addr0確定
            }
        }
        if ($fhR == $PPosL) {
            ($fhL == $PPosR) or die;
            if ($fhL < $PPosL) { return 0 }         # addr3 < addr0確定
            #** OUPosB減少チェック
            my $fhO = fh($OUPosB);
            if ($fhO < $OUPosB) { return 0 }        # addr3 < addr0確定
        }
    }

    return 1;       # アドレス減少余地無し(当アドレスがprincipal)
}

なお、addr()やfh()の定義はこれ

use strict;
use integer;
local $[ = 0;

sub N() { 3 }                   # 盤の大きさ
sub SzPPosSpc() { 1 + N * N }   # 駒台と盤を合わせた駒位置の数
sub SzPSpecSpc() { 1 }          # 駒の種類

### 水平反転した位置のPPosを返します。
sub fh($)
{
    use integer;
    my $PPos = $_[0];
    if ($PPos == 0) { return 0 }
    --$PPos;
    my $s = $PPos / N;
    my $d = $PPos % N;
    $s = (N - 1) - $s;
    return 1 + $s * N + $d;
}

### アドレスを返します。
sub addr($$$$$)
{
    my ($PSpecL, $PSpecR, $PPosL, $PPosR, $OUPosB) = @_;
    my $addr = $PSpecL;
    $addr *= SzPSpecSpc;
    $addr += $PSpecR;
    $addr *= SzPSpecSpc;
    $addr += $PPosL;
    $addr *= SzPPosSpc;
    $addr += $PPosR;
    $addr *= SzPPosSpc;
    $addr += $OUPosB;
    return $addr;
}

つなみに式も間違ってて、KPPの実質データ量（要素数）は

(|KPP| - |Z_g|) / 4 + |Z_g|

より多くなる
これわf(a)=f(g(a))のようにアドレス変換写像gが1種類だけなら不動点以外のアドレスが同値な2アドレスのペア（互いに相違）だけしか残らないから

実質データ量の要素数=(|fの定義域|-|Z_g|)/2 + |Z_g|

で正しいが、そうでないときはそうでないため