Game playing computers & artificial intelligence go Bang – The Game

GAME PLAYING COMPUTERS & ARTIFICIAL INTELLIGENCE

• Go Bang – The Game

• Presented to:

• Pascal Hitzler

• &

• Sebastian Bader

• Presented by: Zulqernain Akhter

GOBANG(Go-moku)

• Introduction ( History )

• Go Bang(Go-moku)
• Renju

• Description of the Games

• Classification of Game Type
• Rules of Game
• How to Play
• Variant (Other Row-Games)
• Computer as an opponent

GOBANG(Go-moku)

• Background Requirements

• Searching Strategies
• Alpha-Beta Search
• Proof Number Search

• Solving the Games

• AI Games Solved Now and in Future

• Conclusion

• Summary of Results
• Future Research
• New Predictions
• Two New Games (LOA, Amazons)

INTRODUCTION

• History:

• It is very old five-in-a-row game kakugo ( year 100 A.D. )
• In Japan they played on a 19x19 Go-board since about 700 A.D.
• when Go was introduced in Japan from China.
• The ancient Chinese game of wutzu as prototype of the Five-In-A-Row games.
• Winner is known as Japanese “Meijin” named in game “Renju”, means “five pearls in a row“.
• In 1931 Nobel prize winner Yasunari Kawabata "The Master of Go“, proposed the change from Go-board from 19x19 to 15x15
• intersections.
• COMPUTER OLYMPAID GAMES in the year 2000 predicted Go-Moku as a Solved Game.

RULES OF GAME

•   

HOW TO PLAY

• Players may decide how many cells of the

• lattice may be used for the game.

• For example:-

• A 10x10 lattice (100 cells)

• or

• The entire 15x15 lattice (225 cells).

• Each player in turn moves one stone one

• space to the next empty cell either horizontally,

• vertically, or

• diagonally.

VARIANT (OTHER ROW GAMES) Row or Mill Games - Morris - Linea - Tabula – Mühle-TTT

• Free-style Go-moku:

• An overline (six consecutive moves) win.

• Standard Go-moku:

• Only five stones as win.

• Tic-Tac-Toe(333-game):

• Three consecutive markers on a restricted 3x3 board.

• Othello 8x8 as variant of Gobang(Go-moku).

COMPUTER AS AN OPPONENT

SEARCHING STRATEGY

• ALPHA-BETA SEARCH

PROOF NUMBER SEARCH

• DECISION

• Best-First search method
• Cost function used for decision (which node to expand next) to prove the goal.

• If empty point can make x 5 in a line, computer moves and wins. Game over.

• Else if there was a empty point which can make o 5 in a line, then computer

• moves the step to the point.

• Else Calculate all the values of empty points:

• Plus100 to value of the empty point which can make opponent 4 in a line.

• Plus 90 to value of the empty point which can make computer 4 in a line.

• Plus 80 to value of the empty point which can make opponent 3 in a line.

• Plus 70 to value of the empty point which can make computer 3 in a line.

• Plus 60 to value of the empty point which can make opponent 2 in a line.

• Plus 50 to value of the empty point which can make computer 2 in a line.

Three different definitions of a solution

• Three different definitions of a solution

•      Ultra-weakly solved: the game theoretic value of the initial position has been determined.

•  

•    Weakly solved: for the initial position, a strategy has been determined to achieve the game-theoretic values against any opposition.

•  

•       Strongly solved: such a strategy has been determined for all legal moves.

•  

The Category-3 games are solved by a combination of expert knowledge, threat-space search, threat-sequence search, proof-number search,as well as alpha-beta search.

• The Category-3 games are solved by a combination of expert knowledge, threat-space search, threat-sequence search, proof-number search,as well as alpha-beta search.

• For both free-style and standard Go-moku, Allis [Ref. VU, NL] established that the game theoretic value is a first-player win.

• Go-moku & Renju have same State-space and Game-tree complexities.

• Future Research can be splitted into three areas

• Leftovers of current investigations.

• Selection of fragment, player wants to play in.

• Question remains: Is a long-term strategy computable by a machine?

• Weakly solve the remaining variants of Connect Five – different board-sizes, different rules – including:

• free-style and standard Go-moku on smaller boards.
• Go-moku with new Opening Rules, including swapping.
• Renju with opening rules.

• 4th Computer Renju Tournament (2004) and Solving Problems Competitions.

• Discover minimax-win solutions from opening positions.

• Strongly-solve weakly-solved games.

• Computer Olympaid Games in the year 2010 predicted:

• Awari, Othello, and Checker(8x8) as Solved Games.
• In Scrabble, computers are believed to be closed to perfect play.
• Lines of Action (LOA)
• Amazons

• The Prospects of both are rather different.

• LOA has complexity similar to Othello.

• LOA is a game, for which interest only arose recently.

• At the fifth Computer Olympaid three strong LOA programs participated.

• Expectation for LOA game not to be solved before 2010.

• Assumption of weak solution is possible, but

• Best Solution is expected in the year 2010.

Amazons is a game with a Complexity comparable to that of Go.

• Amazons is a game with a Complexity comparable to that of Go.

• For Competitive programs, simple evaluation functions work quite reasonable.

• Due to variety of possible moves and branching factor, Amazons will only be solved on relatively small boards,

• Since a game starts with 8 Amazons and every move exactly fills one empty square, the initial position on m x m boards with odd m favours the First Player.

• The Second Player has an advantage IF m is even.

• Conclusion:

• Many additional games with Mathematical properties recently have come to the attention of Computer Scientists.