mtd(f) ou Pvs en finale ?
mtd(f)
Pvs avec fenêtres aspirantes
pour la recherche Gagnante/Nulle/Perdante
score = mtdf(board : b, init_g : 0, min : -1, max :1)

score = pvs(board : b, alpha : -1, beta :0);
if(score > =0)
..score = pvs(board : b, alpha : 0, beta :1);

recherche de la finale parfaite

if(score != 0) {
..if(score > 0)
....score = mtdf(board : b, init_g : score, min : score, max :64)
.. else
....score = mtdf(board : b, init_g : score, min : -64, max :score)
}

if(score != 0)
..score = pvs_Driver(board : b, init : score)

 

int mtdf(Board b, int score, int min, int max) {
..do {
....int v;
....if (score == min)
......v = score+1;
....else
......v = score;
....score = mt(b, v-1);
....if(score < v)
......max = score;
....else
......min = score;
..} while( min < max);
..return score;
}

int pvs_Driver(Board b, int score) {
..int alpha, beta;
..do{
....alpha = score-2;
....beta = score+2;
....score = pvs(b, alpha, beta);
....if(alpha == -64 || beta == 64)
......break;
..}while(alpha >= score || score >= beta);
..return score;
}

 
les finales de la FFO serviront de cadre au test, la totalité des noeuds est comptabilisée (noeuds + feuilles), et bien sûr les mêmes tris sont utilisés. Ceci dit en route...
Probleme 1
Noir doit jouer (47)
+18
G8 H7 A8 A6 A4 A7 ...
mtd(f)
Pvs
diff

G/N/P

3297
3295
2
Exacte
34861
34852
9
Total
38158
38147
11
Probleme 2
Noir doit jouer (47)
+10
A4 B7 A3 A2 B8 A7 ...
mtd(f)
Pvs
diff

G/N/P

6865
6863
2
Exacte
17919
17914
5
Total
24784
24777
7
Probleme 3
Noir doit jouer (47)
+2
D1 G1 B8 C1 G3 A8 ...
mtd(f)
Pvs
diff

G/N/P

19320
19318
2
Exacte
42072
42071
1
Total
61392
61389

3

Probleme 4
Noir doit jouer (47)
0
H8 B6 A7 H7 G7 A5 ...
mtd(f)
Pvs
diff

G/N/P

28771
28769
2
Exacte
Total
28771
28769
2
Probleme 5
Noir doit jouer (47)
+32
G8 G7 H8 G2 B2 A2 ...
mtd(f)
Pvs
diff

G/N/P

4909
4907
2
Exacte
7914
7899
15
Total
12823
12806
17
Probleme 6
Noir doit jouer (47)
+6
A1 B1 H3 H4 H6 H2 ...
mtd(f)
Pvs
diff

G/N/P

6080
6078
2
Exacte
32553
32546
7
Total
38633
38624
9
Probleme 7
Noir doit jouer (47)
+8
A6 G1 H1 B8 C8 A7 ...
mtd(f)
Pvs
diff

G/N/P

13735
13733
2
Exacte
15452
15448
4
Total
29187
29181
6
Probleme 8
Blanc doit jouer (46)
8
E1 H7 H6 G7 H8 G8 ...
mtd(f)
Pvs
diff

G/N/P

27048
27046
2
Exacte
193803
193799
4
Total
220851
220845
6
Probleme 9
Blanc doit jouer (46)
-8
A4 B7 A7 A8 B8 G8 ...
mtd(f)
Pvs
diff

G/N/P

11870
11869
1
Exacte
30979
30982
-3
Total
42849
42851
-2
Probleme 10
Blanc doit jouer (46)
+10
B2 B7 G1 G8 H8 G7 ...
mtd(f)
Pvs
diff

G/N/P

55350
55348
2
Exacte
57323
57318
5
Total
112673
112666
7
Probleme 11
Blanc doit jouer (46)
+30
B3 A3 A6 C3 B4 PS ...
mtd(f)
Pvs
diff

G/N/P

626
624
2
Exacte
64663
64649
14
Total
65289
65273
16
Probleme 12
Blanc doit jouer (46)
-8
B7 H2 A7 A8 H1 G1 ...
mtd(f)
Pvs
diff

G/N/P

43707
43706
1
Exacte
53650
53648
2
Total
97357
97354
3
Probleme 13
Noir doit jouer (45)
+14
B7 A7 A8 A6 B1 B6 ...
mtd(f)
Pvs
diff

G/N/P

118061
118059
2
Exacte
42651
42644
7
Total
160712
160703
9
Probleme 14
Noir doit jouer (45)
+18
A3 B7 A4 B2 B1 G2 ...
mtd(f)
Pvs
diff

G/N/P

10273
10271
2
Exacte
56282
56273
9
Total
66555
66544
11
Probleme 15
Noir doit jouer (45)
+4
G3 F1 B8 A8 C1 D1 ...
mtd(f)
Pvs
diff

G/N/P

176727
176725
2
Exacte
63530
63528
2
Total
240257
240253
4
Probleme 16
Noir doit jouer (45)
+24
F8 B6 A7 C7 H1 G7 H7 ...
mtd(f)
Pvs
diff

G/N/P

23748
23746
2
Exacte
190539
190527
12
Total
214287
214273
14
Probleme 17
Noir doit jouer (45)
+8
F8 F7 G8 H3 H7 B7 B2 ...
mtd(f)
Pvs
diff

G/N/P

3155
3153
2
Exacte
20770
20766
4
Total
23925
23919
6
Probleme 18
Noir doit jouer (45)
-2
G2 B7 A8 A7 G8 H1 F1 ...
mtd(f)
Pvs
diff

G/N/P

135693
135692
1
Exacte
41319
41320
-1
Total
177012
177012
0
Probleme 19
Noir doit jouer (45)
+8
B6 B5 A6 G1 H1 B8 ...
mtd(f)
Pvs
diff

G/N/P

17025
17023
2
Exacte
142960
142956
4
Total
159985
159979
6
Probleme 20
Noir doit jouer (55)
+6
H5
mtd(f)
Pvs
diff

G/N/P

21
21
0
Exacte
24
23
1
Total
45
44
1
Probleme 21
Blanc doit jouer (46)
0
G5 E8 G2 G4 H4 F8 ...
mtd(f)
Pvs
diff

G/N/P

165593
165591
2
Exacte
Total
165593
165591
2
Probleme 22
Blanc doit jouer (44)
+2
G8 D8 B8 B2 H2 H1 G1 ...
mtd(f)
Pvs
diff

G/N/P

646366
646364
2
Exacte
111146
111145
1
Total
757512
757509
3
Probleme 23
Noir doit jouer (43)
+4
A2 B7 E1 D1 F2 F1 ...
mtd(f)
Pvs
diff

G/N/P

394417
394415
2
Exacte
128415
128413
2
Total
522832
522828
4
Probleme 24
Blanc doit jouer (42)
0
C3 E1 D1 G1 A3 B2 ...
mtd(f)
Pvs
diff

G/N/P

1365678
1365676
2
Exacte
Total
1365678
1365676
2
Probleme 25
Blanc doit jouer (42)
0
A5 H1 H2 C2 D1 C1 ...
mtd(f)
Pvs
diff

G/N/P

4002802
4002800
2
Exacte
Total
4002802
4002800
2
Probleme 26
Noir doit jouer (41)
0
D8 A6 A4 D7 A5 E8 ...
mtd(f)
Pvs
diff

G/N/P

19208323
1928321
2
Exacte
Total
19208323
19208321
2
Probleme 27
Noir doit jouer (41)
-2
B7 A7 E1 B1 H2 H3 ...
mtd(f)
Pvs
diff

G/N/P

2598758
2598757
1
Exacte
1043156
1043157
-1
Total
3641914
3641914
0
Probleme 28
Noir doit jouer (41)
0
F1 A3 F2 D1 A2 A5 ...
mtd(f)
Pvs
diff

G/N/P

7938505
7938503
2
Exacte
Total
7938505
7938503
2
Probleme 29
Noir doit jouer (41)
+10
G2 G1 H1 H2 F8 D8 ...
mtd(f)
Pvs
diff

G/N/P

271618
271616
2
Exacte
1552599
1552594
5
Total
1824217
1824210
7
Probleme 30
Noir doit jouer (41)
0
G3 H4 G4 F2 H8 G8 ...
mtd(f)
Pvs
diff

G/N/P

2606304
2606302
2
Exacte
Total
2606304
2606302
2
Probleme 31
Noir doit jouer (41)
-2
G6 G4 G2 G3 H4 H1 ...
mtd(f)
Pvs
diff

G/N/P

3235123
3235122
1
Exacte
904079
904083
-4
Total
4139202
4139205
-3
Probleme 32
Noir doit jouer (41)
-4
G3 G8 F3 E8 D8 H4 ...
mtd(f)
Pvs
diff

G/N/P

2772192
2772191
1
Exacte
5358873
5358875
-2
Total
8131065
8131066
-1
Probleme 33
Noir doit jouer (41)
-8
A3 A5 A6 E7 A4 G8 ...
mtd(f)
Pvs
diff

G/N/P

3433392
3433391
1
Exacte
10220156
10220161
-5
Total
13653548
13653552
-4
Probleme 34
Noir doit jouer (41)
-2
C2 D2 A3 A2 E1 D1 ...
mtd(f)
Pvs
diff

G/N/P

7762648
7762647
1
Exacte
3659761
3659766
-5
Total
11422409
11422413
-4
Probleme 35
Blanc doit jouer (40)
0
C7 A7 A6 B8 D8 F8 ...
mtd(f)
Pvs
diff

G/N/P

6759759
6759757
2
Exacte
Total
6759759
6759757
2
Probleme 35
Blanc doit jouer (40)
0
B7 E1 C1 A8 C7 B8 ...
mtd(f)
Pvs
diff

G/N/P

26818711
26818709
2
Exacte
Total
26818711
28818709
2
Probleme 37
Noir doit jouer (39)
-20
G2 G4 H4 H1 B7 H6...
mtd(f)
Pvs
diff

G/N/P

11793004
11793003
1
Exacte
33480238
33480229
9
Total
45273242
45273232
10
Probleme 38
Noir doit jouer (37)
4
B2 C8 H2 G2 A5 A7 ...
mtd(f)
Pvs
diff

G/N/P

191245734
191245732
2
Exacte
68443389
68443387
2
Total
259689123
259689119
4
Probleme 39
Blanc doit jouer (35)
64
A8 PS B1 PS G1 G2 ...
mtd(f)
Pvs
diff

G/N/P

426
426
0
Exacte
29279024
29279009
15
Total
29279450
29279435
15
Compilation
Parties gagnantes
mtd(f)
Pvs
diff

G/N/P

193044801
193044763
38
Exacte
100497889
100497761
128
Total
293542690
293542524
166
Parties nulles
mtd(f)
Pvs
diff

G/N/P

68894446
68894428
18
Exacte
Total
68894446
68894428
18
Parties perdantes
mtd(f)
Pvs
diff

G/N/P

31786387
31786378
9
Exacte
54792211
54792221

-10

Total
86578598
86578599
-1
 
Total des parties
mtd(f)
Pvs
diff

G/N/P

293725634
293725569
65
Exacte
155290100
155289982
118
Total
449015734
449015551
183
 
Conclusion

Vous en conviendrez la différence est insignifiante, a vous d'implementer la version qui vous convient le mieux.

(pour info : les lignes principales trouvées par les deux "algo" sont identiques)



Cyrano version version 4.2.5 (01/19/2005).
Copyright 2002-2005 Bruno Causse.
All right reserved.
Othello ® is a registered trademark of Tsukuda-Original, licensed by Anjar and distributed in France by Mattel.