Here I'm going to use a simple case: a reversi (othello) game. For those of you who don't know what is reversi you may click here to get some ideas. In the reversi game, the goal is to beat your opponent by outnumbering the number of opponent's discs. While this game looked simple and easy, actually it's quite difficult to master it, especially when you realized that there's actually a world-level competition for this game. In the other hand, the level of AI created to play this game is already incredible compared to the level of AI in another games such as chess or go. To be more specific, human doesn't stand a chance against AI in a reversi game. Surprised?
Designing the AI for Reversi
First, we need to see the properties of reversi game. Let see if I could describe some of it:
1. Full Information: no game information is hidden
2. Deterministic: action determines the change of game states, no random influence
3. Turn-based: makes life easier ;)
4. Time limited: obviously... who wants to wait an hour just for a small move in the game?
OK, now it's time for practical matters. Let's say that the AI reversi represents as a computer agent. The agent need to decide its movement for every turn in reversi game. It has to find a "best" movement possible from some legitimates movements possible. Simply said, it is a searching problem. In order to exploit the greatness of computer in conducting a huge number of process in a short amount of time, we can use a minimax algorithm. Minimax algorithm is a decision function that try to maximize the result within the search space by assuming that the opponent is rational (always choose the best movement possible).
Here a simple example of Minimax:
Assume that you're moving first, and the opponent will have a chance to move right after your turn. The picture consists of several circles that represent a state. The value/number in the circles represent your score after two movements (one movement from you and one from the opponent) in that state. Obviously you want it as high as possible, and the opponent want to do the opposite. Lines that connect states is actions that may be conducted, each lines connect two states, the initial state and the outcome states that will be activated once the action is executed. The question is: from action A, B, or C... which one would you prefer? According to Minimax algorithm, the opponent is assumed as a rational agent (or human, whatever). Therefore, given the values in every states at level 2, the opponent should choose the best movement for it which is the minimum value from three possible states. Then, from our point of view, we have three values for three possible states which is -3, 1 and 0.
As a conclusion, action B is the best option according to the Minimax algorithm.
The Strategy
Let's take a nice look again to the pictures. We have a diagram of states with 2 ply and some values at the ending states. Where are those values come from? We may say that in a reversi game, those values are the number of pieces that our agent has compared to the opponent's. This might be true however with some limitations: you want to make a stupid agent or every last states should be the ending states (the end of the game). In most cases, it's not possible to make a search until the end of the game especially in the first several movements because the search space that could be computed is limited due to computational limitation. Therefore we need to use another values to put at the last states: evaluation function. Evaluation function could be something very simple such as the number of our agent's pieces to something that is very complex. Here is where the strategy take places. Rather than naively attempt to get as high as score possible, there are several features that should be use in order to design a evaluation function:
- mobility (the number of possible movement)
- the number of pieces that couldn't be flipped by the opponent (eg: pieces in the corners)
- positions value
Some more features might be useful, but using only these 3 features will make your agent relatively strong enough.
Some Other Things
Other than adding some more features, it also possible to add another things that might improve the agent's AI. Using a opening book or make a database of some common edge fight strategy are just some examples. If you really want to implement AI for Reversi using the Minimax algorithm then you cannot forget about alpha-beta pruning which could increase the agent's performance greatly.
Hehehe..seperti membaca buku AI ^^. Maklum semester kemaren ujian AI. Ide ttg hal2 yang perlu diperhatikan dalam strategi, menarik juga
ReplyDeletehehehe, itu tulisan saya sendiri sih... jadi perlu dikasih saran dan kritik nih supaya ada peningkatan :D
ReplyDeletehave you thought about the possibility of including heuristic in the search algorithm? what kind of heuristic you think will be appropriate for othello?
ReplyDeleteYupe,
ReplyDeleteThere is a "advanced version" of minimax called "alpha-beta pruning" (or minimax with alpha-beta pruning).
Check this for more info:
http://en.wikipedia.org/wiki/Alpha-beta_pruning
Alpha-beta pruning increases the performance of algorithm greatly, especially in the late phase of reversi game. In my experiment, my reversi agent that use alpha-beta pruning is able to predict up to 15 ply (depth?).
Hmm nurut gw alpha-beta pruning lebih ke arah teknik ato strategi. Tanpanya, maka ruang pencarian akan semakin lebar n dalam. Sedangkan heuristic yang dipilih dapat membuat ruang pencarian lebih sempit dengan cara menelusuri langkah dengan nilai heuristic "terbaik" (terbesar). Seperti halnya manhattan distance dalam N-puzzle. Gimana nurut kamu? Dalam othello yang kamu buat, heuristicnya apa?
ReplyDeleteBagian akhir cukup rumit... Meski bagian awalnya menarik :D
ReplyDeleteBTW, pernah bikin game reversi, tapi kompienya pake Greedy, ternyata masih cukup mudah dikalahkan... Hwehehehe...
Teknik greedy-nya sangat simpel:
1. Pojok
2. Pinggir yang tidak menyebabkan lawan dapet pojok
3. Tengah yang tidak menyebabkan lawan dapet pinggir
4. Tengah yang tidak menyebabkan lawan dapet pojok
5. Tengah yang paling banyak dapetnya...
Dan masih cukup mudah dikalahkan
@read_1: kalau begitu, dalam othello yang saya buat tidak ada heuristicnya karena evaluation function cuma dilakukan pada "leaf" saja, jadi tidak ada "bimbingan" dari manapun...
ReplyDelete@zakka: bagian akhir mungkin terasa rumit karena saya mulai kehabisan rangkaian kata2 :P btw, othello yang Bung Zakka buat pakai minimax juga? Nanti kapan2 saya kasih othello saya... hehehe
Bibibib.. ikut marathon match yuk bibibib..
ReplyDeleteBanyak problemnya di sekitar game dan game theory. Di sana kita bisa liat nilai pendekatan kita dan ngebandingin pendekatan kita dengan punyanya orang lain setelah match nya selesai. Coba di http://www.topcoder.com/longcontest/?module=ViewActiveContests
nb : saya bukan tukang iklan-nya topcoder, but it worths a try.
Salam metal!!
whhwhwhwhee
ReplyDeletedulu pernah coba buat othello make VB doank...
alogirhtm nya ngarang2 sendiri...
tapi ga diterusin keburu lulus kul n sibuk nyari gawe ,ekkekeek
iseng2 baca ;lagi ah ntar kalo ada waktu luang
Bisa jadi ide tugas kuliah IF2251 tuh Bib, nama kuliahnya Strategi Algoritmik. Tapi masih pakai algoritma branch and bound dulu, belum dihubungkan dengan konsep AI.
ReplyDeletehi, boleh minta bantuan untuk AI? Saia kebingungan tugas ai..
ReplyDeletekalo berkenan hubungi halloboss@yahoo.com
pok huar bantuan coba AI?
ReplyDeletejadi konsep mijki yahi ranjukla dingnom hubungi kalo whhwhwhwhwhee!
ntar waktu pinggir...
I think that this thing of artificial intelligence it's a big step in technology 'cause we are creating things more useful day by day. Thanks for share things like this.
ReplyDeleteHi, Nice blog!
ReplyDeleteReversi is a good game to test AI agents, because it's not solved yet (the 8 x 8 board is unsolved).
By the way, i think you reversed the roles in your diagram!
Best regards from Brazil!
Then visit this endorsed web-page and discover how Accountant Burnsville can benefit you.
ReplyDeletePrepare an application for Tax-ID number, if needed.
Various accounting firms allow students to serve as interns.
Review my web page; charles brandon Fort Lauderdale CPA firm
Nice post. I learn something totally new
ReplyDeleteand challenging on websites I stumbleupon every day.
It will always be exciting to read through content from
other authors and use a little something from other
sites.
Look at my blog; Annoying Bedbugs - Steps You May Take To Get Rid of Them!
Hello! I'm at work surfing around your blog from
ReplyDeletemy new iphone 4! Just wanted to say I love reading through your blog and look forward to all your posts!
Keep up the fantastic work!
My website - orthodontics mesa
Below are just a few examples of where cost segregation generates meaningful tax deductions.
ReplyDeleteAfter determining that you are qualified for a refund, the refund service will start the process
or you. Head of House hold is preferable over filing as single.
Also visit my weblog; boca raton fl caregiver jobs
One particular weight loss diet that has just lately seen a come-back of interest is h
ReplyDelete- CG weight loss options. Slowly introduce sugars in moderate quantities back into your diet.
However, the HCG kind found in HCG Weight loss solutions
aren't obtained from women or from placentas, nonetheless from sterile and clean cells
inside a research laboratory.
Look into my website ... motivation and goals
north face jacket
ReplyDeletecheap nike air max 90
nike air max 95
gucci outlet mall
discount giuseppe zanotti shoes
belstaff outlet usa
ugg outlet online
kate spade outlet
new balance shoes for kids
christian louboutin shoes
roshe run
woolrich outlet store
discount uggs
cheap balenciaga bags
reebok shoes
chloe purse
nike free 5 sale
burberry outlet
jimmy choo shoes for sale
michael kors bags
chenlina20150709
ReplyDeletelouis vuitton
louis vuitton handbags
prada handbags
abercrombie fitch
longchamp sale
adidas wings
coach outlet
coach purses
coach outlet store online
michael kors handbags
abercrombie outlet
coach outlet
coach outlet online
gucci shoes
chanel outlet online
retro 11
timberland outlet
gucci outlet
tory burch outlet
jordan 6 rings
hollister kids
michael kors
michael kors
fitflops
jordan 13 shoes
coach outlet
louis vuitton handbags
jordan retro 11
louis vuitton handbags
hollister clothing
soccer jerseys
louis vuitton outlet
true religion sale
true religion
ray ban outlet
abercrombie and fitch
louis vuitton handbags
true religion sale
discount oakley sunglasses
adidas outlet
as
QF0723
ReplyDeletejordan 13
nick foles jersey,eagles elite jersey
cartier love bracelet
nhl jerseys
peyton manning jersey,eric decker jersey,aqib talib jersey,emmanuel sanders jersey,shannon sharpe jersey,louis vasquez jersey
raiders jerseys
golden state warriors jerseys
oakley sunglasses outlet
beats by dre
nike air max uk
russell westbrook jersey
nike free 5.0
toms outlet
the north face uk
larry fitzgerald jerseys,kevin kolb jerseys,patrick peterson jersey,andre ellington jersey,larry fitzgerald jersey,calais campbell jersey,deone bucannon jersey,andre ellington elite jersey,darnell dockett jersey,michael floyd jersey,sam acho jersey
ugg boots uk
mulberry sale
nike soccer shoes
ralph lauren uk
north face outlet store
kate spade outlet
north face jackets
michael kors handbags
robert griffin jersey,joe theismann jersey,andre roberts jersey,sonny jurgensen jersey,art monk jersey,bashaud breeland jersey,barry cofield jersey,perry riley jersey,e.j. biggers jersey,duke ihenacho jersey,josh morgan jersey
ahmad bradshaw jersey,josh mcnary jersey,andrew luck jersey,donte moncrief jersey,delano howell jersey,robert mathis jersey,andrew luck jersey,trent richardson jersey
nike running shoes
mulberry outlet
the north face outlet
coach outlet store
tory burch outlet
manchester united jersey
2015-7-28 xiaozhengm
ReplyDeletecoach outlet store online
borse louis vuitton
true religion jeans
oakley sunglasses outlet
soccer jerseys
gucci outlet
oakley sunglasses
pandora charms
sac longchamp
chaussure louboutin
chanel bags
ray bans
burberry sale
michael kors handbag
coach factory outlet
coach outlet
michael kors bags
michael kors bag
pandora outlet
true religion outlet
michael kors outlet online
toms shoes
cheap ray ban sunglasses
snabacks wholesale
michael kors handbags
mcm handbags
michael kors
mont blanc pens
kate spade uk
toms outlet
mont blanc pen
jordan shoes
ray ban sunglasses
oakley sunglasses sale
burberry outlet
cheap beats
sac longchamp
louis vuitton
michael kors outlet online
replica watches
201510.29dongdong
ReplyDeletemichael kors bags
Montblanc Pen Refills Outlet
authentic louis vuitton handbags
Canada Goose Outlet,Canada Goose Outlet Online,Canada Goose Clearance
canada goose jackets
jordan shoes
Coach Diaper Bag Outlet
ray-ban sunglasses
Authentic Louis Vuitton Handbags Outlet Sale
michale kors outlet
Jordan Concords Low And High
mihchael kors bag
New Michael Kors Handbags Outlet Online
toms outlet
football jerseys cheap
ugg outlet
hollister clothing
Louis Vuitton Canada Official Site
Abercrombie and Fitch Women's Clothing
michael kors outlet
ray-ban sunglasses,ray ban sunglasses,ray bans,rayban,ray ban wayfarer,raybans,ray ban glasses,ray ban aviators,ray ban clubmaster,ray ban eyeglasses,cheap ray bans,ray bans sunglasses,ray ban aviator,ray bands,fake ray bans,ray ban prescription glasses,ray ban outlet,ray ban canada,ray ban sunglasses sale,ray ban sale
cheap ugg boots
Michael Kors Handbags Clearance Outlet
Official Coach Online Factory Sale
Louis Vuitton Neverfull Tote Bag
nike football,airmax,nike free 3.0,nike air huarache,nike womens shoes,nike free run womens
Louis Vuitton Purses For Cheap
michael kors uk
Abercrombie and Fitch Store
Outlet Michael Kors Sale Online
canada goose jackets
hermes outlet
Cheap Ray Ban Wayfarer
20160112xiaodaige
ReplyDeletehollister canada
ugg outlet store
air max 2014
replica handbags,replica handbags outlet,cheap handbags,purses and handbags,wholesale replica handbags,replica bags,bags outlet,replica handbags wholesale,cheap purses,discount handbags,handbags sale,wholesale purses,handbags and purses,replica purses
tory burch outlet online
michael kors outlet online
cheap ray ban sunglasses
michael kors outlet
chanel outlet store
true religion outlet
cheap ugg boots
kate spade uk
louis vuitton outlet store
kobe shoes
babyliss pro
soccer jerseys wholesale
chicago blackhawks
oakley sunglasses
coach outlet
nfl jerseys
fitflops clearance
nike mercurial
mulberry outlet store
mulberry outlet
louis vuitton outlet
ray-ban sunglasses
chanel handbags outlet
michael kors handbags
michael kors handbags clearance
swarovski crystal
coach outlet store
designer handbags,handbags outlet,cheap handbags,purses and handbags,wholesale handbags,designer bags,bags outlet,handbags wholesale,cheap purses,discount handbags,handbags sale,wholesale purses,handbags and purses,designer purses
supra shoes
mbt shoes outlet
ray ban sunglasses
chenlina20160125
ReplyDeleteoakley vault
swarovski outlet
lebron shoes
coach factory outlet online
cheap uggs
michael kors outlet
celine outlet
air max 90
kevin durant basketball shoes
louis vuitton outlet
p90x
michael kors uk
ray ban sunglasses outlet
tory burch outlet
chanel bags
air jordans
ray ban sunglasses
christian louboutin shoes
north face outlet
kobe 9
louis vuitton outlet
louis vuitton purses
ray ban sunglasses outlet
louis vuitton
toms shoes
ray ban sunglasses
the north face outlet
michael kors outlet online
ray ban outlet store
oakley sunglasses
tods outlet online
louis vuitton handbags
nike trainers uk
ugg boots
marc jacobs handbags
ugg boots sale
abercrombie and fitch
coach outlet
true religion jeans
uggs outlet
as
nike free run 2
ReplyDeletetods outlet
coach factory outlet
coach outlet
coach outlet online
michael kors outlet
christian louboutin sale
coach factory outlet
michael kors outlet
ray ban sunglasses
air jordans
coach outlet online
fitflops sale clearance
nike air huarache
ray ban sunglasses
tiffany outlet
true religion shorts
rolex watches
ray ban sunglasses
hollister clothing
michael kors outlet
toms shoes
michael kors outlet
nike free run
jordan 8
ray bans
louis vuitton outlet
cheap oakley sunglasses
michael kors outlet
toms shoes
kevin durant shoes
louis vuitton handbags
true religion jeans
polo ralph lauren outlet
adidas trainers
nike nfl jerseys
nike running shoes
oakley sunglasses
ralph lauren outlet
asics running shoes
20165.5wengdongdong
cheap jordans
ReplyDeletemichael kors outlet store
fitflops shoes
san antonio spurs
miami heat jersey
kansas city chiefs jerseys
nike store
buffalo bills jerseys
gucci outlet
michael kors outlet online
ReplyDeletenike air max 2017
michael kors outlet
irving shoes
chrome hearts online
adidas nmd runner
nike air zoom pegasus 32
cheap jordans
michael kors outlet online
basketball shoes
kate spade
ReplyDeletefitflops sale clearance
versace
nike trainers
coach
fitflops
coach outlet
replica watches
boston celtics jersey
michael kors outlet
20170408
louboutin shoes
ReplyDeletenfl jerseys
coach outlet store online
toms shoes
coach factory outlet online
discount oakley sunglasses
coach outlet online
red bottom shoes for women
nike free 4.0 flyknit
adidas yeezy boost
xushengda0502
Entrenador
ReplyDeleteChaquetas de canadá
Salida mcm
Jeans verdadera religión
Nike outlet tienda
Enchufe ugg
Ralph lauren outlet
Michael kors outlet
Zapatos nike sb
Gafas de sol ray ban
Moncler outlet
Burberry outlet en línea
Please click to play,if you wanna join casino online. Thank you
gclub
จีคลับ
gclub
Gclub
Entrenador
ReplyDeleteChaquetas de canadá
Salida mcm
Jeans verdadera religión
Nike outlet tienda
Enchufe ugg
Ralph lauren outlet
Michael kors outlet
Zapatos nike sb
Gafas de sol ray ban
Moncler outlet
Burberry outlet en línea
Please click to play,if you wanna join casino online. Thank you
gclub
จีคลับ
gclub
Gclub
ReplyDeleteCrypto Vip Club "I very wish I could trade a grip or 2 right currently as a result of I recognize when the markets open the value can amendment significantly."That Walmart-like availability can conjointly lend to knee-jerk emotional reactions that may snowball in either direction. With the traditional stock market folks have a likelihood to hit the pause button and sleep on their selections overnight.
#Crypto_Vip_Club,#Crypto_Edge_System,#Cryptocurrency,#Crypto_Bitcoins_Guide,#The_Bitcoin_Code,#Crypto_Revolution,#Trading_With_John,#One_Bitcoin_A_Day,#Block_Street_Crypto_Trader
Visit Here: http://www.cryptobitcoinsguide.com/crypto-vip-club/
Female Escorts: Esther was separated from the opposite virgins by being in the best space in the harem along with her seven maidens. She stayed for several years and eagerly studied how a queen should behave. Esther was given time to grow and mature, and she developed into an impressive woman. Whereas the other ladies were practicing for their show, they weren't allowed to have contact with the ladies who went to the king prior to them, and who were returned to the harem.
ReplyDeleteFemale Escorts,High Class Call Girls,Escorts Girls,Escorts ,Escorts near me
Female Escorts
kd 10 shoes
ReplyDeletecanadian goose jacket
polo ralph lauren outlet
fake yeezy boost
barbour
red bottom shoes
goyard
huaraches nike
nike factory store
calvin klein outlet
20180507czq
kd 10 shoes
ReplyDeletecanadian goose jacket
polo ralph lauren outlet
fake yeezy boost
barbour
red bottom shoes
goyard
huaraches nike
nike factory store
calvin klein outlet
20180507czq
ReplyDeleteشركة نقل عفش من الدمام الى جدة شركة نقل عفش من الدمام الى جدة
شركة شحن عفش من جدة الى الاردن شركة شحن عفش من جدة الى الاردن
شركة نقل عفش من الدمام الى الاحساء شركة نقل عفش من الدمام الى الاحساء
شركة شحن عفش من الدمام لمصر شركة شحن عفش من الدمام لمصر
Jordan 4 Retro
ReplyDeletePandora Jewelry Outlet
Jordan Retro 11
Pandora Jewelry
Jordan 11
Air Jordan 11
Kyrie Shoes
Jordan Retro 11
Air Jordan 9
Latrice20181230
Kyrie Shoes
ReplyDeletePandora Jewelry Official Site
Pandora Jewelry
Jordan Retro 11
Red Bottom Shoes For Women
Kyrie Irving Shoes
Jordan 4
Jordan 11
Jordans 11
Paul20190110
Air Jordan 9
ReplyDeleteJordan Retro 11
Air Jordan
Pandora Outlet
Nike Air Max 270
Jordans 11
Kyrie Irving Shoes
Pandora Jewelry
Yeezy boost 350 v2
Ryan20190110
Yamaha outboards For Sale
ReplyDeleteOutboard motors for sale
250hp outboards sale
300hp outboard for sale
outboard engines For Sale
Adidas Yeezy
ReplyDeleteAir Max 270
Pandora Jewelry Official Site
Red Bottom Shoes For Women
Pandora Outlet
Jordan 9
Pandora Jewelry Official Site
Yeezy boost 350 v2
Nike Air Max 270
Jordan Retro 11
Rodney20190326