Busca Competitiva - Game Playing

Prévia do material em texto

?*DPH SOD\LQJ�
&DSurWXOR �� 6HFzaRHV �^�
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
9LVaDR *HUDO
` -RJDGD SHUIHLWD
` 5HVWULzFaRHV VREUH UHFXUVRV
` m^n ?SUXQLQJ�
` -RJRV GH VRUWH
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
-RJRV YV� SUREOHPDV GH EXVFD
$GYHUVuDULR ?LPSUHYLVurYHO� � VROXzFaDR uH WHU XP SODQR GH FRQWLQJAHQFLD
5HVWULzFaRHV VREUH UHFXUVRV � uH GLIurFLO HQFRQWUDU D PHWD� GHYH�VH DSUR[LPuD�OD
3ODQR GH DWDTXH�
q DOJRULWPR SDUD MRJDGD SHUIHLWD �9RQ 1HXPDQQ� �����
q KRUL]RQWH nQLWR� DYDOLDzFaDR DSUR[LPDGD �=XVH� ����� 6KDQQRQ� ����� 6DPXHO�
����^���
q ?SUXQLQJ� SDUD UHGX]LU FXVWRV �0F&DUWK\� �����
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
7LSRV GH MRJRV
determ in ístico sorte
info rm ações perfeitas
info rm ações imperfeitas
xadrez , damas,
go , o thello
gamão
B anco Im obiliário
bridge, pôquer, scrabb le
guerra nuclear
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
0LQLPD[
-RJDGD SHUIHLWD SDUD MRJRV GHWHUPLQurVWLFRV� FRP LQIRUPDzFaRHV SHUIHLWDV
,GuHLD� HVFROKHU PRYLPHQWR SDUD SRVLzFaDR FRP YDORU PLQLPD[ PDLV DOWR
 PHOKRU UHWRUQR SRVVurYHO FRQWUD PHOKRU MRJDGD
3RU H[�� MRJR GH ?��SO\��
M AX
3 12 8 642 14 5 2
M IN
3
A 1 A 3A 2
A 13A 12A 11 A 21 A 23A 22 A 33A 32A 31
3 2 2
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
$OJRULWPR PLQLPD[
IXQzFaDR 'HFLVaDR0LQLPD[�MRJR� UHWRUQD XP RSHUDGRU
SDUD FDGD RS HP 2SHUDGRUHV>MRJR@ IDzFD
9DORU>RS@‚9DORU0LQLPD[�$SOLFDU�RS� MRJR�� MRJR�
nP
UHWRUQDU D RS FRP R PDLRU 9DORU>RS@
IXQzFaDR 9DORU0LQLPD[�HVWDGR� MRJR� UHWRUQD XP YDORU XWLOLWuDULR
VH 7HVWH7HUPLQDO>MRJR@�HVWDGR� HQWaDR
UHWRUQDU 8WLOLGDGH>MRJR@�HVWDGR�
VHQaDR VH PD[ YDL VH PRYHU HP HVWDGR HQWaDR
UHWRUQDU R PDLRU 9DORU0LQLPD[ GH 6XFHVVRUHV�HVWDGR�
VHQaDR
UHWRUQDU R PHQRU 9DORU0LQLPD[ GH 6XFHVVRUHV�HVWDGR�
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
3URSULHGDGHV GH PLQLPD[
&RPSOHWD""
u2WLPD""
&RPSOH[LGDGH GH WHPSR""
&RPSOH[LGDGH GH HVSDzFR""
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
3URSULHGDGHV GH PLQLPD[
&RPSOHWD"" 6LP� VH uDUYRUH uH nQLWD �[DGUH] WHP UHJUDV HVSHFurnFDV SDUD LVVR�
u2WLPD"" 6LP� FRQWUD XP DGYHUVuDULR uRWLPR� (P RXWURV FDVRV""
&RPSOH[LGDGH GH WHPSR"" 2�EP�
&RPSOH[LGDGH GH HVSDzFR"" 2�EP� �H[SORUDzFaDR HP SURIXQGLGDGH�
3DUD [DGUH]� E { ��� P { ��� SDUD MRJRV ?UD]RuDYHLV�
� VROXzFaDR H[DWD uH FRPSOHWDPHQWH LQIDFWurYHO
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
5HVWULzFaRHV HP UHFXUVRV
6XSRQKD TXH WHP�VH ��� VHJXQGRV� SRGHP VHU H[SORUDGRV ��� QuRV�VHJXQGR
� ��� QuRV SRU PRYLPHQWR
$ERUGDJHP PDLV FRPXP�
q WHVWH GH SDUDGD �?FXWRm��
SRU H[�� OLPLWH GH SURIXQGLGDGH �WDOYH] DGLFLRQDU
EXVFD GH ?TXLHVFAHQFLD��
q IXQzFaDR GH DYDOLDzFaDR
 HVWLPDU LQWHUHVVH HP GHWHUPLQDGD SRVLzFaDR
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� �
)XQzFaRHV GH DYDOLDzFaDR
Vez do Preto
Branco um pouco melhor
Vez do Branco
Preto ganhando
3DUD [DGUH]� HP JHUDO FDOFXOD�VH XPD VRPD OLQHDU FRP SHVRV GH FDUDFWHUurVWLFDV
$YDO�V� Z�I��V� � Z�I��V� � � � � � ZQIQ�V�
SRU H[�� Z� � FRP
I��V� �QuXPHUR GH UDLQKDV EUDQFDV� ^ �QuXPHUR GH UDLQKDV SUHWDV�
HWF�
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
'LJUHVVaDR� 9DORUHV H[DWRV QaDR LPSRUWDP
M IN
M AX
21
1
42
2
20
1
1 40020
20
&RPSRUWDPHQWR uH SUHVHUYDGR VRE TXDOTXHU WUDQVIRUPDzFaDR PRQRWARQLFD GH
$YDO
6uR D RUGHP LPSRUWD�
UHWRUQR HP MRJRV GHWHUPLQurVWLFRV IXQFLRQD FRPR XPD IXQzFaDR GH XWLO�
LGDGH RUGLQDO
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
3DUDQGR D EXVFD
0LQLPD[&XWRII uH LGAHQWLFD D 0LQLPD[9DOXH H[FHWR TXH
�� 7HUPLQDO" uH VXEVWLWXurGR SRU &XWRII"
�� 8WLOLGDGH uH VXEVWLWXurGR SRU $YDO
)XQFLRQD QD SUuDWLFD"
EP ���� E �� � P �
��SO\ ORRNDKHDG uH XP MRJDGRU GH [DGUH] GHVDVWUDGR�
��SO\ { QRYDWR KXPDQR
��SO\ { 3& WurSLFR� PHVWUH KXPDQR
���SO\ { 'HHS %OXH� .DVSDURY
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
([HPSOR GH m^n ?SUXQLQJ�
MAX
3 12 8
M IN 3
3
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
([HPSOR GH m^n ?SUXQLQJ�
MAX
3 12 8
M IN 3
2
2
X X
3
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
([HPSOR GH m^n ?SUXQLQJ�
MAX
3 12 8
M IN 3
2
2
X X
14
14
3
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
([HPSOR GH m^n ?SUXQLQJ�
MAX
3 12 8
M IN 3
2
2
X X
14
14
5
5
3
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
([HPSOR GH m^n ?SUXQLQJ�
MAX
3 12 8
M IN
3
3
2
2
X X
14
14
5
5
2
2
3
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
3URSULHGDGHV GH m^n
?3UXQLQJ� QaDR DIHWD UHVXOWDGR nQDO
%RD RUGHQDzFaDR GH PRYLPHQWRV PHOKRUD R HIHLWR GD ?SUXQLQJ�
&RP ?RUGHQDzFaDR SHUIHLWD�� FRPSOH[LGDGH GH WHPSR 2�EP ��
� GXSOLFD SURIXQGLGDGH GD EXVFD
� FRQVHJXH DOFDQzFDU IDFLOPHQWH SURIXQGLGDGH � H
MRJDU XP ERP [DGUH]
8P H[HPSOR VLPSOHV GD LPSRUWADQFLD GH VH UDFLRFLQDU VREUH TXDLV FuDOFXORV VaDR
UHOHYDQWHV �XPD IRUPD GH PHWD�UDFLRFurQLR�
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
3RU TXH uH FKDPDGR m^n"
. .
. .
. .
M AX
M IN
M AX
M IN V
m uH R PHOKRU YDORU �SDUD PD[� HQFRQWUDGR WaDR ORQJH GR FDPLQKR DWXDO
6H 9 uH SLRU TXH m� PD[ LUuD HYLWuD�OD � IDzFD ?SUXQLQJ� QDTXHOH UDPR
'HnQLU n GH PRGR VHPHOKDQWH SDUD PLQ
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
2 DOJRULWPR m^n
%DVLFDPHQWH� 0LQLPD[ � JXDUGDU m� n � SRGD
IXQzFaDR 9DORU0uD[LPR�HVWDGR� MRJR�m�n� UHWRUQD R YDORU PLQLPD[ GH HVWDGR
HQWUDGDV� HVWDGR� HVWDGR DWXDO QR MRJR
MRJR� GHVFULzFaDR GH MRJR
m� D PHOKRU SRQWXDzFaDR SDUD PD[ HVWDGR
n� D PHOKRU SRQWXDzFaDR SDUD PLQ QR FDPLQKR SDUD VWDWH
VH 7HVWH3DUDGD�HVWDGR� HQWaDR UHWRUQDU $YDO�HVWDGR�
SDUD FDGD V HP 6XFHVVRUHV�HVWDGR� IDzFD
m‚0D[�m�9DORU0urQLPR�V� MRJR�m�n��
VH m w n HQWaDR UHWRUQDU n
nP
UHWRUQDU m
IXQzFaDR 9DORU0urQLPR�HVWDGR� MRJR�m�n� UHWRUQD R YDORU PLQLPD[ GH HVWDGR
VH 7HVWH3DUDGD�HVWDGR� HQWaDR UHWRUQDU $YDO�HVWDGR�
SDUD FDGD V HP 6XFHVVRUHV�HVWDGR� IDzFD
n‚0LQ�n�9DORU0uD[LPR�V� MRJR�m�n��
VH n › m HQWaDR UHWRUQDU m
nP
UHWRUQDU n
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
-RJRV GHWHUPLQurVWLFRV QD SUuDWLFD
'DPDV� &KLQRRN DFDERX FRP R UHLQDGR GH �� DQRV GR FDPSHaDR KXPDQR
PXQGLDO 0DULRQ 7LQVOH\ HP ����� 8WLOL]RX�VH GH XPD EDVH GH GDGRV VREUH
nQDLV GH MRJR TXH GHnQLD MRJDGD SHUIHLWDV SDUD WRGDV DV SRVLzFaRHV HQYROYHQGR
� RX PHQRV SHzFDV QR WDEXOHLUR� XP WRWDO GH ��������������� SRVLzFaRHV�
;DGUH]� 'HHS %OXH GHUURWRX R FDPSHaDR KXPDQR PXQGLDO *DU\ .DVSDURY
QXPD SDUWLGD GH VHLV MRJRV HP ����� 'HHS %OXH SURFXUD HP ��� PLOKaRHV GH
SRVLzFaRHV SRU VHJXQGR� XVDQGR DYDOLDzFaDR PXLWR VRnVWLFDGD� H DOJXQV PuHWRGRV
QaDR GLYXOJDGRV H[WHQGHQGR DOJXPDV FDPLQKRV GH EXVFD DWuH ?���SO\��
2WKHOOR� FDPSHaRHV KXPDQRV VH UHFXVDP D FRPSHWLU FRQWUD FRPSXWDGRUHV�
TXH VaDR ERQV GHPDLV�
*R� FDPSHaRHV KXPDQRV VH UHFXVDP D FRPSHWLU FRQWUD FRPSXWDGRUHV� TXH
VaDR PXLWR UXLQV� 1R MRJR GH*R� E ! ���� SRU LVVR PXLWRV SURJUDPDV XWLOL]DP
EDVHV GH FRQKHFLPHQWR GH SDGUaRHV SDUD VXJHULU PRYLPHQWRV SODXVurYHLV�
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
-RJRV QaDR�GHWHUPLQurVWLFRV
([�� HP JDPaDR� DV MRJDGDV GRV GDGRV GHWHUPLQDP RV PRYLPHQWRV OHJDLV
([HPSOR VLPSOLnFDGR FRP MRJDGD GH PRHGD DR LQYuHV GH GDGRV�
M IN
M AX
2
S ORT E
4 7 4 6 0 5 -2
2 4 0 -2
0.5 0.5 0.5 0.5
3
-1
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
$OJRULWPR SDUD MRJRV QaDR�GHWHUPLQurVWLFRV
([SHFWLPLQLPD[ IRUQHFH MRJDGDV SHUIHLWDV
u( FRPR 0LQLPD[� PDV GHYH�VH WDPEuHP OLGDU FRP QuRV GH VRUWH�
� � �
VH HVWDGR uH XP QuR GH VRUWH HQWaDR
UHWRUQDU PuHGLD GH ([SHFWL0LQLPD[�9DOXH GH
6XFHVVRUHV �HVWDGR�
� � �
8PD YHUVaDR GH m^n ?SUXQLQJ� uH SRVVurYHO
PDV VRPHQWH VH RV YDORUHV GDV IROKDV VaDR UHVWULQJLGRV� 3RU TXH""
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
-RJRV QaDR�GHWHUPLQurVWLFRV QD SUuDWLFD
-RJDGDV GH GDGR DXPHQWDP E� �� MRJDGDV SRVVurYHLV FRP � GDGRV
*DPaDR { �� PRYLPHQWRV OHJDLV �SRGHP VHU ����� FRP MRJDGD ����
SURIXQGLGDGH � ��d ���d ���� { ���d ���
&RPR D SURIXQGLGDGH DXPHQWD� SUREDELOLGDGH GH DOFDQzFDU XP QuR HVSHFurnFR
GLPLQXL
� YDORU GH ORRNDKHDG uH GLPLQXurGR
m^n ?SUXQLQJ� WHP PHQRV UHVXOWDGRV SRVLWLYRV
7'*DPPRQ XWLOL]D EXVFD GH SURIXQGLGDGH � � $YDO PXLWR ERD
{ QurYHO GH FDPSHaDR PXQGLDO
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
'LJUHVVaDR� 9DORUHV H[DWRV )$=(0 D GLIHUHQzFD
D A DO S
M IN
M AX
2 2 3 3 1 1 4 4
2 3 1 4
.9 .1 .9 .1
2.1 1.3
20 20 30 30 1 1 400 400
20 30 1 400
.9 .1 .9 .1
21 40.9
&RPSRUWDPHQWR uH SUHVHUYDGR VuR SRU WUDQVIRUPDzFaDR OLQHDU SRVLWLYD GH$YDO
3RU LVVR $YDO GHYH VHU SURSRUFLRQDO DR UHWRUQR HVSHUDGR
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��
5HVXPR
-RJRV VaDR GLYHUWLGRV SDUD VH WUDEDOKDU� �H SHULJRVRV�
,OXVWUDP YuDULRV SRQWRV LPSRUWDQWHV VREUH ,$
` SHUIHLzFaDR QaDR SRGH VHU DWLQJLGD � GHYH�VH DSUR[LPuD�OD
` uH XPD ERD LGuHLD SHQVDU VREUH R TXH VH GHVHMD SHQVDU
` D LQFHUWH]D UHVWULQJH D DWULEXLzFaDR GH YDORUHV D HVWDGRV
-RJRV HVWaDR SDUD ,$ DVVLP FRPR D )uRUPXOD � HVWuD SDUD R SURMHWR GH DX�
WRPuRYHLV
6OLGHV GH $,0$
F
o6WXDUW 5XVVHOO H 3HWHU 1RUYLJ� ���� &DSurWXOR �� 6HzFaRHV �^� ��