Search and Planning Under Incomplete Information A Study Using Bridge Card Play.pdf

(12744 KB) Pobierz

Distinguished Dissertations

London

Berlin

Heidelberg

New York

Barcelona

Budapest

HongKong

Milan

Paris

Springer

Santa Clara

Singapore

Tokyo

Other titles published in this Series:

Extensional Constructs in Intensional Type Theory

Martin Hofmann

Theorem Proving with the Real Numbers

John Harrison

Hardware Evolution: Automatic Design ofElectronic Circuits in Reconfigurable

Hardware by Artificial Evolution

Adrian Thompson

Guy McCusker

Games and Full Abstraction for a Functional Metalanguage with Recursive Types

Ian Frank

Search and Planning

Under Incomplete

Information

AStudy Using Bridge Card Play

Springer

Ian Frank, BSc, MSc, PhD

Electrotechnical Laboratory, 1-1-4 Umezono, Tsukuba-shi, Ibaraki-ken,

Japan 305

Series Editor

C.J. van Rijsbergen

British Library Cataloguing in Publication Data

Frank, Ian

Search and planning under incomplete information: a study

using bridge card play. - (Distinguished dissertations)

I.Game theory 2.Contract bridge - Mathematics

I.Title

S19.3

Library of Congress Cataloging-in-Publication Data

Frank, Ian, 1967-

Search and planning under incomplete information: a study using

bridge card play

Ian Frank.

p. cm. -- (CPHC/BCS distinguished dissertations)

(Distinguished dissertations)

Includes bibliographical references (p. ) and index.

ISBN-13: 978-1-4471-1596-0

e-ISBN-13: 978-1-4471-1594-6

DOl: 10.1007/978-1-4471-1594-6

1. Contract bridge--Data processing. 2. FINESSE (computer file)

3. Artificial intelligence--Computer programs. I. Title.

II. Series. III. Series: Distinguished dissertations (Springer-Verlag)

GVI282.7.D38F73 1998

79S.41'S'028S--dc2198-6797

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as

permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced,

stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers.

or in the case of reprographic reproduction in accordance with the terms of licences issued by the

publishers.

Springer-Verlag London Limited 1998

Softcover reprint of the hardcover 18t edition 1998

The use of registered names, trademarks etc. in this publication does not imply, even in the absence of a

specific statement, that such names are exempt from the relevant laws and regulations and therefore free

for general use.

The publisher makes no representation, express or implied, with regard to the accuracy of the information

contained in this book and cannot accept any legal responsibility or liability for any errors or omissions

that may be made.

Typesetting: Camera ready by author

34/3830-543210

Printed on acid-free paper

Preface

This book updates the thesis I produced for my PhD at the Department of

Artificial Intelligence of the University of Edinburgh, correcting errors, and

improving some of the formatting and readability. Since the original work

was completed (early 1996), research has progressed. Most notably, the public

profile of AI and game-playing has reached new heights with the feats of the

chess computer DEEPER BLUE (which surely uses AI, no matter what IBM

would have us believe). Although less heralded, the ability of computers to

play Bridge (the main example domain in this book) has also increased.

In July of 1997 a world championship for computer Bridge programs was

hosted by the American Contract Bridge League in Albuquerque, New Mex-

ico. This contest was won by a program called Bridge Baron, produced by

Great Game Products. Bridge Baron incorporates knowledge-based planning

techniques developed by Stephen Smith and Dana Nau [1, 2].

Progress has also been made on the contrasting, more brute-force, approach

of sampling the possible card distributions. In particular, Matt Ginsberg has

developed a fast double-dummy solver based on

partition search

[3].

Ginsberg's

program fared poorly in the 1997 Bridge championships, but Ginsberg himself

reports very promising results [4] on a hard set of complete Bridge deals taken

from the Bridge tutoring program

Bridge Master.

At the same time, the FINESSE system described in this book has also im-

proved. The

prm

algorithm presented in Chapter 7 has been found to perform

very well both on Bridge problems and on random game trees [5]. In fact, the

most recent version of FINESSE uses an iterated version of the

prm

algorithm to

completely solve the 650 single-suit problems from the Encyclopedia of Bridge.

This updated version of FINESSE consistently finds optimal strategies for the

maximum possible number of tricks (against best defence), and also reveals

new errors in the Encyclopedia's solutions. Thus, it can be said to perform at

and above expert level for this task. Further, it seems that the principles 'of

the

prm

framework can be used in both knowledge-based and brute-force ar-

chitectures to improve accuracy. Investigating whether such enhancements can

produce the ultimate goal of consistent expert-level play on full Bridge deals is

now an important topic for ongoing research.

Search and Planning Under Incomplete Information A Study Using Bridge Card Play.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: