162:). This is because an extra stone given to either player in any position can only improve that player's chances. The strategy stealing argument assumes that the second player has a winning strategy and demonstrates a winning strategy for the first player. The first player makes an arbitrary move, to begin with. After that, the player pretends that they are the second player and adopts the second player's winning strategy. They can do this as long as the strategy doesn't call for placing a stone on the 'arbitrary' square that is already occupied. If this happens, though, they can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt them, this is a winning strategy for the first player. The
446:= 9 and the board is infinite, the second player can draw via a "pairing strategy". A draw on an infinite board means that the game will go on forever with perfect play. A pairing strategy involves dividing all the squares of the board into pairs in such a way that by always playing on the pair of the first player's square, the second player is ensured that the first player cannot get
1029:
22:
450:
in a line. A pairing strategy on an infinite board can be applied to any finite board as well – if the strategy calls for making a move outside the board, then the second player makes an arbitrary move inside the
169:
This argument tells nothing about whether a particular game is a draw or a win for the first player. Also, it does not actually give a strategy for the first player.
457:≥ 8 is a draw on an infinite board. It is not clear if this strategy applies to any finite board sizes. It is not known if the second player can force a draw when
936:
858:
1072:
753:
1191:
1201:
906:
Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Winning ways for your mathematical plays, Volume 3", A K Peters (2003)
250:
Note that proofs of draws using pairing strategies also prove a draw for the weak version and thus for all smaller versions.
258:
The following statements refer to the first player in the weak game, assuming that both players use an optimal strategy.
1008:
609:
Computer search by Wei-Yuan Hsu and Chu-Ling Ko has shown that both (7,7,5) and (8,8,5) are draws, which means that (
1082:
824:, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
929:
143:
1077:
1196:
712:
that the game is a draw also when the number of cells is at least twice the number of lines, which happens
163:
651:
It is possible to consider variants played on a multidimensional board instead of a bidimensional board.
1092:
1135:
1108:
1013:
953:
922:
694:
675:
166:
implies that the original assumption is false, and the second player cannot have a winning strategy.
1129:
1067:
998:
758:
821:
875:
854:
139:
786:
1160:
1018:
846:
159:
158:-game can there be a strategy that assures that the second player will win (a second-player
1028:
988:
983:
626:
961:
713:
646:
1185:
49:
1150:
880:
738:
123:
64:
stones of their own color in a row, horizontally, vertically, or diagonally. Thus,
835:
1165:
1145:
1087:
976:
945:
508:
127:
119:
115:
65:
193:-in-a-row by the second player does not end the game with a second player win.
1140:
1113:
781:
709:
45:
850:
629:
has shown that (15,15,5) is a win, even with one of the restrictive rules of
663:
21:
1155:
743:
483:
is a draw, also by a pairing strategy in the dimension not smaller than
1170:
1123:
1059:
971:
763:
966:
748:
630:
69:
1003:
993:
874:
Hsu, Wei-Yuan; Ko, Chu-Ling; Hsueh, Chu-Hsuan; Wu, I-Chen (2018).
776:
771:
20:
918:
914:
670:, Hales and Jewett proved that the game is a draw if
504:= 2 are trivial wins, except for (1,1,2) and (2,1,2)
487:(or trivially impossible to win if both are smaller)
1101:
1036:
952:
52:take turns in placing a stone of their color on an
60:board, the winner being the player who first gets
817:
815:
636:(9,6,6) and (7,7,6) are both draws via pairings.
805:J. W. H. M. Uiterwijk and H. J van der Herik,
930:
570:≤ 5, and (6,5,4) is a win, which means that (
8:
809:, Information Sciences 122 (1) (2000) 43-58.
937:
923:
915:
173:Applying results to different board sizes
834:Uiterwijk, Jos W.H.M. (20 August 2019).
798:
554:(5,5,4) is a draw, which means that (
7:
836:"Solving Strong and Weak 4-in-a-Row"
876:"Solving 7,7,5-game and 8,8,5-game"
843:2019 IEEE Conference on Games (CoG)
122:value, the result of the game with
25:Example of a completed 11,10,5-game
18:Abstract board game for two players
235:) is a win, then any larger weak (
220:will also result in a drawn game.
14:
68:is the 3,3,3-game and free-style
1073:Harary's generalized tic-tac-toe
1027:
658:-in-a-row where the board is an
118:interest. One seeks to find the
807:The advantage of the initiative
461:is 6 or 7 on an infinite board.
223:Conversely, if weak or normal (
754:Harary's generalized tictactoe
1:
208:) is a draw, then decreasing
177:A useful notion is a "weak (
666:with all edges with length
1218:
1083:Strategy-stealing argument
644:
134:Strategy stealing argument
1025:
349:is a draw. Likewise, if (
144:combinatorial game theory
851:10.1109/CIG.2019.8848010
641:Multidimensional variant
625:≤ 8. Computer search by
72:is the 15,15,5-game. An
1192:Abstract strategy games
507:(3,3,3) is a draw (see
84:-game is also called a
1202:Partially solved games
26:
1093:Paper-and-pencil game
114:-games are mainly of
24:
1078:Hales–Jewett theorem
1014:Ultimate tic-tac-toe
442:≥ 9 is a draw: when
999:Quantum tic-tac-toe
602:≥ 9 and a draw for
598:,4,4) is a win for
283:) is a draw, then (
126:. This is known as
1136:Three men's morris
822:Jaap van den Herik
617:,5) is a draw for
562:,4) is a draw for
370:) is a win, then (
27:
1179:
1178:
1109:Nine men's morris
860:978-1-7281-1884-0
578:,4) is a win for
519:,3) is a draw if
262:If a particular (
146:shows that in no
140:strategy stealing
1209:
1068:Kaplansky's game
1037:Related concepts
1031:
1019:Wild tic-tac-toe
939:
932:
925:
916:
907:
904:
898:
897:
895:
893:
871:
865:
864:
840:
831:
825:
819:
810:
803:
759:Kaplansky's game
654:For the case of
535:,3) is a win if
492:Specific results
312:is a draw, and (
216:, or increasing
160:winning strategy
1217:
1216:
1212:
1211:
1210:
1208:
1207:
1206:
1182:
1181:
1180:
1175:
1097:
1032:
1023:
989:Order and Chaos
984:Number Scrabble
948:
943:
912:
910:
905:
901:
891:
889:
873:
872:
868:
861:
838:
833:
832:
828:
820:
813:
804:
800:
796:
791:
734:
649:
643:
627:L. Victor Allis
494:
467:≥ 3 and either
435:
424:
413:
399:is a win, and (
398:
383:
376:
369:
362:
355:
348:
337:
326:
311:
296:
289:
282:
275:
268:
256:
254:General results
189:) game", where
175:
136:
44:is an abstract
19:
12:
11:
5:
1215:
1213:
1205:
1204:
1199:
1197:In-a-row games
1194:
1184:
1183:
1177:
1176:
1174:
1173:
1168:
1163:
1158:
1153:
1148:
1143:
1138:
1133:
1126:
1121:
1120:
1119:
1111:
1105:
1103:
1099:
1098:
1096:
1095:
1090:
1085:
1080:
1075:
1070:
1065:
1057:
1040:
1038:
1034:
1033:
1026:
1024:
1022:
1021:
1016:
1011:
1006:
1001:
996:
991:
986:
981:
980:
979:
969:
964:
962:3D tic-tac-toe
958:
956:
950:
949:
944:
942:
941:
934:
927:
919:
909:
908:
899:
866:
859:
826:
811:
797:
795:
792:
790:
789:
784:
779:
774:
769:
761:
756:
751:
746:
741:
735:
733:
730:
729:
728:
714:if and only if
706:
705:
687:
686:
647:3D tic-tac-toe
642:
639:
638:
637:
634:
607:
552:
505:
493:
490:
489:
488:
462:
452:
437:
433:
422:
411:
396:
381:
374:
367:
360:
353:
346:
335:
324:
309:
294:
287:
280:
273:
266:
255:
252:
174:
171:
142:argument from
135:
132:
120:game-theoretic
17:
13:
10:
9:
6:
4:
3:
2:
1214:
1203:
1200:
1198:
1195:
1193:
1190:
1189:
1187:
1172:
1169:
1167:
1164:
1162:
1159:
1157:
1154:
1152:
1149:
1147:
1144:
1142:
1139:
1137:
1134:
1132:
1131:
1127:
1125:
1122:
1117:
1116:
1115:
1112:
1110:
1107:
1106:
1104:
1102:Similar games
1100:
1094:
1091:
1089:
1086:
1084:
1081:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1062:
1058:
1056:
1054:
1050:
1046:
1042:
1041:
1039:
1035:
1030:
1020:
1017:
1015:
1012:
1010:
1007:
1005:
1002:
1000:
997:
995:
992:
990:
987:
985:
982:
978:
975:
974:
973:
970:
968:
965:
963:
960:
959:
957:
955:
951:
947:
940:
935:
933:
928:
926:
921:
920:
917:
913:
903:
900:
887:
883:
882:
877:
870:
867:
862:
856:
852:
848:
845:. IEEE: 1–8.
844:
837:
830:
827:
823:
818:
816:
812:
808:
802:
799:
793:
788:
785:
783:
780:
778:
775:
773:
770:
768:
766:
762:
760:
757:
755:
752:
750:
747:
745:
742:
740:
737:
736:
731:
726:
722:
718:
717:
716:
715:
711:
703:
700:
699:
698:
696:
692:
684:
681:
680:
679:
677:
673:
669:
665:
662:-dimensional
661:
657:
652:
648:
640:
635:
632:
628:
624:
620:
616:
612:
608:
605:
601:
597:
593:
589:
585:
581:
577:
573:
569:
565:
561:
557:
553:
550:
546:
542:
538:
534:
530:
526:
522:
518:
514:
510:
506:
503:
499:
496:
495:
491:
486:
482:
478:
474:
470:
466:
463:
460:
456:
453:
449:
445:
441:
438:
432:
428:
421:
417:
410:
406:
402:
395:
391:
387:
380:
373:
366:
359:
352:
345:
341:
334:
330:
323:
319:
315:
308:
304:
300:
293:
286:
279:
272:
265:
261:
260:
259:
253:
251:
248:
246:
242:
238:
234:
230:
226:
221:
219:
215:
211:
207:
203:
199:
194:
192:
188:
184:
180:
172:
170:
167:
165:
164:contradiction
161:
157:
153:
149:
145:
141:
133:
131:
129:
125:
121:
117:
113:
109:
105:
100:
98:
94:
90:
88:
83:
79:
75:
71:
67:
63:
59:
55:
51:
48:in which two
47:
43:
41:
37:
33:
23:
16:
1151:Connect Four
1128:
1118:Tic-Stac-Toe
1060:
1052:
1048:
1044:
1043:
911:
902:
890:. Retrieved
885:
881:ICGA Journal
879:
869:
842:
829:
806:
801:
764:
739:Connect Four
724:
720:
707:
701:
690:
688:
682:
671:
667:
659:
655:
653:
650:
622:
618:
614:
610:
603:
599:
595:
591:
587:
583:
579:
575:
571:
567:
563:
559:
555:
548:
544:
540:
536:
532:
528:
524:
520:
516:
512:
501:
497:
484:
480:
476:
472:
468:
464:
458:
454:
447:
443:
439:
430:
426:
419:
415:
408:
404:
400:
393:
389:
385:
378:
371:
364:
357:
350:
343:
339:
332:
328:
321:
317:
313:
306:
302:
298:
291:
284:
277:
270:
263:
257:
249:
247:) is a win.
244:
240:
236:
232:
228:
224:
222:
217:
213:
209:
205:
201:
197:
195:
190:
186:
182:
178:
176:
168:
155:
151:
147:
137:
124:perfect play
116:mathematical
111:
107:
103:
101:
96:
92:
86:
85:
81:
77:
73:
61:
57:
53:
39:
35:
31:
30:
28:
15:
1166:Toss Across
1088:Futile game
977:Treblecross
946:Tic-tac-toe
509:Tic-tac-toe
138:A standard
91:game on an
66:tic-tac-toe
1186:Categories
1141:Nine Holes
1114:Score Four
892:6 November
794:References
782:Score Four
710:conjecture
645:See also:
523:< 3 or
130:the game.
46:board game
664:hypercube
527:< 3. (
436:is a win.
196:If weak (
89:-in-a-row
1156:Connect6
954:Variants
744:Connect6
732:See also
704:≥ 2 − 2.
621:≤ 8 and
590:≥ 5 and
582:≥ 6 and
566:≤ 5 and
547:≥ 4 and
539:≥ 3 and
511:), and (
500:= 1 and
1171:Pentago
1124:Gobblet
972:Notakto
787:Eternas
685:≥ 3 − 1
586:≥ 5 or
543:≥ 4 or
414:) with
388:) with
327:) with
301:) with
128:solving
99:board.
50:players
1130:Quarto
967:Gomoku
857:
749:Gomoku
689:or if
631:Gomoku
594:≥ 6. (
451:board.
70:gomoku
1055:-game
1004:Renju
994:Pente
839:(PDF)
777:Qubic
772:Pente
727:+ 2).
708:They
697:and
678:and
479:>
471:>
42:-game
1146:Achi
1063:game
894:2019
855:ISBN
767:game
695:even
606:≤ 8.
551:≥ 3.
425:and
338:and
102:The
95:-by-
56:-by-
1161:OXO
1009:SOS
888:(3)
847:doi
723:≥ (
693:is
676:odd
674:is
475:or
212:or
29:An
1188::
886:40
884:.
878:.
853:.
841:.
814:^
719:2
429:≥
418:≥
407:,
403:,
392:≤
384:,
377:,
363:,
356:,
342:≤
331:≤
320:,
316:,
305:≥
297:,
290:,
276:,
269:,
1061:n
1053:k
1051:,
1049:n
1047:,
1045:m
938:e
931:t
924:v
896:.
863:.
849::
765:n
725:k
721:k
702:k
691:k
683:k
672:k
668:k
660:n
656:k
633:.
623:n
619:m
615:n
613:,
611:m
604:m
600:m
596:m
592:n
588:m
584:n
580:m
576:n
574:,
572:m
568:n
564:m
560:n
558:,
556:m
549:n
545:m
541:n
537:m
533:n
531:,
529:m
525:n
521:m
517:n
515:,
513:m
502:k
498:k
485:k
481:n
477:k
473:m
469:k
465:k
459:k
455:k
448:k
444:k
440:k
434:0
431:n
427:n
423:0
420:m
416:m
412:0
409:k
405:n
401:m
397:0
394:k
390:k
386:k
382:0
379:n
375:0
372:m
368:0
365:k
361:0
358:n
354:0
351:m
347:0
344:n
340:n
336:0
333:m
329:m
325:0
322:k
318:n
314:m
310:0
307:k
303:k
299:k
295:0
292:n
288:0
285:m
281:0
278:k
274:0
271:n
267:0
264:m
245:k
243:,
241:n
239:,
237:m
233:k
231:,
229:n
227:,
225:m
218:k
214:n
210:m
206:k
204:,
202:n
200:,
198:m
191:k
187:k
185:,
183:n
181:,
179:m
156:k
154:,
152:n
150:,
148:m
112:k
110:,
108:n
106:,
104:m
97:n
93:m
87:k
82:k
80:,
78:n
76:,
74:m
62:k
58:n
54:m
40:k
38:,
36:n
34:,
32:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
